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.
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.
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.
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.
30357320
The Power to Two-Way Deterministic Checking Stack Automata
Abstract It is well known that nondeterministic two-way checking stack automata recognize NSPACE( n ). We show that deterministic two-way checking stack automata have the same power as deterministic two-way two-head finite automata. The easy proof is based on the closure under inverse deterministic two-way GSM mappings of the deterministic two-way two-head finite automaton languages.
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.
3010463
Equality Languages and Fixed Point Languages
This paper considers equality languages and fixed-point languages of homomorphisms and deterministic gsm mappings. It provides some basic properties of these classes of languages. We introduce a new subclass of dgsm mappings, the so-called symmetric dgsm mappings. We prove that (unlike for arbitrary dgsm mappings) their fixed-point languages are regular but not effectively obtainable. This result has various consequences. In particular we strengthen a result from Ehrenfeucht, A., and Rozenberg, G. [(1978), Theor. Comp. Sci. 7, 169–184] by pointing out a class of homomorphisms which includes elementary homomorphisms but still has regular equality languages. Also we show that the result from Herman, G. T., and Walker, A. [(1976), Theor. Comp. Sci. 2, 115–130] that fixed-point languages of DIL mappings are regular, is not effective.
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.
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.