Antoine Meyer
email: ameyer@liafa.jussieu.fr

Traces of term-automatic graphs

Introduction

In classical language theory, context-sensitive languages, one of the families of the Chomsky hierarchy [START_REF] Chomsky | On certain formal properties of grammars[END_REF], are defined as the languages generated by growing grammars. They were later characterised as the languages accepted by linearly space-bounded Turing machines [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF], i.e. Turing machines whose runs on any input word of length n use at most k • n work tape cells, for some constant k. In [START_REF] Latteux | Context-sensitive string languages and recognizable picture languages[END_REF], it was shown that context-sensitive languages also coincide with the languages accepted by bounded tiling systems.

In 2001, [START_REF] Morvan | Rational graphs trace context-sensitive languages[END_REF] provided yet another characterisation of this family as the set of path languages of rational graphs [START_REF] Morvan | On rational graphs[END_REF], i.e. infinite graphs whose vertices are words and whose sets of edges are defined by finite transducers. This result was later extended in [START_REF]The synchronized graphs trace the context-sensitive languages[END_REF] to the more restricted family of automatic graphs (Cf. [START_REF] Khoussainov | Automatic presentations of structures[END_REF]), and even to synchronous rational graphs when an infinite number of initial and final vertices are considered (see also [START_REF] Morvan | Families of automata characterizing context-sensitive languages[END_REF]). In a way, this provides a "forward", automata-based characterisation of context-sensitive languages, as opposed to linearly bounded machines which are essentially a twoway mechanism. To prove the inclusion of context-sensitive languages in the set of path languages of these families of graphs, these papers use a normal form for growing grammars, due to Penttonen [START_REF] Penttonen | One-sided and two-sided context in formal grammars[END_REF]. In [START_REF] Carayol | Context-sensitive languages, rational graphs and determinism[END_REF], these results were reformulated using simpler proof techniques based on tiling systems. This also allowed to investigate interesting sub-cases, in particular concerning deterministic context-sensitive languages or various sub-classes of rational graphs.

The aim of this work is to extend the results of [START_REF] Latteux | Context-sensitive string languages and recognizable picture languages[END_REF] and [START_REF] Carayol | Context-sensitive languages, rational graphs and determinism[END_REF] to the more general family ETIME of languages accepted by deterministic Turing machines working in time less than 2 O(n) , or equivalently by alternating linearly bounded machines. This family lies between context-sensitive and recursivelyenumerable languages in the Chomsky hierarchy. We obtain two new characterisations of ETIME, first as the languages accepted by arborescent tiling systems and second as the traces of infinite graphs defined by various classes of term transducers, namely term-synchronous and term-automatic (or tree-automatic) graphs [START_REF] Blumensath | Automatic structures[END_REF].

After recalling definitions and notations in Section 1, we introduce the notion of arborescent tiling systems in Section 2 and prove that they characterise ETIME. Finally, we extend previously mentioned proofs over rational graphs to the family of term-automatic graphs in Section 3.

Notations

Words, terms and trees

A word u over alphabet Σ can be seen as a tuple (a 1 , . . . , a n ) of elements of Σ, usually written a 1 . . . a n . Its i-th letter is denoted by u(i) = a i . The set of all words over Σ is written Σ * . The number of letters occurring in u is its length, written |u| (here |u| = n). The empty word is written ε. The concatenation of two words u = a 1 . . . Let F = n≥0 F n be a finite ranked alphabet, each F n being the set of symbols of F of arity n, and X be a finite set of variables disjoint from F (all sets F n are also disjoint). We denote the arity of a symbol f ∈ F by a(f ). Variables are considered of arity 0. The set of finite first-order terms on F with variables in X, written T (F, X), is the smallest set including X such that f ∈ F n ∧ t 1 , . . . , t n ∈ T (F, X) ⇒ f t 1 . . . t n ∈ T (F, X). Words can be seen as terms over a ranked alphabet whose symbols have arity exactly 1 and whose last symbol is a variable or a special constant. To improve readability, f t 1 . . . t n will sometimes be written f (t 1 , . . . , t n ).

A finite ordered tree t over a set of labels Σ is a mapping from a prefix-closed set dom(t) ⊆ N * into Σ. Elements of dom(t) are called positions, and for every p ∈ dom(t), t(p) is the label of the node at position p. The node at position ε is called the root of the tree, nodes at maximal positions (i.e. positions x such that ∄y = ε, xy ∈ dom(t)) are called leaves, other nodes are called internal.

Any term t over a ranked alphabet F and set of variables X can be represented as a finite ordered ranked tree, whose leaves are labelled with constants in F 0 or variables in X and whose internal nodes are labelled with symbols of arity equal to the number of children of that node. In that case, the domain of t, additionally to being prefix-closed, also has the following properties:

1. ∀p ∈ dom(t), t(p) ∈ F n≥1 =⇒ {j | pj ∈ dom(t)} = [1, n], 2. ∀p ∈ dom(t), t(p) ∈ F 0 ∪ X =⇒ {j | pj ∈ dom(t)} = ∅.
In such a tree, position pi with i ∈ N always denotes the i-th child of node p. Conversely, any finite ordered tree t labelled over Σ can be represented as a ranked tree t ′ , and hence as a term, by mapping each node label a to a set of symbols (a, n) in Σ × N, with a(a, n) = n, and by renumbering all positions such that dom(t ′ ) verifies the above properties. This will usually be left implicit.

A finite tree (or term) automaton is a tuple A = Q, F, q 0 , δ , where Q is a set of control states, F a ranked alphabet, q 0 the initial set and δ the set of transition rules of A of the form (q, f, q 1 , . . . , q n ) with a(f ) = n. A run of A over a tree t is a mapping ρ from dom(t) to Q such that ρ(ε) = q 0 and for all node u ∈ dom(t) of arity a(u) = n, (ρ(u), t(u), ρ(u1), . . . , ρ(un)) ∈ δ. If A has a valid run on t, we say that t is accepted by A. The set of trees accepted by a finite automaton is called its language, and all such languages are said to be regular.

Graphs

A labelled, directed and simple graph is a set G ⊆ V × Σ × V where Σ is a finite set of labels and V an arbitrary countable set. An element (s, a, t) of G is an edge of source s, target t and label a, and is written s

a → G t or simply s a → t if G
is understood. An edge with the same source and target is called a loop. The set of all sources and targets of a graph form its support V G , its elements are called vertices. A sequence of edges (s

1 a1 → t 1 , . . . , s k a k → t k ) with ∀i ∈ [2, k], s i = t i-1 is called a path. It is written s 1 u → t k
, where u = a 1 . . . a k is the corresponding path label. Vertex s 1 is called the origin of the path, t k its destination. A path is called a cycle if its origin and destination are the same vertex. The language, or set of traces of a labelled graph between two sets I and F of vertices is the set of all words w such that there exists a path labelled by w whose origin is in I and destination in F .

Turing machines

A Turing machine is a tuple M = Γ, Σ, Q, q 0 , F, δ where Σ is the input alphabet, Γ the tape or work alphabet (with Σ ⊆ Γ ), Q is a set of states among which q 0 is an initial state and F is a set of final states, and δ is a set of transition rules of the form pA → qBǫ where p, q ∈ Q, A, B ∈ Γ ∪ { } ( being a blank symbol not in Γ ) and ǫ ∈ {+, -}.

Configurations of M are denoted as words upv, where uv is the content of the work tape (where prefix and suffix blank symbols are omitted), p is the current control state and the head scans the cell containing the first letter of v. A transition d = pA → qBǫ is enabled on any configuration c of the form upAv, and yields a new configuration

