Nonmonotonic consequences in default domain theory

Default domain theory is a framework for representing and reasoning about commonsense knowledge. Although this theory is motivated by ideas in Reiter’s work on default logic, it is in some sense a dual framework. We make Reiter’s default extension operator into a constructive method of building models, not theories. Domain theory, which is a well established tool for representing partial information in the semantics of programming languages, is adopted as the basis for constructing partial models. This paper considers some of the laws of nonmonotonic consequence, due to Gabbay and to Kraus, Lehmann, and Magidor, in the light of default domain theory. We remark that in some cases Gabbay’s law of cautious monotony is open to question. We consider an axiomatization of the nonmonotonic consequence relation on prime open sets in the Scott topology – the natural logic – of a domain, which omits this law. We prove a representation theorem showing that such relations are in one to one correspondence with the consequence relations determined by extensions in Scott domains augmented with default sets. This means that defaults are very expressive: they can, in a sense, represent any reasonable nonmonotonic entailment. Results about what kind of defaults determine cautious monotony are also discussed. In particular, we show that the property of unique extensions guarantees cautious monotony, and we give several classes of default structures which determine unique extensions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Logical considerations on default semantics

We consider a reinterpretation of the rules of default logic. We make Reiter’s default rules into a constructive method of building models, not theories. To allow reasoning in first‐order systems, we equip standard first‐order logic with a (new) Kleene 3‐valued partial model semantics. Then, using our methodology, we add defaults to this semantic system. The result is that our logic is an ordinary monotonic one, but its semantics is now nonmonotonic. Reiter’s extensions now appear in the semantics, not in the syntax. As an application, we show that this semantics gives a partial solution to the conceptual problems with open defaults pointed out by Lifschitz [V. Lifschitz, On open defaults, in: Proceedings of the Symposium on Computational Logics (1990)], and Baader and Hollunder [F. Baader and B. Hollunder, Embedding defaults into terminological knowledge representation formalisms, in: Proceedings of Third Annual Conference on Knowledge Representation (Morgan‐Kaufmann, 1992)]. The solution is not complete, chiefly because in making the defaults model‐theoretic, we can only add conjunctive information to our models. This is in contrast to default theories, where extensions can contain disjunctive formulas, and therefore disjunctive information. Our proposal to treat the problem of open defaults uses a semantic notion of nonmonotonic entailment for our logic, related to the idea of “only knowing”. Our notion is “only having information” given by a formula. We discuss the differences between this and “minimal‐knowledge” ideas. Finally, we consider the Kraus–Lehmann–Magidor [S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models, and cumulative logics, Artificial Intelligence 44 (1990) 167–207] axioms for preferential consequence relations. We find that our consequence relation satisfies the most basic of the laws, and the Or law, but it does not satisfy the law of Cut, nor the law of Cautious Monotony. We give intuitive examples using our system, on the other hand, which on the surface seem to violate these two laws. We make some comparisons, using our examples, to probabilistic interpretations for which these laws are true, and we compare our models to the cumulative models of Kraus, Lehmann, and Magidor. We also show sufficient conditions for the laws to hold. These involve limiting the use of disjunction in our formulas in one way or another. We show how to make use of the theory of complete partially ordered sets, or domain theory. We can augment any Scott domain with a default set. We state a version of Reiter’s extension operator on arbitrary domains as well. This version makes clear the basic order‐theoretic nature of Reiter’s definitions. A three‐variable function is involved. Finding extensions corresponds to taking fixed points twice, with respect to two of these variables. In the special case of precondition‐free defaults, a general relation on Scott domains induced from the set of defaults is shown to characterize extensions. We show how a general notion of domain theory, the logic induced from the Scott topology on a domain, guides us to a correct notion of “affirmable sentence” in a specific case such as our first‐order systems. We also prove our consequence laws in such a way that they hold not only in first‐order systems, but in any logic derived from the Scott topology on an arbitrary domain. This revised version was published online in June 2006 with corrections to the Cover Date.     

