9686977
A Temporal Model Theory for Default Logic
By explicitly identifying the temporal aspect of a default rule as it is used in a reasoning process, it is argued that a natural semantic theory of Reiter's default logic is a temporal one. To be able to accommodate the lack of complete knowledge at any point in time, the temporal models should be partial models. A temporal partial logic is introduced, and it is shown that this logic can provide semantics for Reiter's default logic.
35737768
A Compositional Reasoning System for Executing Nonmonotonic Theories of Reasoning
In this paper a system was developed using the compositional modelling environment DESIRE (framework for DEsign and Specification of Interacting REasoning components). This environment for the development of compositional reasoning systems and multi-agent systems has been succesfully used to design various types of reasoning systems and multi-agent systems and applications in particular domains. The DESIRE sofware environment offers a graphical editor, an implementation generator and an execution environment to execute specifications automatically.
1862248
Monotonicity and Persistence in Preferential Logics
An important characteristic of many logics for Artificial Intelligence is their nonmonotonicity. This means that adding a formula to the premises can invalidate some of the consequences. There may, however, exist formulae that can always be safely added to the premises without destroying any of the consequences: we say they respect monotonicity. Also, there may be formulae that, when they are a consequence, can not be invalidated when adding any formula to the premises: we call them conservative. We study these two classes of formulae for preferential logics, and show that they are closely linked to the formulae whose truth-value is preserved along the (preferential) ordering. We will consider some preferential logics for illustration, and prove syntactic characterization results for them. The results in this paper may improve the efficiency of theorem provers for preferential logics.
7110538
Only Persistence Makes Nonmonotonicity Monotonous
An important characteristic of many logics for artificial intelligence is that they are nonmonotonic. This means that adding a formula to the premises can destroy some of the consequences. There may exist formulae that can always be safely added to the premises without destroying any of the consequences: they respect monotonicity. We consider three preferential logics for which we analyze the class of formulae which respect monotonicity. For each of the three logics we show that this class is equal to the class of formulae preserved under going to more preferred models, and we provide syntactic characterizations of these classes.
32078047
Temporal Theories of Reasoning
In this paper we describe a general way of formalizing reasoning behaviour. Such a behaviour may be described by all the patterns which are valid for the behaviour. A pattern can be seen as a sequence of information states which describe what has been derived at each time point. A transition from an information state at a point in time to the state at the (or a) next time point is induced by one or more inference steps. We choose to model the information states by partial models and the patterns either by linear time or branching time temporal models. Using temporal logic one can define theories and look at all models of that theory. For a number of examples of reasoning behaviour we have been able to define temporal theories such that its (minimal) models correspond to the valid patterns of the behaviour. These theories prescribe that the inference steps which are possible, are "executed" in the temporal model. The examples indicate that partial temporal logic is a powerful means of describing and formalizing complex reasoning patterns, as the dynamic aspects of reasoning systems are integrated into the static ones in a clear fashion.
40535872
Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic
Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence.
34994233
Iterated deterministic substitution
SummaryDeterministic substitution of languages means substituting the same word (from a given language) for all occurrences of a symbol. For an arbitrary family K of languages the notion of deterministic K-iteration grammar is introduced, which is essentially the iteration of a finite number of deterministic substitutions of languages from K. The families of languages generated by these grammars are investigated.
5981521
Nested Pebbles and Transitive Closure
First-order logic with k-ary deterministic transitive closure has the same power as two-way k-head deterministic automata that use a finite set of nested pebbles. This result is valid for strings, ranked trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Other examples of such families are grids, toruses, and rectangular mazes.
11003400
Passes and Paths of Attributive Grammars
An attribute grammar is pure (left-to-right) multi-pass if a bounded number of left-to-right passes over the derivation tree suffice to compute all its attributes. There is no requirement, as for the usual multi-pass attribute grammars, that all occurrences of the same attribute are computed in the same pass. It is shown that the problem of determining whether an arbitrary attribute grammar is pure multipass, is of inherently exponential time complexity. For fixed k > 0, it can be decided in polynomial time whether an attribute grammar is pure k-pass. The proofs are based on a characterization of pure multi-pass attribute grammars in terms of paths through their dependency graphs. A general result on dependency paths of attribute grammars relates them to (finite-copying) top-down tree transducers. The formal power of k-pass attribute grammars increases with increasing k. Formally, multi-pass attribute grammars are less powerful than arbitrary attribute grammars.
13469765
Decidability of the Finiteness of Ranges of Tree Transductions
Abstract The finiteness of ranges of tree transductions is shown to be decidable for TBY + , the composition closure of macro tree transductions. Furthermore, TBY + definable sets and TBY + computable relations are considered, which are obtained by viewing a tree as an expression that denotes an element of a given algebra. A sufficient condition on the considered algebra is formulated under which the finiteness problem is decidable for TBY + definable sets and for the ranges of TBY + computable relations. The obtained result applies in particular to the class of string languages that can be defined by TBY + transductions via the yield mapping. This is a large class which is proved to form a substitution-closed full AFL.
15175574
Branching synchronization grammars with nested tables
A generalization of ET0L systems is introduced: grammars with branching synchronization and nested tables. The main result is that branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers. Based on this it is shown, e.g., that the family of generated string languages is a full principal AFL for each n.