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.
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.
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.
15984778
XML transformation by tree-walking transducers with invisible pebbles
The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of "invisible" pebbles (as opposed to the usual ("visible" ones). The resulting pebble tree automata recognize the regular tree languages (i.e., can validate all generalized DTD's) and hence can find all matches of MSO definable n-ary patterns. Moreover, when viewed as a navigational device, they lead to an XPath-like formalism that has a path expression for every MSO definable binary pattern. The resulting pebbletree transducers can apply arbitrary MSO definable tests to (the observable part of) their configurations, they (still) have a decidable typechecking problem, and they can model the recursion mechanism of XSLT. The time complexity ofthe typechecking problem for conjunctive queries that use MSO definable binary patterns can often be reduced through the use of invisible pebbles.
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.
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.