Higher order generalization and its application in program verification

Generalization is a fundamental operation of inductive inference. While first order syntactic generalization (anti–unification) is well understood, its various extensions are often needed in applications. This paper discusses syntactic higher order generalization in a higher order language λ2 [1]. Based on the application ordering, we prove that least general generalization exists for any two terms and is unique up to renaming. An algorithm to compute the least general generalization is also presented. To illustrate its usefulness, we propose a program verification system based on higher order generalization that can reuse the proofs of similar programs. This revised version was published online in June 2006 with corrections to the Cover Date.     

Local pseudo MV-algebras

 The pseudo MV-algebras were defined in [12] as non-commutative extensions of MV-algebras. In this paper we define the local pseudo MV-algebras and we suggest a classification for these structures. The subclass of perfect pseudo MV-algebras is deeply investigated. Extending the Di Nola–Lettieri result for MV-algebras [8], we prove that the category of l-groups is equivalent to a subcategory of perfect pseudo MV-algebras.     

State‐saving transformations for efficient bottom‐up evaluation of logic programs and rule‐based systems

Redundant computations in bottom‐up evaluation of logic programs and rule‐based systems can be avoided by caching intermediate joins – i.e., partial rule instantiations – for later use. Joins can be cached either at representation level by program transformation techniques introducing supplementary predicates or at implementation level by specialized implementation techniques using internal memory cells. The efficiency of these state‐saving techniques depends on the selection of premises for storing the joins. In this paper we first present a general program transformation technique for saving joins which heuristically reorders subgoals and performs predicate splitting optimization, an extension of unfolding. This state‐saving transformation can be applied for any goal‐directed and model‐generation evaluation. It does not require any information about the query. We show that the program transformation approach is equivalent to the specialized state‐saving implementations known from production systems and model‐generation theorem provers. To use the efficient and complete bottom‐up evaluation also for query answering, we improve the supplementary extensions of Generalized Magic Sets and Magic Templates rewriting strategies by the presented state‐saving transformation. This revised version was published online in June 2006 with corrections to the Cover Date.     

On Parabolic Boundary Layers for Convection–Diffusion Equations in a Channel: Analysis and Numerical Applications

In this article we discuss singularly perturbed convection–diffusion equations in a channel in cases producing parabolic boundary layers. It has been shown that one can improve the numerical resolution of singularly perturbed problems involving boundary layers, by incorporating the structure of the boundary layers into the finite element spaces, when this structure is available; see e.g. [Cheng, W. and Temam, R. (2002). Comput. Fluid. V.31, 453–466; Jung, C. (2005). Numer. Meth. Partial Differ. Eq. V.21, 623–648]. This approach is developed in this article for a convection–diffusion equation. Using an analytical approach, we first derive an approximate (simplified) form of the parabolic boundary layers (elements) for our problem; we then develop new numerical schemes using these boundary layer elements. The results are performed for the perturbation parameter ε in the range 10⁻¹–10⁻¹⁵ whereas the discretization mesh is in the range of order 1/10–1/100 in the x-direction and of order 1/10–1/30 in the y-direction. Indications on various extensions of this work are briefly described at the end of the Introduction.Dedicated to David Gottlieb on his 60th birthday.     

Combining Nonstably Infinite Theories

The Nelson–Oppen combination method combines decision procedures for first-order theories over disjoint signatures into a single decision procedure for the union theory. In order to be correct, the method requires that the component theories be stably infinite. This restriction makes the method inapplicable to many interesting theories such as, for instance, theories having only finite models. In this paper, we describe two extensions of the Nelson–Oppen method that address the problem of combining theories that are not stably infinite. In our extensions, the component decision procedures exchange not only equalities between shared variables but also certain cardinality constraints. Applications of our results include the combination of theories having only finite models, as well as the combination of nonstably infinite theories with the theory of equality, the theories of total and partial orders, and the theory of lattices with maximum and minimum. Calogero G. Zarba: Work done by this author at Stanford University and later at LORIA and INRIA-Lorraine.     