d(c) = uBqv ′ (with v ′ = v if v = ε, or otherwise) if ǫ = + and u ′ qCBv (with u ′ C = u if u = ε or u ′ = ε and C = otherwise) if ǫ = -. If d is not enabled on c, then d(c) is left undefined.
An alternating Turing machine M is defined similarly, with the exception that rules are of the form d = pA → i∈[1,n] q i B i ǫ i . The alternation degree n of d is written a(d), by analogy with the notion of arity. For all i ≤ a(d), we write d i the non-alternating transition pA → q i B i ǫ i . A run of M on input word w is a tree whose root is labelled by configuration q 0 w, and such that the children of any node labelled by configuration c are labelled by c 1 , . . . , c n if and only if there exists a transition d ∈ δ enabled on c such that a(d) = n and ∀i ∈ [1, n], c i = d i (c). Such a run is successful if all its leaves are labelled by configurations whose control state is in F .

A Turing machine is linearly bounded if on every run the total work tape space it uses is at most proportional to the length of its input word. By standard coding techniques, it is sufficient to consider machines whose tape is limited to the cells initially containing the input word. This may be enforced by forbidding transition rules to rewrite the blank symbol . The languages of non-alternating linearly bounded machines form the complexity class SPACE(O(n)), which is equivalent to context-sensitive languages [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF]. Adding alternation, one obtains the more general class ASPACE(O(n)). By classical complexity results [START_REF] Chandra | Alternation[END_REF], it is also equivalent to the class DTIME(2 O(n) ), also called ETIME.

Arborescent tiling systems

To facilitate the proofs of our main results, this section provides an important technical tool, which was also central to some versions of the corresponding proofs on rational graphs and context-sensitive languages (Cf. [START_REF] Carayol | Context-sensitive languages, rational graphs and determinism[END_REF]).

Tiling systems were originally defined to recognise or specify picture languages, i.e. sets of two-dimensional words on finite alphabets [START_REF] Giammarresi | Handbook of Formal Languages, volume 3, chapter Two-dimensional languages[END_REF], called local picture languages. However, by only looking at the words contained in the first row of each picture of a local picture language, one obtains a context-sensitive language, and the converse is true : for any context-sensitive language there exists a local picture language (and a tiling system accepting it) whose set of upper frontiers is that language [START_REF] Latteux | Context-sensitive string languages and recognizable picture languages[END_REF].

In this section, we extend this result to an arborescent extension of tiling systems, and prove that this new formalism characterises precisely the class ETIME.

Definitions

Instead of planar pictures, we consider so-called arborescent pictures, which are to ordinary pictures what terms are to words.

Definition 1 (Arborescent picture). Let Γ be a finite alphabet, an arborescent picture p over Γ is a mapping from the set X × [1, m] to Γ , where X ⊆ N + * is a finite, prefix-closed set of sequences of positive integers (called positions in the framework of trees) and m is a positive integer called the width of p. The set dom(p) = X × [1, m] is the domain of p. The set of arborescent pictures over

X × [1, m] is written AP(X, m).
Like in the case of trees, we assume that X is not only prefix-closed but also left-closed, i.e. ∀i > 0, ui ∈ X =⇒ ∀j < i, uj ∈ X. For a given picture p ∈ AP(X, m), we write fr(p) the word w ∈ Γ m such that w(i) = p(ε, i), which we call the (upper) frontier of p.

Arborescent pictures of domain X × [1, m] are isomorphic to ordered trees of domain X with nodes labelled over the set Γ m . As such, if m = 1 they are isomorphic to Γ -labelled ordered trees. One can observe that any branch of an arborescent picture seen as a Γ m -labelled tree, as well as any arborescent picture whose set of positions X is a subset of 1 * , is an ordinary, planar picture.

Definition 2 (Sub-picture). For any arborescent picture p ∈ AP(X, m), the sub-picture

p ′ = p| x,i,Y,n of p at offset o = (x, i) with x ∈ X and i ∈ [0, m -1] is the arborescent picture of domain Y × [1, n] such that Y is prefix-and left-closed and ∀(y, j) ∈ Y × [1, n], (xy, i + j) ∈ X × [1, m] and p ′ (y, j) = p(xy, i + j).
We can now define arborescent tiling systems, which allow the specification of sets of arborescent pictures. Similarly to planar tiling systems, in order to be able to recognise meaningful sets of pictures, we first add a border or frame to each picture using a new symbol #.

Definition 3 (Framed picture). Let p be an arborescent picture of domain X × [1, m] over Γ and # ∈ Γ a new symbol, we define the #-framed picture p # as the picture of domain

X ′ × [1, m + 2] with X ′ = {ε} ∪ {1}X ∪ X ′′ and X ′′ = {1x1 | x ∈ X ∧ ∄y ∈ N, xy ∈ X} such that p # (ε, i) = # for all i ∈ [1, m + 2], p # (1x, 1) = # and p # (1x, m + 2) = # for all x ∈ X, p # (x, i) = # for all x ∈ X ′′ , i ∈ [1, m + 2], p # (1x, i + 1) = p(x, i) for all x ∈ X, i ∈ [1, m].
An arborescent tiling system is then defined as a set of tiling elements of width and height 2, which can then be combined to form larger framed pictures.

