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.
34555418
Nonmonotonic Reasoning with Multiple Belief Sets
In the present paper we introduce nonmonotonic belief set operators and selection operators to formalize and to analyze multiple belief sets in an abstract setting. We define and investigate formal properties of belief set operators as absorption, congruence, supradeductivity and weak belief monotony. Furthermore, it is shown that for each belief set operator satisfying strong belief cumulativity there exists a largest monotonic logic underlying it, thus generalizing a result for nonmonotonic inference operations. Finally, we study abstract properties of selective inference operations connected to belief set operators and which are used to choose one of the possible views.
41515310
Minimal Temporal Epistemic Logic
17644062
Specification of nonmonotonic reasoning
ABSTRACT Two levels of description of nonmonotonic reasoning are distinguished. For these levels semantical formalizations are given. The first level is defined semantically by the notion of belief state frame, the second level by the notion of reasoning frame. We introduce two specification languages to describe nonmonotonic reasoning at each of the levels: (1) a specification language for level 1, with formal semantics based on belief state frames, (2) a fragment of infinitary temporal logic as a general specification language for level 2, with formal semantics based on reasoning frames. In our framework every level 2 description can be abstracted to level 1, and for every level 1 description there are level 2 descriptions which are a specialization of it.
9865419
A compositional reasoning system for executing nonmonotonic theories of reasoning
In this paper the framework DESIRE for the design of compositional reasoning systems and multi-agent systems was applied to build a generic nonmonotonic reasoning system. The outcome is a general reasoning system that can be used to model different nonmonotonic reasoning formalisms and that can be executed by a generic execution mechanism. The main advantages of using DESIRE (for example, compared to a direct implementation in a programming language such as PROLOG) are that the design is generic and has a transparent compositional structure, and the explicit declarative specification of both the static and dynamic aspects of the nonmonotonic reasoning processes, including their control. © 2003 Wiley Periodicals, Inc.
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.
17739753
Finite Languages for the Representation of Finite Graphs
We introduce a new way of specifying graphs: through languages, i.e., sets of strings. The strings of a given (finite, prefix-free) language represent the vertices of the graph; whether or not there is an edge between the vertices represented by two strings is determined by the pair of symbols at the first position in these strings where they differ. With this new, “positional” or lexicographic, method, classical and well-understood ways of specifying languages can now be used to specify graphs, in a compact way; thus, (small) finite automata can be used to specify (large) graphs. Since (prefix-free) languages can be viewed as trees, our method generalizes the hierarchical specification of particular types of graphs such as cographs and VSP graphs. Our main results demonstrate an intrinsic relationship between the fundamental operations of language concatenation and graph substitution.
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.
17560850
Clique-Width for Four-Vertex Forbidden Subgraphs
Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. The notion of clique-width extends the one of treewidth, since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.
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.
17757601
A Kleene characterization of computability
The recursively enumerable binary relations are the smallest class containing all singleton relations and closed under union, concatenation, Kleene star, composition, and transitive closure.