Modelling concurrency with comtraces and generalized comtraces

Comtraces (combined traces) are extensions of Mazurkiewicz traces that can model the “not later than” relationship. In this paper, we first introduce the novel notion of generalized comtraces, extensions of comtraces that can additionally model the “non-simultaneously” relationship. Then we study some basic algebraic properties and canonical representations of comtraces and generalized comtraces. Finally we analyze the relationship between generalized comtraces and generalized stratified order structures. The major technical contribution of this paper is a proof showing that generalized comtraces can be represented by generalized stratified order structures.     

An Efficient and Accurate Method for 3D-Point Reconstruction from Multiple Views

In this paper we consider the problem of finding the position of a point in space given its projections in multiple images taken by cameras with known calibration and pose. Ideally the 3D point can be obtained as the intersection of multiple known rays in space. However, with noise the rays do not meet at a single point generally. Therefore, it is necessary to find a best point of intersection. In this paper we propose a modification of the method (Ma et al., 2001. Journal of Communications in Information and Systems, (1):51–73) based on the multiple-view epipolar constraints. The solution is simple in concept and straightforward to implement. It includes generally two steps: first, image points are corrected through approximating the error model to the first order, and then the 3D point can be reconstructed from the corrected image points using any generic triangulation method. Experiments are conducted both on simulated data and on real data to test the proposed method against previous methods. It is shown that results obtained with the proposed method are consistently more accurate than those of other linear methods. When the measurement error of image points is relatively small, its results are comparable to those of maximum likelihood estimation using Newton-type optimizers; and when processing image-point correspondences cross a small number of views, the proposed method is by far more efficient than the Newton-type optimizers.     

Pseudo-BCK algebras and PD-posets

The notion of pseudo-BCK algebras was introduced by Georgescu and Iorgulescu Proceedings of DMTCS′01: Combinatorics, Computability and Logic, Springer, London, pp 97–114, 2001. It is so general that fleas, pseudo-hoops, psMTL, psBL, pseudo-MV et al., and so hoops, MTL, BL, MV et al. can be seen its extensions. In this paper, we extend the ideal and congruence theory to pseudo-BCK algebras, and investigate the connections between pseudo-BCK algebras and PD(GPD)-posets.     

Typability in Partial Applicative Structures

Adapting a claim of Kracht (Theor Comput Sci 354:131–141, 2006), we establish a characterization of the typable partial applicative structures.     

Synthesis of optimal fuzzy estimation algorithms

Conclusion The article shows that the well-known ellipsoidal estimation formalism can be constructively extended to the case of estimating sets of a more general form. Mathematical models of these sets are defined not only by positive definite quadratic forms (as in the case with ellipsoids), but also by Lyapunov, Bellman, and other functions. We have considered the parametric properties of estimates represented by fuzzy estimating sets. A formalism approximating the set-theoretical intersection operation has been developed for these fuzzy estimates. An important feature of the proposed approach is that the intersection procedure is optimized not in each step or cycle, but over the entire sequence of steps in accordance with an additive criterion which is fairly natural for the relevant class of problems. We have thus established a relationship between optimal fuzzy set-theoretical estimation procedures and standard optimal algorithms. In the concluding part of the article we have considered state estimation of a static object from observations distorted by additive noise. The state estimation problem has been solved in the class of fuzzy ellipsoidal estimates with a so-called tolerant part. The linear “size“ or “radius“ of the tolerant part provides an efficient measure of the “degree of fuzziness“ of the estimate. On the whole, the estimation (filtering) algorithm proposed in this article, like other fuzzy estimation algorithms, is robust to prior errors. The study has been supported by US CRDF grant VE 2300. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 167–183, July–August, 1998.     

Optimization of data exchange in parallel computers with distributed memory