Definition 4 (Arborescent tiling system). An arborescent tiling system (or ATS) S is a triple (Γ, #, ∆), where Γ is a finite alphabet, # ∈ Γ a frame symbol and ∆ is a set of arborescent tiling elements (tiles Note that any tiling element d = (A, B, C, D) of arity n is isomorphic to an arborescent picture p d of domain X ×[1, 2], where X = {ε, 1, . . . , n} and p d (ε, 1), p d (ε, 2), p d (i, 1) and p d (i, 2) are respectively equal to A, B, C i and D i (for all i ∈ [1, n]). In general we do not distinguish p d from d and write simply d.

) in { Γ × Γ × Γ n × Γ n | n > 0} with Γ = Γ ∪ {#}.
Well-formed tiling systems should obey a certain number of restrictions over their set of tiles, regarding in particular the occurrences of the frame symbol # inside tiles. For all d = (A, B, C, D),

1. (A, B) = (#, #) =⇒ a(d) = 1 ∧ (C 1 , D 1 ) = (#, #), 2. ∃i, (C i , D i ) = (#, #) =⇒ a(d) = 1 ∧ (A, B) = (#, #), 3. ∃i, C i = # ∧ D i = # =⇒ A = # ∧ ∀i, C i = #, 4. ∃i, D i = # ∧ C i = # =⇒ B = # ∧ ∀i, D i = #,
Before defining the set of pictures and the word language accepted by an arborescent tiling system, we define for any arborescent picture p of domain X × [1, m] over Γ the set T(p) of tiling elements of p as the set of all subpictures p| x,j,X ′ ,2 of p such that x is an internal position in X, j ∈ [1, m -1] and

X ′ = {ε} ∪ {i ′ > 0 | xi ′ ∈ X}.
Definition 5 (Language of a tiling system). The set of arborescent pictures accepted by an arborescent tiling system S = (Γ, #, ∆) is the set P(S) = {p ∈ AP | T(p # ) ⊆ ∆}. The (word) language accepted by S is the set L(S) = {w ∈ Γ * | ∃p ∈ P(S), w = fr(p)} of all upper frontiers of pictures of P(S).

As previously, note that arborescent tiling systems are a syntactical generalisation of planar tiling systems : framed pictures with a domain X ⊆ 1 * or branches of framed arborescent pictures are planar framed pictures, and arborescent tiling systems whose elements all have arity 1 are ordinary, planar tiling systems. 2.1 represents an arborescent picture p whose frontier is the word a 3 b 3 c 3 , as well as the corresponding framed picture. For the sake of clarity, the tree-structure of p is denoted by dashed lines only where the arity is greater than 1. By considering all sub-pictures of height and width 2 of that framed picture, one obtains a set of tiling elements ∆, which contains, among others, tiling elements (#, #, a, b), (a, +, +, +) and (+, +, #, #) of arity 1 and (b, c, b +, ×+) of arity 2, but not (b, c, b +, c +) or (#, +, #, +) for instance.

× × × b b + + c c × × × b + + + + c × × × + + + + + + a a + + b b × × × a + + + + b × × × + + + + + + × × × # # # # # # # # # # # # a a a b b b c c c # # × × × b b + + c c # # × × × b + + + + c # # × × × + + + + + + # # # # # # # # # # # # # a a + + b b × × × # # a + + + + b × × × # # + + + + + + × × × # # # # # # # # # # # #
One can see that the tiling system S = ({a, b, c, +, ×}, #, ∆) accepts all arborescent pictures similar to p whose frontiers are words of the form a n b n c n with n ≥ 2 : the left branch of each such picture ensures that the number of a's and b's is equal by replacing at each successive row one occurrence of a and one occurrence of b by some symbol +. Occurrences of c are irrelevant and are replaced with symbol ×. A lower frame borders can only be generated once all occurrences of a and b have been replaced. A similar check is performed by the right branch for symbols b and c.

Note that S does not accept the word abc, since accepting a similar picture with frontier abc would require some additional tiling elements, like for instance (a, b, +×, ++) and (b, c, ++, ×+). Consequently, the language L(S) is

{a n b n c n | n ≥ 2}.

Languages of arborescent tiling systems

In this section, we prove that arborescent tiling systems and alternating linearly bounded machines define the same family of languages, namely ASPACE(O(n)), also equal as previously mentioned to DTIME(2 O(n) ) = ETIME.

Proposition 1. For every arborescent tiling system S, there exists an alternating linearly bounded machine M such that L(M ) = L(S).

Proof sketch. Let S = (Γ, #, ∆) be an arborescent tiling system. We build an alternating linearly bounded machine M = (Γ, Γ ′ , Q, q # , f, δ) accepting L(S). Its work alphabet Γ ′ is the union of all Γ k for k ∈ [1, a(S)], where Γ = Γ ∪ {#} and a(S) = max{a(d) | d ∈ ∆}. We informally describe M 's behaviour as follows:

1. M starts in configuration [q # w], where w ∈ Γ * is the input word. In a first sweep, it checks that w is a possible frontier of a picture accepted by S. 2. In the next sweep, M generates a n-tuple of possible next rows based on the current configuration and the tiles in ∆. M then uses universal branching to evaluate the sub-pictures whose upper frontiers are each of these rows. 3. The last generated row consists in a sequence of frame symbols # if and only if the last written symbol is #. If this is the case on the current computation branch, reach accepting state f . Otherwise, repeat the previous step.

Steps 2 and 3 are repeated until all computation branches have reached the accepting state f . ⊓ ⊔ Proposition 2. For every alternating linearly bounded machine M , there exists an arborescent tiling system S such that L(S) = L(M ).

Proof sketch. Let M = (Σ, Γ, Q, q 0 , F, δ) be an alternating linearly bounded machine. We build an arborescent tiling system S = (Γ ′ , #, ∆) such that L(S) = [L(M )], where [ and ] are two new symbols. The set of tiling elements ∆ is built in order to conform to the following informal specification. S first needs to set an input word w as the upper frontier of any picture it accepts. It then encodes the initial configuration of M on w as the second row. Subsequent tiles simulate the application of a transition of M on the configuration encoded by the current row, and check that the previous transition was correctly simulated. This requires additional information, in particular about the position of the head and the index of the last simulated transition, to be added to the picture alphabet. Arity n tiling elements are used when the simulated rule is of alternation degree n. This process goes on until an accepting state is reached by M on a given execution branch. In that case, a bottom border is generated by S on the corresponding picture branch.

⊓ ⊔

From Propositions 1 and 2, we deduce the announced theorem.

Theorem 1. The languages of arborescent tiling systems form the complexity class ETIME.

Note that the language accepted by the tiling system of Example 1 is a context-sensitive language, which could also be accepted by a non-arborescent tiling system.

Traces of term-automatic graphs

We now turn to the main result of this paper, which is the study of languages of graphs characterised by automata-defined binary relations over terms, and in particular term-automatic graphs. We define these relations and the graphs they generate, then present a two-steps proof that the languages of term-automatic graphs indeed coincide with ASPACE(O(n)). First, we establish this result for the simpler term-synchronous graphs in Section 3.2, then generalise it to termautomatic graphs in Section 3.3.

Definitions

Let s = f (s 1 . . . s m ) and t = g(t 1 . . . t n ) be two terms over some ranked alphabet F . We define the overlap [st] of s and t as a term over domain dom(s) ∪ dom(t) and extended alphabet (F ∪ {⊥}) 2 (each element (f, g) of this alphabet being written simply f g), such that ∀p ∈ dom(s) ∪ dom(t), [st](p) = f g with f = s(p) if p ∈ dom(s) or ⊥ otherwise, and g = t(p) if p ∈ dom(t) or ⊥ otherwise. This notation is extended to sets in the natural way.

We can now define term-automatic and term-synchronous relations. We say a binary relation R is term-(or tree-)automatic if the term language [R] = {[st] | (s, t) ∈ R} is regular. If furthermore for all (s, t) ∈ R, dom(s) = dom(t), it is called synchronous. In other words, a synchronous relation is an automatic relation which only associates terms with the same domain. Both families of relations are closed under relational composition. Term-automatic and termsynchronous relations are syntactical extensions of the corresponding families of relations over words. As such, they also define extended families of graphs.

Definition 6. A Σ-graph G is term-automatic (resp. term-synchronous) if it is isomorphic to a graph {u a → v | a ∈ Σ, (u, v) ∈ R a },
where (R a ) a∈Σ is a family of term-automatic (resp. term-synchronous) relations.

Term-synchronous graphs

This section presents direct simulations of alternating tiling systems by synchronous graphs and conversely, showing that the languages of term-synchronous graphs between regular sets of vertices form the class ETIME.

Proposition 3. For every term-synchronous graph G and regular sets I and F there exists an arborescent tiling system S such that L(S) = L(G, I, F ).

Proof sketch. Let G = (R a ) a∈Σ be a synchronous graph, and I, F two regular sets of vertices of G. We build a tiling system S = (Γ, #, ∆) such that L(S) = L(G, I, S).

For all a ∈ Σ, let A a be a finite top-down term automaton accepting the language [R a ] (as defined in Section 3.1), and A I , A F similar automata for I and F respectively. For every a ∈ Σ, we also define relations

R I•a = Id I • R a and R a•F = R a • Id F ,
where Id L denotes the identity relation over some set L. Let also A I•a and A a•F be two automata accepting the languages [R I•a ] and [R a•F ] respectively. The control state sets of all these automata are supposed disjoint.

The idea of this construction is that, for every path t 0 a1 → t 1 . . . an → t n in G with t 0 ∈ I, t n ∈ F and ∀i, dom(t i ) = X, S should accept an arborescent picture p whose upper frontier is w and whose successive vertical "slices" correspond to encodings of runs of A I•a1 , A a2 , . . . , A an-1 and A an•F respectively. Conversely, S should only accept all such pictures which correspond to paths in G between I and F . These conditions are sufficient for L(S) to be equal to L(G, I, F ). To ensure they indeed hold, we define ∆ in order to be able to check that the i-th and (i + 1)-th "slices" are indeed compatible.

⊓ ⊔ Proposition 4. For every arborescent tiling system S, there exists a term-synchronous graph G and regular sets I and F such that L(G, I, F ) = L(S).

Proof sketch. Let S = (Γ, #, ∆) be an arborescent tiling system. We build a term-synchronous graph G such that L(S) = L(G, I, F ) for some regular sets I and F . In the following, symbol # is overloaded to make the notation less cumbersome, and represents functional symbols of varying arities, which can be deduced from the context. In particular, we write # X for a given prefix-closed set X the term of domain X whose nodes are all labelled with #. Let R a , a ∈ Σ, be the binary relation between all terms #(s) and #(t) (i.e. s and t with an additional unary # at the root) such that a labels the root of t and for a given p ∈ P (S), either s = p| ε,i,X,1 and t = p| ε,i+1,X,1 for some i > 0 or s = # X and t = p| ε,0,X,1 . Let G be the graph defined by (R a ) a∈Σ , we show that G is term-synchronous by constructing automata (A a ) a∈Σ such that L(A a ) = [R a ] = {[st] | (s, t) ∈ R a }. For all a, A a has transitions:

q 0 ## → q AB,1 if (#, #, A, B) ∈ ∆, q Ā B,i AB → q C D,1 . . . q C D,k if d = (A i , B i , C, D) ∈ ∆, k = a(d), A i = Ā(i) and B i = B(i), q Ā B,i A i B i → ε if (A i , B i , #, #) ∈ ∆, A i = Ā(i) and B i = B(i).
We define I as the regular set of all terms labelled over {#}, and F as the set of all possible rightmost columns of pictures accepted by S. This set of terms is accepted by an automaton A F whose construction is straightforward. By construction of I, A F and each of the A a , there is a path in G labelled by a word w between a vertex in I and a vertex in F iff the vertices along that path are the successive columns of a picture in P (S) with frontier w. ⊓ ⊔

Term-automatic graphs

In this section, we show that the more general family of term-automatic graphs defines the same family of languages as their synchronous counterparts.

Proposition 5. For every term-automatic graph G and regular sets of terms I and F , there exists a term-synchronous graph G ′ and regular sets I ′ and F ′ such that L(G ′ , I ′ , F ′ ) = L(G, I, F ).

Proof sketch. Let G be a term-automatic graph defined by a family (R a ) a∈Σ of automatic relations and I, F be two regular languages, each [R a ] being accepted by an automaton A a , I by A I and F by A F . We define a synchronous graph G ′ = (R ′ a ) a∈Σ and two regular sets I ′ and F ′ such that L(G, I, F ) = L(G ′ , I ′ , F ′ ). Recall that term-automatic relations are defined using a notion of overlap between terms (Cf. Section 3.1). Two terms s and t with different domains belong to a term-automatic relation R defined by automaton A if the overlap [st] of s and t is accepted by A. This notion of overlap consists in "unifying" the domains of s and t, and padding undefined positions with a special symbol ⊥.

We wish to reuse this idea, but instead of unifying the domains of two terms only, we have to unify the domains of all vertices along a given path. Indeed, in a term-synchronous graph, edges can only exist between terms with precisely the same domain. For every term s standing for a vertex in G, we will thus have to consider an infinite set of "versions" of s in G ′ , one for each possible term domain larger than that of s.

Let Γ be a ranked alphabet, we define alphabet

Γ ′ as Γ ′ = Γ 0 ∪ Γ n with Γ ′ 0 = # 0 and Γ ′ n = Γ ∪ # n ,
where n is the maximal arity of symbols in Γ . Let φ be a mapping from T (Γ ) to 2 T (Γ ′ ) such that for any term t ∈ T (Γ ),

φ(t) = t ′ ∈ T (Γ ′ ) | dom(t) ⊂ dom(t ′ ), ∀p ∈ dom(t), t ′ (p) = t(p) and ∀p ∈ dom(t ′ ) \ dom(t), t ′ (p) ∈ {# 0 , # n } .
In other words, to any term t, φ associates the set of all terms obtained by "padding" t with silent symbols # 0 and # n . This mapping is extended to sets of terms in the natural way. Note that, given any t ′ ∈ F (Γ ′ ), there exists at most one term t ∈ T (Γ ) such that t ′ ∈ φ(t).

We now define, for every a ∈ Σ, relation R ′ a as {(s ′ , t ′ ) | (s, t) ∈ R a , s ′ ∈ φ(s), t ′ ∈ φ(t) and dom(s ′ ) = dom(t ′ )}. This synchronous relation can be characterised by a finite tree automaton A ′ a defined from A a . We also let I ′ = φ(I) and F ′ = φ(F ), for which automata can be similarly defined from A I and A F .

Let G ′ be the term-synchronous graph defined by (R ′ a ) a∈Σ . One can show that for every path labelled w in G ′ between some i ′ ∈ I ′ and f ′ ∈ F ′ , there exists a unique path between I and F in G with the same label, and that conversely for every w-path between I and F in G there must exist at least one corresponding path in G ′ between I ′ and F ′ . This ensures that L(G, I, F ) and L(G ′ , I ′ , F ′ ) are indeed equal.

⊓ ⊔ Remark 1. Note that for every term-automatic graph G and regular sets I and F , there exists a term-automatic graph G ′ and finite sets I ′ and F ′ such that L(G ′ , I ′ , F ′ ) = L(G, I, F ). Indeed, for any regular I and F and finite I ′ and F ′ the relations I ′ × I and F × F ′ are automatic. Since term-automatic relations are closed under union and composition, this can be used to build G ′ from G. This, however, does not hold in the term-synchronous case. Indeed, since each connected component of a term-synchronous graph is finite, the language of any such graph from a finite set of initial vertices is regular.

Combining Theorem 1, Propositions 3, 4 and 5, as well as Remark 1, we obtain the following result concerning the family of languages accepted by termsynchronous and term-automatic graphs.

Theorem 2. The languages of term-synchronous graphs between regular sets of vertices and of term-automatic graphs between regular or finite sets of vertices form the complexity class ETIME.

Conclusion

We have proved that the class of languages accepted by alternating linearly bounded machines (ETIME) can also be characterised as the sets of first rows of pictures accepted by arborescent tiling systems, as well as the sets of path labels of term-automatic graphs between regular or finite sets of initial and final vertices.

A natural extension of this work would be to generalise Theorem 2 to graphs defined by more expressive classes of tree transducers, in order to fully extend the existing results on rational graphs. In practice, this would require extending the construction for Proposition 5 to more general padding techniques.

Further points of interest concern the extension of other results from [CM06] to term-automatic graphs, in particular regarding structural restrictions of these graphs, like finite or bounded degree, or the restriction to a single initial vertex, as well as a similar study of related complexity classes or families of languages.

  a n and v = b 1 . . . b m is the word uv = a 1 . . . a n b 1 . . . b m . The concatenation operation extends to sets of words: for all A, B ⊆ Σ * , AB stands for the set {uv | u ∈ A and v ∈ B}.

  Each tiling element d ∈ ∆ is of the form d = (A, B, C, D) with A, B ∈ Γ and C, D ∈ Γ n for some positive integer n. We define additional notations to conveniently manipulate tiling elements. Let d = (A, B, C, D) with C = C 1 . . . C n and D = D 1 . . . D n , we write a(d) = n to denote the arity of d, and d i with i ∈ [1, a(d)] to denote the (planar) tile (A, B, C i , D i ).

  a a a b b b c c c

Fig. 1 .

 1 Fig. 1. Arborescent picture p and the corresponding framed picture p #

Figure


Nutan Limaye

Meena Mahajan

Antoine Meyer
email: ameyer@liafa.jussieu.fr

On the complexity of membership and counting in height-deterministic pushdown automata

While visibly pushdown languages properly generalise regular languages and are properly contained in deterministic context-free languages, the complexity of their membership problem is equivalent to that of regular languages. However, the corresponding counting problem could be harder than counting paths in a non-deterministic finite automaton: it is only known to be in LogDCFL. We investigate the membership and counting problems for generalisations of visibly pushdown automata, defined using the notion of heightdeterminism. We show that, when the stack-height of a given PDA can be computed using a finite transducer, both problems have the same complexity as for visibly pushdown languages. We also show that when allowing pushdown transducers instead of finite-state ones, both problems become LogDCFL-complete; this uses the fact that pushdown transducers are sufficient to compute the stack heights of all real-time heightdeterministic pushdown automata, and yields a candidate arithmetization of LogDCFL that is no harder than LogDCFL(our main result).

Introduction

There is a close connection between complexity classes and formal language theory. Over the years, various language classes have been studied from the complexity theoretic perspective. Capturing the complexity of membership has been the goal in this approach. The study of language classes and their complexity under meaningful closures was first started by Sudborough [START_REF] Sudborough | A note on tape-bounded complexity classes and linear contextfree languages[END_REF][START_REF] Sudborough | On the tape complexity of deterministic context-free language[END_REF]. In [START_REF] Sudborough | A note on tape-bounded complexity classes and linear contextfree languages[END_REF], he showed that the nondeterministic linear context-free languages or LIN are complete for the complexity class NL (nondeterministic log-space). In [START_REF] Sudborough | On the tape complexity of deterministic context-free language[END_REF], he defined two interesting complexity classes, namely LogCFL and LogDCFL, as the log-space closures of context-free languages (CFLs) and their deterministic counterparts (DCFLs) respectively. Ibarra, Jiang and Ravikumar [START_REF] Ibarra | Some subclasses of context-free languages in N C 1[END_REF] further studied subclasses of CFL such as DLIN LL [START_REF] Sudborough | A note on tape-bounded complexity classes and linear contextfree languages[END_REF] (the deterministic counterpart of LIN defined by LL(1) linear grammars), Dyck2 and bracketed expressions and showed that they are contained in NC 1 . Holzer and Lange [START_REF] Holzer | On the complexities of linear LL(1) and LR(1) grammars[END_REF] showed that deterministic linear context-free languages (DLIN), as defined via LR(1) linear grammars, are equivalent to those accepted by deterministic 1-turn automata DPDA 1-turn (deterministic pushdown automata that never push after a pop move). They showed that deciding membership in a DLIN language is complete for L, in contrast to the result of [START_REF] Ibarra | Some subclasses of context-free languages in N C 1[END_REF]. Barrington made an important contribution to the above study [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1[END_REF], showing that the class of regular languages, REG, is complete for the circuit complexity class NC 1 comprising of polynomial size log depth bounded fan-in and-or circuits. (As the classes get smaller, completeness is via not L -reductions but appropriate weaker notions such as AC 0 -many-one-reductions.) See [START_REF] Lange | Complexity and structure in formal language theory[END_REF] for an overview of these results.

Visibly pushdown automata (VPA) are real-time pushdown automata whose stack behaviour is dictated solely by the input letter under consideration. They are also referred to as input-driven PDA. The membership problem for VPL was considered in [START_REF] Mehlhorn | Pebbling mountain ranges and its application to DCFL recognition[END_REF][START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF][START_REF] Dymond | Input-driven languages are in log n depth[END_REF]; [START_REF] Dymond | Input-driven languages are in log n depth[END_REF] shows that languages accepted by such PDA are in NC 1 . A rigorous language-theoretic study of VPA was done in [START_REF] Alur | Visibly pushdown languages[END_REF], where it is shown that they can be determinised. Thus they lie properly between REG and DCFLs, and their membership problem is complete for NC 1 .

A related line of study is understanding the power of counting. It is easy to see from the proof of [START_REF] Sudborough | A note on tape-bounded complexity classes and linear contextfree languages[END_REF] that counting the number of parse trees in a linear grammar, #LIN, is equivalent to counting accepting paths in an NL machine. At the lower end, however, though Barrington's result showed that deciding membership in REG (and hence in the language of a nondeterministic finite-state automaton or NFA) is equivalent to NC 1 , counting the number of accepting paths in an NFA (#NFA) is not yet known to be equivalent to arithmetic NC 1 , #NC 1 . In [START_REF] Caussinus | Nondeterministic N C 1 computation[END_REF], a one-way containment is shown: #NFA ⊆ #NC 1 , but to this day the converse reduction remains open 3 . A natural question to ask is what generalisation of NFA can capture #NC 1 in this setting. In [START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF], it was claimed that the generalisation to VPA adds no power, #VPA is equivalent to #NFA. However, this claim was later retracted in [START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF], where it is shown, however, that #VPA functions can be computed in LogDCFL (and are hence presumably weaker than #PDA functions).

Our starting point in this note is a careful examination of what makes membership and path-counting easier in VPA than in general PDA. The intention is to identify a largest possible class of PDA for which the technique used for VPA can still be applied. This technique exploits the fact that, despite nondeterminism, all paths on a given input word have the same stack-profile, and furthermore, this profile is very easily computable. One can view the partitioning of the input alphabet as height advice being provided to an algorithm for deciding membership. This naturally leads to the conjecture that PDA possessing easy-to-compute height advice functions should be easier than general PDA. The real-time heightdeterministic PDA defined by Nowotka and Srba ( [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF]), rhPDA, are a natural candidate: they are defined as precisely those PDA that possess height advice functions. They also very naturally generalise a subclass of the synchronised PDA defined by Caucal ([15]), namely the subclass where the synchronisation function is the stack-height, and, as in general synchronised PDA, is computable by a finite-state transducer. We provide a parameterised definition of rhPDA that captures this generalisation: the complexity of the transducer computing the height advice function is the parameter. We then examine the complexity of membership and path-counting at either end of the parameterisation.

A related model equivalent to VPA is that of nested word automata (NWA), defined in [START_REF] Alur | Adding nesting structure to words[END_REF] with a view to applications in software verification and XML document processing. [START_REF] Blass | A note on nested words[END_REF] defines motley word automata (MWAs) as a generalisation of NWAs. Our techniques can be used to show that the equivalence is indeed very strong: deciding membership and counting accepting paths in NWA and MWA are NC 1 -equivalent to the same problems over VPA.

Preliminaries

A pushdown automaton (PDA) over Σ is a tuple P = (Q, q 0 , F, Γ, Σ, δ) where Q is a finite set of control states, q 0 ∈ Q the initial state, F ⊆ Q a set of accepting states, Γ a finite alphabet of stack symbols, Σ a finite alphabet of labels and δ a finite set of transition rules pU a -→ qV with p, q ∈ Q, U, V ∈ Γ * and a ∈ Σ. In the following, we will only consider weak PDA, whose rules are such that |U V | ≤ 1. 4A configuration of P is a word of the form pW with p ∈ Q and W ∈ Γ * , where p is the current control state and W is the current stack content read from top to bottom. The stack height at configuration pW is |W |.

The semantics of P are defined with respect to its transition graph

G P = {pU W a -→ qV W | pU a -→ qV ∈ δ, W ∈ Γ * }.
A run of P on input word w ∈ Σ * from configuration pW is a path in G P between vertex pW and some vertex qW , written pW w -→ qW . Such a run is successful (or accepting) if pW = q 0 and q belongs to the set F of accepting states of P . By L(G P , S, T ) where S, T are sets of vertices of G P , we mean all words w ∈ Σ * such that c w -→ c for some configurations c ∈ S, c ∈ T . The language of P is the set of all words w over which there exists an accepting run; i.e. it is the language L(G P , {q 0 }, F Γ * ).

A visibly pushdown automaton (VPA) over Σ is a weak PDA P where Σ is partitioned as Σ c ∪ Σ r ∪ Σ i , and for all p ∈ Q, a ∈ Σ, p a -→ qγ ⇒ a ∈ Σ c (a push move/call ), pγ a -→ q ⇒ a ∈ Σ r (a pop move/return) and p a -→ q ⇒ a ∈ Σ i (an internal move). VPA can be nondeterministic, i.e. δ need not be a function. VPA are equivalent to the earlier notion of input-driven automata when run on well-matched strings, and their languages can be easily reduced to input-driven languages, as observed in [START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF][START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF].

For any class C of automata, its arithmetic version #C is defined as follows: [START_REF] Caussinus | Nondeterministic N C 1 computation[END_REF][START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF]). The following inclusions hold:

#C = {f : Σ * → N | for some M ∈ C, f (x) = #acc M (x) for all x ∈ Σ * } Proposition 1 ([
#NFA ⊆ #NC 1 ⊆ L ⊆ LogDCFL #NFA ⊆ #VPA ⊆ LogDCFL (A containment F ⊆ C involving both a function class F and a language class C means: ∀f ∈ F, L f ∈ C, where L f = { x, i, b | the ith bit of f (x) is b}.)
3 Revisiting the VPL in NC 1 proof

In [START_REF] Dymond | Input-driven languages are in log n depth[END_REF], Dymond proved that the membership problem for VPL is in NC 1 . Dymond's proof transforms the problem of recognition/membership to efficiently evaluating an expression whose values are binary relations on a finite set and whose operations are functional compositions and certain unary operations depending on the inputs. This transformation is done in NC 1 . Containment in NC 1 follows from the result, due to Buss [START_REF] Buss | The Boolean formula value problem is in ALOGTIME[END_REF], that the evaluation of formulae involving expressions as k-ary functions over a finite domain is in NC 1 . For a VPA, on an input w, the stack height after processing i letters, h(i, w) (or simply h(w) if i = |w|), is the same across any run. Define a set of binary relations, denoted ⇒ i,j for 1 ≤ i ≤ j ≤ |w|, on surface configurations (q, γ) ∈ Q×Γ (state and stack-top pair). These relations are expected to capture all cases where surface configurations are reachable from one another without accessing the previous stack profiles. A unary operation, and a composition operation, are defined on these relations. Given a string w, the main work is to figure out the correct indices for the relations and then the appropriate operations. But that can be accomplished essentially by computing stack heights for various configurations, which is easy for VPL.

As pointed out in [START_REF] Dymond | Input-driven languages are in log n depth[END_REF], the above transformation works for more than VPAs.

Remark 1 ([9]

). Dymond's NC 1 membership algorithm works for any pushdown automaton M satisfying the following three conditions.

-There should be no -moves.

-Accepting runs should end with an empty stack (and a final state).

-There should exist an NC 1 -computable function h such that for w ∈ Σ * and 0 ≤ i ≤ |w|, h(i, w) is the height of the stack after processing the first i symbols of w. If M is non-deterministic, then h(i, w) should be consistent with some run ρ of M on w; further, if M accepts w, then ρ should be an accepting run.

Clearly, VPA satisfy these conditions. By definition, they have no -moves. Though they may not end with an empty stack, this can be achieved by appropriate padding that is computable in TC 0 , see for instance [START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF][START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF]. (TC 0 is a subclass of NC 1 consisting of polynomial size constant depth circuits where each gate is allowed unbounded fan-in, and gates compute majority and not.) Though VPA may be nondeterministic, all runs have the same height profile, and the function h(i, w) can in fact be computed in TC 0 .

Since any computation up to NC 1 can be allowed for Dymond's proof to go through, VPL do not fully exploit Dymond's argument. We explore a natural generalisation of VPA allowing us to define natural classes for which Dymond's scheme or its precursor from [START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF] may work for deciding membership, and then examine the power of counting in these models.

More general height functions: height-determinism

Adding a pushdown stack to an NFA significantly increases the complexity of both membership (regular to context-free) and path-counting (#NFA to #PDA). However, if stack operations are restricted to an input-driven discipline, as in VPA, then membership is no harder than for NFA, and path-counting seems easier than over general PDA. What is being exploited is that, despite nondeterminism, all paths on a given input word have the same stack-profile, and this profile is computable in NC 1 (and even in TC 0 ). One can view the partitioning of the input alphabet as height advice being provided to an algorithm for deciding membership. This naturally leads to the question: what can be deduced from the existence of such height advice, independently of how this function is computed?

The term height-determinism, coined by [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF], captures precisely this idea. A PDA is height-deterministic if the stack height reached after any partial run depends only on the input word w which has been read so far, and not on non-deterministic choices performed by the automaton. Consequently, in any (real-time) height-deterministic pushdown automaton (rhPDA), all runs on a given input word have the same stack profile. Another way to put it is that for any rhPDA P , there should exist a height-advice function h from Σ * to integers, such that h(w) is the stack-height reached by P on any run over w.

Any rhPDA that accepts on an empty stack and whose height-advice function h is computable in NC 1 directly satisfies the conditions in Remark 1, and hence its membership problem lies in NC 1 . In this section, we explore some sub-classes of rhPDA and discuss the complexity of their membership and counting problems.

Let us first give a formal definition of rhPDA.

Definition 1 (rhPDA, [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF]). A real-time (weak) pushdown automaton 5 P = (Q, q 0 , F, Γ, Σ, δ) is called height-deterministic if it is complete (does not get stuck on any run), and ∀w ∈ Σ * , q 0 w -→ qα and q 0 w -→ qβ imply |α| = |β|.

The robustness of this notion is illustrated by the fact that rhPDA retain most good properties of VPA, even when the actual nature of the height-advice function is left unspecified. This had already been obtained in [START_REF] Caucal | Synchronization of pushdown automata[END_REF] for a slightly different class (which the authors of [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF] admittedly used as a starting point in the elaboration of their paper).

Proposition 2 ( [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF][START_REF] Caucal | Synchronization of pushdown automata[END_REF]). Any rhPDA can be determinised. Consequently, for a fixed h, the class of languages accepted by rhPDA and whose height advice function is h forms a boolean algebra (and properly includes regular languages). Moreover, language equivalence between two rhPDA with the same height-advice function is decidable.

All these results are effective as soon as h is computable. Since any deterministic real-time PDA is also height-deterministic, another consequence of the fact that rhPDA can be determinised is that the whole class rhPDA accepts precisely the class of real-time DCFL. 5 In [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF], the definition involves rules of the form pX a -→ qα where α ∈ { , X} ∪ {Y X|Y ∈ Γ }. This is not an essential requirement for the results presented here.

Instances of height-deterministic PDA

The definition of a rhPDA leaves the exact nature of the height-advice function h unspecified. This is troublesome, since h could be arbitrarily complex. We consider some classes of specific height-advice functions, the simplest being VPA.

Following the framework developed by Caucal [START_REF] Caucal | Synchronization of pushdown automata[END_REF], we consider classes T of transducers mapping words to integers. A transducer T over Σ and Z is a transition system (C, c 0 , F, (Σ × Z), δ), where c 0 denotes the initial configuration and F a set of final configurations, and whose transitions described by δ are labelled with pairs (a, k), where a is a letter and k an integer. The first component of any such label is considered as an input, and the second component as an output. A run c 0 (a 1 , k 1 )c 1 . . . c n-1 (a n , k n )c n is associated to the pair (w, k) (a 1 . . . a n , k 1 +. . .+k n ). Such a transducer defines a relation g T ⊆ Σ * ×Z defined as the set of all pairs (w, k) labelling an accepting run in T .

In our setting, we only consider both input-complete and input-deterministic transducers (i.e. transducers whose underlying Σ-labelled transition system is deterministic and complete), in which all configurations are final (in which case we omit F in the definition). Consequently, for any such transducer T the relation g T is actually a function, and is defined over the whole set Σ * . The transition graph G P of a PDA P is said to be compatible with a transducer T if for every vertex

s of G P , if u, v ∈ L(G P , {q 0 }, {s}) then g T (u) = g T (v).
One may consider several kinds of transducers. The simplest class is finitestate transducers (FST), where the configuration space C is simply a finite set of control states (often written Q). One may also consider pushdown transducers (PDT) whose underlying Σ-labelled transition system is a PDA transition graph, or even more complex transducers (for instance defined using Turing machines).

Definition 2. For any class T of complete deterministic transducers, rhPDA(T ) is the class of rhPDA whose height function h can be computed by a transducer T in T , in the sense that h(w) = |g T (w)| (absolute value of g T (w)) for all w.

The height-advice function of any VPA running on well-matched strings can be computed by a single-state transducer, that reads letters and outputs +1 or -1 or 0 depending on whether the letter is in Σ c or Σ r or Σ i . However, note that such single-state transducers can also compute stack-heights for languages that are provably not in VPL. Also, allowing more than one state in a FST provably enlarges the class of languages. The language REV = {wcw R | w ∈ {a, b} * } is not a VPL. The obvious DPDA acceptor has a height function computable by a two-state transducer: one state has +1 on a and b, the other has -1 on a and b, and moves to second state on c. It is easy to see that for any PDA accepting REV, two states in the transducer are essential for computing stack height.

Further, [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF] provided a separating example in rhPDA but not in rhPDA(FST); from Proposition 3 below, it follows that this language is in fact in rhPDA(PDT). In the remainder of this section, we will focus on the classes rhPDA(FST) and rhPDA(PDT), and also to some extent on the class rhPDA(rDPDA 1-turn ), where the transducer is a 1-turn PDT.

The class we define as rhPDA(FST) is a restricted (and simpler) subclass of the synchronised pushdown automata considered by Caucal in [START_REF] Caucal | Synchronization of pushdown automata[END_REF]. Even though Caucal's results require, for a PDA to be synchronised by a transducer T , that the transition graph of P satisfy some additional geometric properties with respect to g T , these properties are always satisfied when only considering stack-height 6 . One can thus see rhPDA(FST) as the intersection of rhPDA with synchronised PDA. As an aside, we note that [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF] considers the class rhPDA(FST) as equivalent to synchronised PDA. This is guaranteed to be true and has to be proved, since [START_REF] Caucal | Synchronization of pushdown automata[END_REF] also permits synchronisation by norms other than stack-height.

Finally, we note that since, by definition, rhPDA are complete, it is in fact unnecessary to consider more complex transducers than deterministic and complete PDTs. Formally: Proposition 3. For any rhPDA P whose height-advice function is h, there exists a deterministic and complete pushdown transducer T such that h(w) = g T (w) for all w ∈ Σ * . That is, every rhPDA is in rhPDA(PDT).

Complexity of the membership problem

As we already mentioned, rhPDA have exactly the same power as real-time DPDA in terms of accepted languages. This settles the complexity of the membership question for the whole class rhPDA (and thus also for rhPDA(PDT)): it is in LogDCFL, and since the hardest DCFL ( [START_REF] Sudborough | On the tape complexity of deterministic context-free language[END_REF]) is hard for the class LogDCFL and is accepted by a real-time DPDA, it is also hard for LogDCFL.

We observe easy bounds on the complexity of the height-advice function.

Lemma 1. For a complete deterministic transducer T computing function g T ,

1. If T is a FST, then g T is computable in NC 1 . 2. If T is a rDPDA 1-turn , then g T is computable in L. 3. If T is a PDT, then g T is computable in LogDCFL.
This allows us to apply Dymond's algorithm for rhPDA(FST).

Lemma 2. For any fixed rhPDA(FST), the membership problem is in NC 1 .

This membership algorithm exploits Dymond's construction better than VPA, as the height function requires a possibly NC 1 -complete computation (predicting states of the transducer). Recall that for VPA, the height function is computable in TC 0 , a subclass of NC 1 .

In [START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF], the membership problem for VPLs is shown to be in L. We observe that their algorithm can be more explicitly implemented as L g where g is the height function of the VPL. In this form, it can be generalised to any rhPDA having height function g, as stated in Theorem 1 below. The proof follows from Lemmas 3 and 4, and the result, along with Lemma 1, yields the next corollary.

Theorem 1. For any fixed rhPDA P with height function g, the membership problem is in L g . Corollary 1. 1. The membership problem for rhPDA(rDPDA 1-turn ) is in L.

The membership problem for rhPDA is in LogDCFL.

The class rhPDA(rDPDA 1-turn ) referred to here contains languages accepted by real-time DPDA 1-turn as well as languages accepted by rhPDA(FST). It is contained in DCFLs. The upper bound for rhPDA follows from [START_REF] Nowotka | Height-deterministic pushdown automata[END_REF], where it is shown that rhPDA as a language class equals the DCFLs accepted by DPDA with no -moves, and so is a proper subclass of DCFLs.

Lemma 4 uses the algorithm from [START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF] to establish the L g T bound for wellmatched inputs, and Lemma 3 brings the input in that form. Lemma 3. For every rhPDA(T ) P over an alphabet Σ, there is a corresponding rhPDA(T ) P over an alphabet Σ and a L g T many-one reduction f such that for every x ∈ Σ * , #acc P (x) = #acc P (f (x)), and f (x) is well-matched.

Lemma 4 (Algorithm 2 of [START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF], stated differently). Let P = (Q, Σ, Q in , Γ, δ, Q F ) be a rhPDA(T ) accepting well-matched strings. Given an input string x, checking if x ∈ L(P ) (membership test for L(P )) can be done in L g T .

Complexity of the counting problem

The aspect of rhPDA which interests us in this study is that it is a nondeterministic model capturing the deterministic class LogDCFL. It thus provides a way of arithmetising LogDCFL, simply by counting the number of accepting paths on each word in a rhPDA. We call the class of such functions #rhPDA. In particular, we consider the classes #rhPDA(FST) and #rhPDA(PDT).

We have seen that although rhPDA(FST) properly generalises VPA, the membership problem has the same complexity as that over VPA. It turns out that even the path-counting problem has the same complexity.

Theorem 2. #rhPDA(FST) ≡ #VPA (via NC 1 many-one reductions).

Proof Sketch. VPA are contained in rhPDA(FST), so we only need to show that computing #rhPDA(FST) functions reduces to computing #VPA functions.

Let P be an rhPDA with height-advice computed by FST T . A naive approach would be to construct a single PDA P that simulates (P, T ) by running PDA P along with transducer T . However, such a PDA P will not necessarily be a VPA. Now consider the string rewritten using an enriched alphabet which consists of the input letter along with a tag indicating whether P should push or pop. On this enriched alphabet, if the tags are correct, then a PDA that simulates the original PDA P (i.e. ignores the tags) behaves like a VPA. But by Lemma 1, the correct tags for any word can be computed in NC 1 .

Theorem 3 shows that membership and counting for rhPDA have the same complexity, a situation rather unusual for nondeterministic complexity classes. Theorem 3. #rhPDA is in LogDCFL.

The proof of this theorem proceeds in several stages. To compute a #rhPDA function f on input x, we first compute f (x) modulo several small (logarithmic) primes, and then reconstruct f (x) from these residues. This is the standard Chinese remainder technique (see for instance [START_REF] Vollmer | Introduction to Circuit Complexity: A Uniform Approach[END_REF]), stated formally below.

Lemma 5 (folklore). Let P be a fixed rhPDA. There is a constant c ≥ 0, depending only on P , such that given input x, the number of accepting paths of P on input x can be computed in logarithmic space with oracle access to the language L res defined below. (Here p i denotes the ith prime number.)

L res = { x, i, j, b |1 ≤ i ≤ |x| c , the jth bit of #acc P (x) mod p i is b }
We now show that L res can be computed by a polynomial time DAuxPDA machine -a deterministic polynomial time PDA with O(log n) auxiliary space, this model characterises LogDCFL -making oracle queries to the height-advice function g T . This follows from the technique of [START_REF] Braunmuhl | Input-driven languages are recognized in log n space[END_REF] as used in [START_REF] Limaye | Arithmetizing classes arround NC 1 and L[END_REF] to show that #VPA functions are in LogDCFL. Lemma 6. If P is any rhPDA and T a PDT computing its height-advice function, then L res is in LogDCFL g T . Lemmas 1 and 6 together imply that L res is in LogDCFL(LogDCFL). This is not adequate for us, since it is not known whether LogDCFL(LogDCFL) ⊆ LogDCFL. (Relativising a space-bounded class is always tricky. Here, we have a pushdown class with auxiliary space, making the relativisation even more sensitive.) However, we further note that the LogDCFL g T machine accepting L res makes oracle queries which all have short representations: each query can be written in logarithmic space. (Strictly speaking, the input x is also part of the query. But for eliminating the oracle, this plays no role.) In such a case, we can establish a better bound, which may be of independent interest: Lemma 7. Let L(M A ) be the language accepted by a poly-time DAuxPDA M which makes O(log n)-bits oracle queries to a language A ∈ LogDCFL. Then L(M A ) ∈ LogDCFL.

Combining these lemmas proves Theorem 3, since L(LogDCFL) equals LogDCFL.

Related models: nested and motley words

In [START_REF] Alur | Adding nesting structure to words[END_REF], Alur and Madhusudan defined nested word automata (NWA) as an equivalent model for VPA, motivated by applications in software verification and XML document processing. In [START_REF] Blass | A note on nested words[END_REF], Blass and Gurevich defined motley word automata (MWAs) as a generalisation of NWAs. The definitions of models of NWA and MWA are orthogonal to the notion of height-determinism. However, we observe that their complexity bounds are the same as that of VPL for both membership and counting problems.

We begin with definitions of NWA and MWA.

A nested relation ν of width n, for n ≥ 0, is a binary relation over [1, n] such that (1) if ν(i, j) then i < j; (2) if ν(i, j) and ν(i , j ) then either {i, j} = {i , j } or {i, j} ∩ {i , j } = ∅, and (3) if ν(i, j) and ν(i , j ) and i < i then either j < i or j < j.

If ν is a nested relation with ν(i, j), then i is the call-predecessor of j and j is the return-successor of i. The definition requires that each position has at most one call-predecessor or at most one return-successor but not both.

A nested word over an alphabet Σ is a pair (w, ν) such that w ∈ Σ * , and ν is a nested relation of width |w|. A position k ∈ [1, |w|] of w is a call position if (k, j) ∈ ν for some j, a return position if (i, k) ∈ ν for some i, and an internal position otherwise.

Definition 3 (NWA). A nested word automaton (NWA) A over an alphabet

Σ is a tuple (Q, q 0 , F, Σ, δ) where Q is a finite set of states, q 0 ∈ Q is the initial state, F ⊆ Q is a set of final states , δ = δ c , δ i , δ r is a set of transitions such that δ c ⊆ Q × Σ × Q, δ i ⊆ Q × Σ × Q and δ r ⊆ Q × Q × Σ × Q are the

transitions for call, internal and return positions respectively.

A starts in state q 0 and reads the word left to right. At a call or internal position, the next state is determined by the current state and input symbol, while at a return position, the next state can also depend on the state just before the matching call-predecessor. A run ρ of the automaton A over a nested word nw = (a 1 . . . a n , ν) is a sequence q 0 , . . . , q n over Q such that for each 1 ≤ j ≤ n, -if j is a call position, then (q j-1 , a j , q j ) ∈ δ c -if j is a internal position, then (q j-1 , a j , q j ) ∈ δ i -if j is a return position with call-predecessor k, then (q j-1 , q k-1 , a j , q j ) ∈ δ r .

A accepts the nested word nw if q n ∈ F . The language L(A) of a nested-word automaton A is the set of nested words it accepts.

A motley word mw of dimension d over Σ is a tuple (w, ν 1 , . . . , ν d ), where w ∈ Σ * and ν 1 , . . . , ν d are nested relations of width |w|.

Definition 4 (MWA). A motley word automaton (MWA) A of dimension d is a direct product

A 1 × . . . × A d of d NWA A 1 , . . . , A d . 7
A run of A on dimension d motley word mw = (w, ν 1 , . . . , ν d ) with |w| = n is a sequence (q 1 0 , . . . , q d 0 ), . . . , (q 1 n , . . . , q d n ) of states of A such that every (q k 0 , . . . , q k n ) [START_REF] Blass | A note on nested words[END_REF], since for some i = j, the same position can be a call-position for ν i and a return position for ν j .

/ / f f & & L L L L L L rhPDA(FST) / / rhPDA(
It is shown in [START_REF] Alur | Adding nesting structure to words[END_REF] (Theorem 6) that for a fixed NWA, the membership question is in NC 1 . The analogous question for a fixed MWA is easily seen to have the same complexity, since it involves answering membership questions for d different, but fixed, NWAs, where d is the dimension of the MWA.

In both models, NWA and MWA, non-determinism is allowed in the definition. We show that path-counting in NWA and MWA is equivalent to that in VPA. This does not follow from the equivalence of membership testing; rather, it requires that the equivalence be demonstrated by a parsimonious reduction. Theorem 4. Deciding membership and counting accepting paths in NWA and MWA are equivalent, via NC 1 -many-one reductions, to the corresponding problems over VPA.

Conclusion

We have studied a range of real-time height-deterministic pushdown automata lying between visibly and real-time deterministic pushdown automata. Fig. 1 depicts the relations between language classes, Fig. 2 shows their closures under appropriate reductions, and Fig. 3 Some open questions remain. First, it would be interesting to investigate additional classes lying between rhPDA(FST) and rhPDA(PDT). Also, the only known upper bound for #VPL, #rhPDA(FST) and #rhPDA(rDLIN), is LogDCFL. It would be interesting to refine this bound. Finally, all of our results concern height-deterministic PDA. However, [START_REF] Caucal | Synchronization of pushdown automata[END_REF] allows PDA to be synchronised by functions other than stack-height. It is not clear how many of our proofs carry over.

Example 1 .

 1 The language EQ(a, b) = {w | |w| a = |w| b } is not accepted by any VPA for any partition of {a, b}. But a single-state transducer can compute the stack-height of the obvious DPDA acceptor: it outputs +1 on a and -1 on b.

  shows the corresponding counting classes. (Dashed arrows indicate incomparability, dotted arrows containment, and solid arrows proper containment.)

NC 1 /Fig. 3 .

 13 Fig. 3. Summary of counting classes

  Summary of language classes closures is a run of A k on the nested word (w, ν k ). A run of A on mw is accepting (or mw is accepted by A) if each of the d constituent runs is. L(A) is defined as usual.The languages of nested/motley words accepted by NWA or MWA are called regular nested/motley languages. Regular motley languages strictly generalise regular nested languages

	rDLIN) O O / / rhPDA I I $ $ I I I I I I I x Fig. 1. Summary of language classes REG < < x x x x x x x x
	NC 1 , REG, VPL, rhPDA(FST), DLIN LL(1)	/ / rhPDA(rDLIN)	/ / L, DLIN LR(1)	rhPDA, / / DCFL, LogDCFL
		Fig. 2.

[START_REF] Caussinus | Nondeterministic N C 1 computation[END_REF] shows a weaker converse: every #NC 1 function can be expressed as the difference of two #NFA functions.

This is only for simplicity, as all results go through for arbitrary U, V ∈ Γ * .

In the terminology of[START_REF] Caucal | Synchronization of pushdown automata[END_REF], this is due to the fact that all transition graphs of pushdown automata are regular by stack height.

As NWA are in general non-deterministic, so are motley automata. A MWA A 1 × . . . × A d is deterministic if every nested word automata A k is so.