[<Nested, <TWPA]

[<Nested]

[<Nested]

A formula from monadic second-order (MSO) logic can be used to specify a binary relation on the set of nodes of a tree. It is proved that, equivalently, such a relation can be computed by a finite-state tree-walking automaton, provided the automaton can test MSO properties of the nodes of the tree. For graphs, if a binary relation on the nodes of a graph can be computed by a finite-state graph-walking automaton, then it can be specified by an MSO formula, but, in general, not vice versa.
[<PODS, <TWPA]

http://dspace.mit.edu/handle/1721.1/6142 [<Nested, <TWPA]

http://doi.ieeecomputersociety.org/10.1109/SFCS.1978.30 [<Nested, <TWPA]

Tree-walking automata are a natural sequential model for recognizing languages of finite trees. Such automata walk around the tree and may decide in the end to accept it. It is shown that deterministic tree-walking automata are weaker than nondeterministic tree-walking automata.
[>TWPA, Trips, <Nested]

Tree-walking automata are a natural sequential model for recognizing tree languages. Every tree language recognized by a tree-walking automaton is regular. In this paper, we present a tree language which is regular but not recognized by any (nondeterministic) tree-walking automaton. This settles a conjecture of Engelfriet, Hoogeboom and Van Best. Moreover, the separating tree language is definable already in first-order logic over a signature containing the left-son, right-son and ancestor relations.
[<Nested]

Two variants of pebble tree-walking automata on binary trees are considered that were introduced in the literature. It is shown that for each number of pebbles, the two models have the same expressive power both in the deterministic case and in the nondeterministic case. Furthermore, nondeterministic (resp. deterministic) tree-walking automata with n + 1 pebbles can recognize more languages than those with n pebbles. Moreover, there is a regular tree language that is not recognized by any tree-walking automaton with pebbles. As a consequence, FO+posTC is strictly included in MSO over trees.
[>TWPA, >Nested, >Trips] [<PODS]

[<Nested]

[<Nested, <PODS]

[<Nested, <TWPA]

[<Nested]

[<Nested, <PODS, <TWPA]

[<Nested]

[<Nested, <TWPA]

The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these treewalking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages.
[=TWPA][<PODS]

String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure. Here we elaborate this result, and match the number of heads to the arity of the transitive closure. More precisely, first-order logic with k-ary deterministic transitive closure has the same power as deterministic automata walking on their input with k heads, additionally using a finite set of nested pebbles. This result is valid for strings, ordered 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. For nondeterministic automata, the logic is restricted to positive occurrences of transitive closure. The special case of k=1 for trees, shows that single-head deterministic tree-walking automata with nested pebbles are characterized by first-order logic with unary deterministic transitive closure. This refines our earlier result that placed these automata between first-order and monadic second-order logic on trees.
[=Nested]

Two-way finite state transducers are considered with a fixed number of pebbles, of which the life times are nested. In the deterministic case, the transductions computed by such pebble transducers are closed under composition, and they can be realized by the composition of one-pebble transducers. The ranges of the k-pebble transducers form a hierarchy with respect to k, their finiteness problem is decidable, and they can be generated by compositions of k macro tree transducers. Related results hold in the nondeterministic case.

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The 0-pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.
[>TWPA, <Nested, <PODS]

The macro tree transducer can be considered as a system of recursive function procedures with parameters, where the recursion is on a tree (e.g., the syntax tree of a program). We investigate characterizations of the class of tree (tree-to-string) translations which is induced by macro tree transducers (macro tree-to-string transducers, respectively). For this purpose we define several pushdown machines of which the control is recursive without parameters, or even iterative, and which work on a generalized pushdown as storage. Because of the relevance for semantics of programming languages, we stress (besides the nondeterministic case) the study of machines for the total deterministic macro tree(-to-string) transducer, which translates every input tree into exactly one output tree (string, respectively). Finally, we characterize the n-fold composition of total deterministic macro tree transducers by recursive pushdown machines with an iterated pushdown as storage, which is a pushdown of pushdowns of ... of pushdowns.
[<PODS]

[<Nested, <TWPA]

[=Trips, <Nested, <PODS, <TWPA]

[<Nested]

[<PODS]

[<Nested]

[<TWPA]

[<TWPA]

[<Nested]

Two-way and multi-pebble automata are considered (the latter appropriately restricted to accept only regular languages), and enriched with additional features, such as nondeterminism and concurrency. We investigate the succinctness of such machines, and the extent to which this succinctness carries over to make the reasoning problem in propositional dynamic logic more difficult. The two main results establish that each additional pebble provides inherent exponential power on both fronts.
[<Nested, <TWPA]

There are two main paradigms for querying semi structured data: regular path queries and XPath. The aim of this paper is to provide a synthesis between these two. This synthesis is given by a small addition to tree walk automata and the corresponding caterpillar expressions. These are evaluated on unranked finite sibling-ordered trees. At the expression level we add an operator whose meaning is intersection with the identity relation. This language can express every first-order definable relation and its expressive power is characterized by pebble tree walk automata that cannot inspect pebbles. We also define an expansion of the caterpillar expressions whose expressive power is characterized by ordinary pebble tree walk automata. Combining results from Bloem-Engelfriet and Gottlob-Koch, we also define an XPath like query language which is complete for all MSO definable binary relations.
[>TWPA, Trips] [<Nested, <PODS]