The problem of optimization of communications during the execution of a program on a parallel computer with distributed memory is investigated. Statements are formulated that make it possible to determine the possibility of organization of data broadcast and translation. The conditions proposed are represented in the form suitable for practical application and can be used for automated parallelization of programs. This work was done within the framework of the State Program of Fundamental Studies of the Republic of Belarus (under the code name “Mathematical structures 21”) with the partial support of the Foundation for Fundamental Studies of the Republic of Belarus (grant F03-062). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 166–182, March–April 2006.     

Interactive building and augmentation of piecewise planar environments using the intersection lines

This paper describes a method for online interactive building of piecewise planar environments for immediate use in augmented reality. This system combines user interaction from a camera–mouse and automated tracking/reconstruction methods to recover planar structures of the scene that are relevant for the augmentation task. An important contribution of our algorithm is that the process of tracking and reconstructing planar structures is decomposed into three steps—tracking, computation of the intersection lines of the planes, reconstruction—that can each be visually assessed by the user, making the interactive modeling procedure really robust and accurate with intuitive interaction. Videos illustrating our system both on synthetic and long real-size experiments are available at .     

An efficient and accurate short-characteristics solver for radiative transfer problems

Summary  In Turek (Computing 54, 27–38, 1995), the concept of the generalized mean intensity has been proposed as a special numerical approach to the (linear) radiative transfer equations which can result in a significant reduction of the dimension of the discretized system, without eliminating any information for the specific intensities. Moreover, in combination with Krylov-space methods (CG, Bi-CGSTAB, etc.), robust and very efficient solvers as extensions of the classical approximate Λ-iteration have been developed. In this paper, the key tool is the combination of special renumbering techniques together with finite difference-like discretization strategies for the arising transport operators which are based on short-characteristic upwinding techniques of variable order and which can be applied to highly unstructured meshes with locally varying mesh widths. We demonstrate how such special upwinding schemes can be constructed of first order, and particularly of second order accuracy, always leading to lower triangular system matrices on general meshes. As a consequence, the global matrix assembling can be avoided (“on-the-fly”) so that the storage cost is almost optimal, and the solution of the corresponding convection-reaction subproblems for each direction can be obtained very efficiently. As a further consequence, this approach results in a direct solver in the case of no scattering, while in the case of non-vanishing absorption and scattering coefficients the resulting convergence rates for the full systems depend only on their ratio and the absolute size of these physical quantities, but only weakly on the grid size or mesh topology. We demonstrate these results via prototypical configurations and we examine the resulting accuracy and efficiency for different computational domains, meshes and problem parameters. This paper is based on research which was supported in part by DFG grant No. TU102/16-1.     

A finite element based level set method for two-phase incompressible flows

We present a method that has been developed for the efficient numerical simulation of two-phase incompressible flows. For capturing the interface between the phases the level set technique is applied. The continuous model consists of the incompressible Navier–Stokes equations coupled with an advection equation for the level set function. The effect of surface tension is modeled by a localized force term at the interface (so-called continuum surface force approach). For spatial discretization of velocity, pressure and the level set function conforming finite elements on a hierarchy of nested tetrahedral grids are used. In the finite element setting we can apply a special technique to the localized force term, which is based on a partial integration rule for the Laplace–Beltrami operator. Due to this approach the second order derivatives coming from the curvature can be eliminated. For the time discretization we apply a variant of the fractional step θ-scheme. The discrete saddle point problems that occur in each time step are solved using an inexact Uzawa method combined with multigrid techniques. For reparametrization of the level set function a new variant of the fast marching method is introduced. A special feature of the solver is that it combines the level set method with finite element discretization, Laplace–Beltrami partial integration, multilevel local refinement and multigrid solution techniques. All these components of the solver are described. Results of numerical experiments are presented.     

Rapid scalar value classification and volume clipping for?interactive 3D medical image visualization

