Moral Dilemmas and Nonmonotonic Logic
- John F. Horty
this paper is to establish some formal connections between deontic and nonmonotonic logics, and to suggest some ways in which the techniques developed in the study of nonmonotonic reasoning and the issues confronted there might help to illuminate deontic ideas. These two subjects have evolved within different disciplines. The field of deontic logic was developed by philosophers and legal theorists as a high level framework for describing valid patterns of normative reasoning. The study of nonmonotonic logic was initiated, much more recently, by researchers in artificial intelligence who felt that ordinary logical techniques could not be applied properly to a...
Modal Logics, Description Logics and Arithmetic Reasoning
- Hans Jürgen Ohlbach; Jana Koehler
We introduce mathematical programming and atomic decomposition as the basic modal (T-Box) inference techniques for a large class of modal and description logics. The class of description logics suitable for the proposed methods is strong on the arithmetical side. In particular there may be complex arithmetical conditions on sets of accessible worlds (role llers). The atomic decomposition technique can deal with set constructors for modal parameters (role terms) and parameter (role) hierarchies specied in full propositional logic. Besides the standard modal operators, a number of other constructors can be added in a relatively straightforward way. Examples are graded modalities (qualied...
Dynamic Updates of Non-Monotonic Knowledge Bases
- J. J. Alferes; J. A. Leite; L.M. Pereira; H. Przymusinska; T. C. Przymusinski
In this paper we investigate updates of knowledge bases represented by logic programs. In order to represent negative information, we use generalized logic programs which allow default negation not only in rule bodies but also in their heads.We start by introducing the notion of an update P \Phi U of one logic program P by another logic program U . Subsequently, we provide a precise semantic characterization of P \Phi U , and study some basic properties of program updates. In particular, we show that our update programs generalize the notion of interpretation update. We then extend this notion to...
Anchoring Symbols to Vision Data by Fuzzy Logic
- Silvia Coradeschi; Alessandro Saffiotti
Intelligent agents embedded in physical environments need the ability to connect, or anchor, the symbols used to perform abstract reasoning to the physical entities which these symbols refer to. Anchoring must rely on perceptual data which is inherently affected by uncertainty. We propose an anchoring technique based on the use of fuzzy sets to represent uncertainty, and of degree of subset-hood to compute the partial match between signatures of objects. We show examples where we use this technique to allow a deliberative system to reason about the objects (cars) observed by a vision system embarked in an unmanned helicopter, in...
Rapid Gate Matching with Don't Cares
- A. -m. Trullemans; Q. Zhang
Ending the logic synthesis, the technology mapping step maps the Boolean function on physical cells. This itep is based on a matching check, which complexity depends on the number of library cell inputs, and increases if don't cares are considered. The method presented here is based on fault analysis. Using a structural equivalent of the cell, it allows to prune dramatically the design space, and derives at the same time the input phase. The experimental results show a real improvement in CPU time compared to ROBDD based Boolean matching, and are promising to handle complex cells. 1 Introduction The technology...
A Space Efficient Engine for Subsumption-Based Tabled Evaluation of Logic Programs
- Ernie Johnson; C. R. Ramakrishnan; I.V. Ramakrishnan; Prasad Rao
Tabled resolution methods increase the declarativeness and efficiency of logic programs through the sharing of answer computations. In variant-based tabled logic programming systems, answer computations are shared only between calls that are identical modulo variable renaming. Subsumption-based tabling can yield superior performance by sharing answer computations between a more general (subsuming) call and specific (subsumed) calls. But realizing this potential in practice requires the capability to efficiently index into dynamic sets of terms. In an earlier work, we proposed a data structure called Dynamic Threaded Sequential Automata (DTSA) to tackle this problem. By retrieving answers from a table one at...
Higher Order Generalization
- Jianguo Lu; Masateru Harao; Masami Hagiya
Generalization is a fundamental operation of inductive inference. While first order syntactic generalization (anti-unification) is well understood, its various extensions are needed in applications. This paper discusses syntactic higher order generalization in a higher order language 2. Based on the application ordering, we proved the least general generalization exists and is unique up to renaming. An algorithm to compute the least general generalization is presented. Keywords: higher order logic, unification, anti-unification, generalization. 1 Introduction The meaning of the word generalization is so general that we can find its occurrences in almost every area of study. In computer science, especially in...
Modelling Combinatorial Problems for CLP(FD+R)
- Henk Vandecasteele; Robert Rodosek
The paper presents results of modelling and solving a large industrial combinatorial problem with Constraint Logic Programming (CLP) in cooperation with Linear Programming (LP). The problem at hand is scheduling the maintenance of the power units in the power plants of Flanders. Using finite domain solvers ROPE [VDS94] and SICStus [Swe97] we were never able to derive an optimal solution. Most of constraints used in the model are linear inequations over integer variables. A number of experiments have been done at IC-Parc by running the Finite Domain solver in ECLiPSe [Eur98] using CPLEX to work on the linear constraints. Unfortunately,...
A Solution To A Problem Of Popper
- Krysia Broda; Marcello D'Agostino; Marco Mondadori
Popper's logical systems were an attempt to "reform the teaching of elementary logic", but were regarded by their own author as "bad and ill-fated". However, the problem raised by Popper was, and still is, a real one. In fact we show that the popular approaches in terms of natural deduction and analytic tableaux are unsatisfactory. Then we present a system of classical logic which combines the virtues of both and can be generalized to a wide range of non-classical logics.
The Relative Complement Problem for Higher-Order Patterns
- Alberto Momigliano; Frank Pfenning
We address the problem of complementing higher-order patterns without repetitions of free variables. Differently from the first-order case, the complement of a pattern cannot, in general, be described by a pattern, or even by a finite set of patterns. We therefore generalize the simply-typed -calculus to include an internal notion of strict function so that we can directly express that a term must depend on a given variable. We show that, in this more expressive calculus, finite sets of patterns without repeated variables are closed under complement and unification. Our principal application is the transformational approach to negation in higher-order...
Constraint Logic Programming - Status and Prospects
- Mark Wallace; William Penney
this paper, the CLP framework suuports a close cooperation between the algorithms in a way that is not supported, for example, when a set of packages are glued together by the underlying operating system. Constraints programming has been successfully applied for solving complex industrial problems in areas such as planning, transportation, scheduling and resource allocation: but applications are the subject of the third section. 2.2 Constraints Programming Example
Accelerating Gate Matching in the Mapping Step Using Don't Cares
- Anne-marie Trullemans; Ricardo Dos Santos Ferreira; Zhang Qinhai
At the end of the logic synthesis, the technology mapping maps the Boolean function on physical cells. This step is based on a matching check, which complexity depends on the number of library cell inputs, and increases if don't cares are considered. We present a method based on fault analysis techniques, which uses a structural equivalent of the cell. This method allows to prune dramatically the design space, and directly derives the input phase. The experimental results show a gain of 2 to 3 orders of magnitude relative to the conventional ones, and behaves almost linearly with the complexity. Keywords...
Using Reconfigurable Computing Techniques to Accelerate Problems in the CAD Domain: A Case Study with Boolean Satisfiability
- Peixin Zhong; Pranav Ashar; Sharad Malik; Margaret Martonosi
The Boolean satisfiability problem lies at the core of several CAD applications, including automatic test pattern generation and logic synthesis. This paper describes and evaluates an approach for accelerating Boolean satisfiability using configurable hardware. Our approach harnesses the increasing speed and capacity of field-programmable gate arrays by tailoring the SAT-solver circuit to the particular formula being solved. This input-specific technique gets high performance due both to (i) a direct mapping of Boolean operations to logic gates, and (ii) large amounts of fine-grain parallelism in the implication processing. Overall, these strategies yields impressive speedups (?200X in many cases) compared to current...
Refinement-Based Planning As Satisfiability
- Amol D. Mali; Subbarao Kambhampati
It has been shown recently that planning problems are easier to solve when they are cast as model finding problems. Some schemes for automated generation of the encodings of the planning problems in propositional logic have been designed. However these schemes lack several of the refinements that traditional split & prune type planners do. We show that it is possible to transfer these refinements into the encodings. Since no single encoding has been shown to have the smallest size and the best performance, it is necessary to know what the space of the encodings is. Knowing this space makes a...
Automata Theory on Trees and Partial Orders
- Wolfgang Thomas
. The paper reviews recent results which aim at generalizing finite automata theory from words and trees to labelled partial orders (presented as labelled directed acyclic graphs), with an emphasis on logical aspects. As an important type of labelled partial order we consider pictures (two-dimensional words). Graph acceptors and their specialization for pictures, "tiling systems", are presented, and their equivalence to existential monadic second-order logic is reviewed. Other restricted versions of graph acceptors are discussed, and an intuitive exposition of the recently established monadic quantifier alternation hierarchy over graphs is given. 1 Introduction The computational model of finite automaton ows...
Bias Field Estimation and Adaptive Segmentation of MRI Data Using a Modified Fuzzy C-Means Algorithm
- M. N. Ahmed; S. M. Yamany; A. A. Farag; T. Moriarty
In this paper, we present a novel algorithm for adaptive fuzzy segmentation of MRI data and estimation of intensity inhomogeneities using fuzzy logic. MRI intensity inhomogeneities can be attributed to imperfections in the RF coils or some problems associated with the acquisition sequences. The result is a slowly-varying shading artifact over the image that can produce errors with conventional intensity-based classification. Our algorithm is formulated by modifying the objective function of the standard fuzzy c-means (FCM) algorithm to compensate for such inhomogeneities and to allow the labeling of a pixel (voxel) to be influenced by the labels in its immediate...
CLP(SC): Implementation and Efficiency Considerations
- Jeffrey S. Foster
CLP(SC) is a constraint logic programming language over set constraints proposed by Kozen . In this paper, we describe a complete C++ implementation of CLP(SC). We describe the data structures used to represent systems of set constraints and an efficient algorithm, a modification of one given in , for unifying constraints. In addition, we investigate two further techniques for increasing efficiency: keeping track of variable equalities and doing PROLOGstyle unification. 1 Introduction A set constraint is an inclusion or equality between two expressions representing sets of ground terms over a finite alphabet. CLP(SC) is a constraint logic programming language over...
Automatic Temporal Verification of Communicating Processes
- A. Prasad Sistla; Lenore D. Zuck
In this paper, we present a formal framework to automatically verify temporal properties of communicating processes. In this framework, processes are modeled as automata with actions while the communication channels are modeled by the set of traces permitted by them. We present a general proof rule that allows one to deduce properties of such systems from the properties of individual processes and the theories of the underlying communication systems. We show how this rule can be applied for different cases when the message channels are FIFO or unordered buffers, and the properties are specified in Restricted Temporal Logic or in...
- P. Dell'Acqua; L. M. Pereira
this paper we propose a combination of the dynamic logic programming paradigm and (a version of) KS-agents. In the resulting framework rational, reactive agents can dynamically change their own knowledge bases as well as their own goals. In particular, at every iteration of (a version of) the observethink -act cycle, the agent can make observations and learn new facts and new rules from the environment, and then it can update its knowledge accordingly. The agent can also receive a piece of information that contrasts with its knowledge. To solve eventual cases of contradiction within the theory of an agent, techniques...
Combining Graph Transformations with Temporal Logic (Extended Abstract)
- Fabio Gadducci; Reiko Heckel; Manuel Koch
this paper we aim at formally combining it with graph transformations, by developing an adequate, graph-based semantics for propositional temporal logic. Thus we will be able to express within the formalism of graph transformations both static and dynamic properties, as well as to take advantage of many results already developed in the area of temporal logic, regarding e.g. verification, analysis, etc. Besides a set of atomic propositions and the usual non-temporal operators like disjunction or negation, temporal formulas additionally contain temporal operators like sometimes/eventually