[<PODS]

[<PODS]

[<Nested]

[<Nested]

[<Nested]

[<Nested]

[<Nested]

[<Nested]

[<Nested]

[<Nested]

[<PODS]

[<Nested, <TWPA]

[<Nested]

[<Nested]

[<Nested]

[<PODS]

[<PODS]

[<PODS]

[<PODS]

[<Nested]

[<Nested]

[<Nested]

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.
[Trips] [<Nested, <PODS]

[<PODS]

[<Nested]

We consider various kinds of deterministic tree-walking automata, with and without pebbles, over ranked and unranked trees. For each such kind of automata we show that there is an equivalent one which never loops. The main consequence of this result is the closure under complementation of the various types of automata we consider with a focus on the number of pebbles used in order to complement the automata.
[Trips, >Nested] [<Nested]

[<Nested]

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class of TWAs that can simulate first-order logic (FO) and is capable of expressing properties not definable in FO extended with regular path expressions; the latter logic being a valid abstraction of current query languages for XML and semistructured data.
[>TWPA, private communication, Trips] [<Nested, <PODS]

[<Nested]

We survey some recent developments in the broad area of automata and logic which are motivated by the advent of XML. In particular, we consider unranked tree automata, tree-walking automata, and automata over infinite alphabets. We focus on their connection with logic and on questions imposed by XML.
[<Nested]

[<Nested]

XML documents conceptually are not trees, but forests. Therefore, we extend the concept of macro tree transducers (mtt's) to a transformation formalism of forests, macro forest transducers (mft's). We show that mft's form a strict superset of mtt's operating on forests (represented as binary trees). On the other hand, the transformation of every mft can be simulated by the composition of two mtt's. Although macro forest transducers are more powerful, the complexity of inverse type inference, i.e., computing the pre-image of a recognizable language, is almost the same as for tree transducers.
[<PODS]

[<Nested]

[<Nested]

Also in: Sequential Machines: Selected Papers (E.F. Moore, ed.), Addison-Wesley, Reading, MA, 1964, pp. 63–91. http://www.research.ibm.com/journal/rd/032/ibmrd0302C.pdf [<Nested, <TWPA]

An off-line, memory-restricted Turing machine model, the marking automaton (MA) is presented here as a device strictly intermediate between finite and linear bounded automata. Although much more restricted than the latter, MA are shown capable of recognizing, deterministically, various kinds of context-free (CF) languages and an important related class, as well as such non-CF languages as xx. It is not known whether all CF languages are recognizable by MA; however, among the familiar subclasses shown to consist of MA recognizable languages are the Dyck, standard, and bounded CF languages. More importantly, each member of the class of structured CF languages, consisting of all structural descriptions (Phrase-markers) of the sentences in a CF language, is shown to be MA recognizable. The closure of the MA recognizable languages under various set (e.g., boolean) operations is revealed in the proof that all bounded CF languages are MA recognizable.
[<Nested]

[<Nested]

[<Nested]

We consider tree-walking automata using k pebbles. The pebbles are either strong (can be lifted from anywhere) or weak (can be lifted only when the automaton is on it). For each k, we give the precise complexities of the problems of emptiness and inclusion of tree-walking automata using k pebbles.
[>TWPA, >Nested, >Trips]

[<PODS]

Automata play an important role for the theoretical foundations of XML data management, but also in tools for various XML processing tasks. This survey article aims to give an overview of fundamental properties of the different kinds of automata used in this area and to relate them to the four key aspects of XML processing: schemas, navigation, querying and transformation.
[>Nested, >TWPA, >Trips] [<Nested]

Also in: Sequential Machines: Selected Papers (E.F. Moore, ed.), Addison-Wesley, Reading, MA, 1964, pp. 92–97. http://www.research.ibm.com/journal/rd/032/ibmrd0302P.pdf
[<Nested, TWPA]

[<Nested, <TWPA]

[<Nested, <PODS]

[<Nested]

We consider the navigational core of XPath, extended with two operators: the Kleene star for taking the transitive closure of path expressions, and a subtree relativisation operator, allowing one to restrict attention to a specific subtree while evaluating a subexpression. We show that the expressive power of this XPath dialect equals that of FO(MTC), first order logic extended with monadic transitive closure. We also give a characterization in terms of nested tree-walking automata. Using the latter we then proceed to show that the language is strictly less expressive than MSO. This solves an open question about the relative expressive power of FO(MTC) and MSO on trees. We also investigate the complexity for our XPath dialect. We show that query evaluation be done in polynomial time (combined complexity), but that satisfiability and query containment (as well as emptiness for our automaton model) are 2ExpTime-complete (it is ExpTime-complete for Core XPath). [>Nested, Invisible]

[<Nested, <PODS]

[<Nested, <PODS, <TWPA]

[<Nested, <TWPA]

(in Russian) English translation: American Mathematical Society Translations, Series 2, 59, 23–55, 1966. [<Nested]

[<TWPA]

What does the age of the Web mean for database theory? It is a challenge and an opportunity, an exciting journey of rediscovery. These are some notes from the road. [>Trips][<Nested]

[<Nested]