A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula of monadic second-order logic. The latter means that the formula defines a set of graphs, in the usual way, such that each “computation graph” in that set determines a pair consisting of an input graph and an output graph.

Two-way finite state transducers are considered that use a finite number of pebbles, of which the life times must be nested. For every nondeterministic transducer that realizes a partial function, an equivalent deterministic transducer can be constructed. The composition of two deterministic transducers can be realized by one such transducer with a minimal number of 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.

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.

The first main result is that if a macro tree translation is of linear size increase, i.e., if the size of every output tree is linearly bounded by the size of the corresponding input tree, then the translation is MSO definable (i.e., definable in monadic second-order logic). This gives a new characterization of the MSO definable tree translations in terms of macro tree transducers: they are exactly the macro tree translations of linear size increase. The second main result is that given a macro tree transducer, it can be decided whether or not its translation is MSO definable, and if it is, then an equivalent MSO transducer can be constructed. Similar results hold for attribute grammars, which define a subclass of the macro tree translations.

We extend a classic result of Büchi, Elgot, and Trakhtenbrot: MSO definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (MSO) logic, are exactly those realized by deterministic two-way finite-state transducers, i.e., finite-state automata with a two-way input tape and a one-way output tape. Consequently, the equivalence of two mso definable string transductions is decidable. In the nondeterministic case however, MSO definable string tranductions, i.e., binary relations on strings that are mso definable by an interpretation with parameters, are incomparable to those realized by nondeterministic two-way finite-state transducers. This is a motivation to look for another machine model, and we show that both classes of MSO definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite-state transducers that are allowed to rewrite their input tape, but may visit each position of their input only a bounded number of times.

We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages and NTS languages.

Theoretical results are presented on multi-pass (both left-to-right and alternating), multi-sweep, and multi-visit attribute grammars. For each of these, a pure type and a simple type are distinguished: The pure attribute grammars are defined by nondeterministic attribute evaluators, and the simple ones by the corresponding (usual) deterministic evaluators. The time complexity of deciding membership in these classes of attribute grammars is studied. In general, this is harder for the pure classes than for the simple ones, for which it is either polynomial or NP-complete. The expressive power of the eight classes is compared by studying the translations they can compute. It is shown that sweeps are more powerful than passes, and visits are more powerful than sweeps.

A string-valued attribute grammar (SAG) has a semantic domain of strings over some alphabet, with concatenation as basic operation. It is shown that the output language (i.e., the range of the translation) of a SAG is log-space reducible to a context-free language.

An iterated pushdown is a pushdown of pushdowns of ... of pushdowns. An iterated exponential function is 2 to the 2 to the ... to the 2 to some polynomial. The main result is that nondeterministic 2-way and multi-head iterated pushdown automata characterize deterministic iterated exponential time complexity classes. This is proved by investigating both nondeterministic and alternating auxiliary iterated pushdown automata, for which similar characterization results are given. In particular it is shown that alternation corresponds to one more iteration of pushdowns. These results are applied to the 1-way iterated pushdown automata: (1) they form a proper hierarchy with respect to the number of iterations, (2) their emptiness problem is complete in deterministic iterated exponential time.

Fixed point languages and equality languages of homomorphisms and dgsm mappings are considered.Some basic properties of these classes of languages are proved, and it is shown how to use them to represent recursively enumerable sets.In particular, very simple languages are introduced which play the same role for the class of recursively enumerable languages that the Dyck languages play for the class of context-free languages.Finally, a new type of acceptor for defining equality languages is introduced.

AnSTV.ACT.A new class of generalized one-way stack automata, called s-pd machines, is mvestlgated The machines are obtained by augmenting a stack automaton with a pushdown store, whose bottom is attached to the top of the stack and whose top follows the movements of the stack-pointer into the stack.Motivations for the modal include a possible protocol for macro expansion with intermittent parameter evaluatton.The languages recogmzed by these machmes are characterized by a natural class of grammars, vlz, the 91ass of OI macro grammars with set-parameters and nonnested function calls (the "extended basic" or EB macro grammars) If the stack is required to be nonerasing or checking, then a useful machine characterizatton for the ETOL languages is obtained, together with the known characterization of this family by means of extended "linear" basic or [~LB macro grammars.It follows that the nonerasmg one-way stack languages are (strictly) included m ETOL.It is proved that the family of unrestricted one-way stack languages and ETOL are incomparable, as are the general OI macro languages and the yields of ranges of topdown tree transducers.It follows that ETOL is strictly included m the family of EB macro languages (which, m turn, is strxctly included in the famdy of indexed languages) Certain determuustic restrictions of s-pd machines lead to machine models for famlhes of nonextended macro languages, vlz, for Ftscher's original linear basic macro (i e, EDTOL) and basle macro languages.

This extended abstract is a condensed version of the results presented in two technical reports ([16] and [13]). In [16] a systematic treatment of the relationships between parallel rewriting systems (top-down tree transducer, ETOL system) and two-way machines (2-way gsm, tree-walking automaton, checking stack automaton) is given. Particular attention is paid to the effect of restricting the copying power of these devices. In [13] the results of [16] are employed to show that the iteration of nondeterministic top-down tree transducers, of nondeterministic 2-way gsm's and of control on ETOL systems each gives rise to a proper hierarchy.