27165586
A new natural structural congruence in the pi-calculus with replication
Abstract.In the $\pi$-calculus with replication, a new structural congruence called “middle” congruence is investigated: a notion of structural equivalence of processes in which replication of a process is viewed as a potential rather than an actual infinite number of copies of the process, in the sense that copies are spawned at need rather than produced all at once. It is slightly weaker than standard congruence (which is also of the potential type) but stronger than the extended congruence investigated before by the authors (which is of the actual type). It is shown that middle congruence has the same desirable properties as extended congruence: it is decidable and it has a concrete multiset semantics. Thus, these properties do not depend on the distinction between potential and actual replication.
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.
47462408
The equivalence problem for deterministic MSO tree transducers is decidable
It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
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.
14239266
The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable
It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
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.
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.
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.
41515310
Minimal Temporal Epistemic Logic
495864
Infinitary Default Logic for Specification of Nonmonotonic Reasoning
In this paper we study constructions leading to the formation of belief sets by agents. We focus on the situation when possible belief sets are built incrementally in stages. We call an infinite sequence of theories that represents such a process a reasoning trace. A set of reasoning traces describing all possible reasoning scenarios for the agent is called a reasoning frame. Default logic by Reiter is not powerful enough to represent reasoning frames. In the paper we introduce a generalization of default logic of Reiter by allowing infinite sets of justifications. We call this formalism infinitary default logic. In the main result of the paper we show that every reasoning frame can be represented by an infinitary default theory. A similar representability result for antichains of theories (belief frames) is also presented.
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.