In many clinical scenarios, medical data visualization and interaction are important to physicians for exploring inner anatomical structures and extracting meaningful diagnostic information. Real-time high-quality volume rendering, artifact-free clipping, and rapid scalar value classification are important techniques employed in this process. Unfortunately, in practice, it is still difficult to achieve an optimal balance. In this paper, we present some strategies to address this issue, which are based on the calculation of segment-based post color attenuation and dynamic ray–plane intersection (RPI) respectively. When implemented within our visualization system, the new classification algorithm can deliver real-time performance while avoiding the “color over-accumulation” artifacts suffered by the commonly used acceleration algorithms that employ pre-integrated classification. Our new strategy can achieve an optimized balance between image quality and classification speed. Next, the RPI algorithm is used with opacity adjustment technique to effectively remove the “striping” artifacts on the clipping plane caused by the nonuniform integration length. Furthermore, we present techniques for multiple transfer function (TF) based anatomical feature enhancement and “keyhole” based endoscopic inner structure view. Finally, the algorithms are evaluated subjectively by radiologists and quantitatively compared using image power spectrum analysis.     

Derivation of Strictly Stable High Order Difference Approximations for Variable-Coefficient PDE

A new way of deriving strictly stable high order difference operators for partial differential equations (PDE) is demonstrated for the 1D convection diffusion equation with variable coefficients. The derivation is based on a diffusion term in conservative, i.e. self-adjoint, form. Fourth order accurate difference operators are constructed by mass lumping Galerkin finite element methods so that an explicit method is achieved. The analysis of the operators is confirmed by numerical tests. The operators can be extended to multi dimensions, as we demonstrate for a 2D example. The discretizations are also relevant for the Navier–Stokes equations and other initial boundary value problems that involve up to second derivatives with variable coefficients.     

A self‐applicable online partial evaluator for recursive flowchart languages

This paper describes a self‐applicable online partial evaluator for a flowchart language with recursive calls. Self‐application of the partial evaluator yields generating extensions that are as efficient as those reported in the literature for offline partial evaluation. This result is remarkable because it has been assumed that online partial evaluation techniques unavoidably lead to inefficient and overgeneralized generating extensions. The purpose of this paper is not to determine which kind of partial evaluation is better, but to show how the problem can be solved by recursive polyvariant specialization. The design of the self‐applicable online partial evaluator is based on a number of known techniques, but by combining them in a new way this result can be produced. The partial evaluator, its techniques, and its implementation are presented in full. Self‐application according to all three Futamura projections is demonstrated. The complete bootstrap of a compiler generator from a partial evaluator is also reported. Copyright © 2011 John Wiley & Sons, Ltd.     

Rainbow: A framework for analysing computer-mediated pedagogical debates

In this paper we present a framework for analysing when and how students engage in a specific form of interactive knowledge elaboration in CSCL environments: broadening and deepening understanding of a space of debate. The framework is termed “Rainbow,” as it comprises seven principal analytical categories, to each of which a colour is assigned, thus enabling informal visualisation by the analyst of the extent to which students are engaging in interaction relating to potential achievement of its pedagogical goal. The categories distinguish between activities that are part of the prescribed assignment and activities that are not, and between task-focused and non-task-focused activities. Activities focused on managing the interaction itself are distinguished from argumentative interaction. Notably, an operational definition of what it means to broaden and deepen understanding in this case is also provided here. The functional Rainbow analysis is complemented by an analysis of topics and subtopics that enables identification of one form of conceptual deepening of the question. In comparison with existing analysis techniques, Rainbow synthesises much of what is known into a single framework, with a broad theoretical base. The usability and educational relevance of the framework has been validated experimentally across a variety of collaborative learning tasks and communication media. Possible and actual extensions to the framework are discussed, with respect to additional CSCL tools, domains and tasks. The research reported here was carried out within the SCALE project (Internet-based intelligent tool to Support Collaborative Argumentation-based Learning in secondary schools, project n° IST-1999–10664, March 2001 – February 2004), funded by the European Community under the ‘Information Societies’ Technology’ (IST) Programme. Information on the project can be found at: , or