Bruno Guillon
email: bruno.guillon@uca.fr

Martin Kutrib

Andreas Malcher

Luca Prigioniero
email: prigioniero@di.unimi.it

Reversible Pushdown Transducers

Keywords: Pushdown transducers, reversible computations, computational capacity, transduction hierarchies

Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to four types of lengthpreserving transductions as well as to the property of working reversibly. It turns out that accurate to one case separating witness transductions can be provided. For the remaining case it is possible to establish the equivalence of both families by proving that stationary moves can always be removed in length-preserving reversible pushdown transductions.

Introduction

Reversible computational models have earned much attention recently, where one incentive for the study of computational devices performing logically reversible computations is probably the question posed by Landauer of whether logical irreversibility is an unavoidable feature of useful computers. Landauer has demonstrated the physical and philosophical importance of this question by showing that whenever a physical computer throws away information about its previous state it must generate a corresponding amount of entropy that results in heat dissipation (see [START_REF] Bennett | Logical reversibility of computation[END_REF] for further details and references). As one of the first models Turing machines have been investigated towards their ability to work reversibly in the work of Lecerf [3] and Bennett [START_REF] Bennett | Logical reversibility of computation[END_REF], where it is shown that for every Turing machine an equivalent reversible Turing machine can be constructed. At the other end of the Chomsky hierarchy, Angluin introduced reversible computations in deterministic finite automata (DFA) and showed that reversible DFAs are weaker than DFAs in general [START_REF] Angluin | Inference of reversible languages[END_REF]. Moreover, it is known that the general model and the reversible one coincide if the input head is two-way [START_REF] Kondacs | On the power of quantum finite state automata[END_REF]. An algebraic characterization of languages accepted by reversible multiple-entry DFAs is obtained in [START_REF] Pin | On reversible automata[END_REF]. Recent results on reversible regular languages are given in [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF][START_REF] Lavado | Minimal and reduced reversible automata[END_REF][START_REF] Lavado | Concise representations of reversible automata[END_REF], where different aspects concerning the descriptional complexity and the minimality of reversible (one-way) DFAs are studied. For deterministic pushdown automata, it has been shown that the reversible variant is weaker than the general one [START_REF] Kutrib | Reversible pushdown automata[END_REF].

Computational models are not only interesting from the viewpoint of accepting some input, but also from the more applied perspective of transforming some input into some output. For example, a parser for a programming language should not only return the information whether or not the input word can be parsed, but also the parse tree in the positive case. Transductions that are computed by different variants of transducers are studied in detail in the book of Berstel [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]. Deterministic and nondeterministic pushdown transducers are investigated in [START_REF] Aho | The theory of parsing, translation, and compiling[END_REF], where also characterizations of pushdown transductions as well as applications to the parsing of context-free languages are given. More recently, iterated finite state transducers have been introduced and studied in [START_REF] Kutrib | Descriptional complexity of iterated uniform finite-state transducers[END_REF][START_REF] Kutrib | Descriptional complexity of iterated uniform finite-state transducers[END_REF], transducing variants of stack automata have been considered in [START_REF] Bensch | Deterministic stack transducers[END_REF], two-way transducers with auxiliary memory structures have been investigated in [START_REF] Ibarra | On the containment and equivalence problems for two-way transducers[END_REF] with respect to their decidable problems, and the parallel model of cellular automata has been studied in [START_REF] Kutrib | One-dimensional cellular automaton transducers[END_REF] towards its transducing capabilities.

Reversibility in transducing devices has been investigated recently in [START_REF] Dartois | On reversible transducers[END_REF][START_REF] Kutrib | Transducing reversibly with finite state machines[END_REF] for deterministic finite state transducers (DFSTs). In the former paper, reversible variants of (two-way) DFSTs are introduced where the reversibility of the transition function depends on the input only. Based on this definition the authors present constructions for the composition and uniformization of twoway DFSTs. In the latter paper, reversible DFSTs are defined whose transition function depends on the input and the output, since reversibility here is meant to preserve information both on the input and the output side. Hence, reversible DFSTs may be considered as reversible Turing machines (see, for example, [START_REF] Axelsen | A hierarchy of fast reversible Turing machines[END_REF][START_REF] Bennett | Logical reversibility of computation[END_REF]) with a one-way input tape and a one-way output tape. The main results of [START_REF] Kutrib | Transducing reversibly with finite state machines[END_REF] concern reversible DFSTs with length-preserving transductions where it is differentiated between different modes that basically differ by the fact whether or not input and output head have to move synchronously.

In this paper, we complement the investigation of reversible models by introducing reversible deterministic pushdown transducers for which we study length-preserving transductions in Mealy mode, strong mode, weak mode, and bounded delay mode. The definition of the model and of the different modes, which basically differ in possible distances between the input and output head, are given in Section 2. In Section 3, we study the computational capacity in detail and we can draw a complete picture. It can be shown by a detailed construction that the Mealy mode and the strong mode coincide. However, this holds in the reversible case only and is no longer true for possibly irreversible deterministic pushdown transducers. Apart from this equivalence for all remaining inclusions we present suitable witness transductions that show their properness both in the reversible and the general case. Finally, reversible transductions can be separated from general transductions in every of the four modes. Moreover, we can prove incomparability results in all cases where inclusion cannot be obtained.

Preliminaries

We denote the non-negative integers {0, 1, 2, . . .} by N. Let Σ * denote the set of all words over the finite alphabet Σ, and Σ ≤k denote its restriction to words of length at most k, for any k ≥ 0. The empty word is denoted by λ. The length of a word w is denoted by |w| and its reversal is denoted by w R . For the number of occurrences of a symbol a in w we use the notation |w| a . Inclusions are denoted by ⊆. For convenience, we use S x to denote S ∪ {x}, where S is a set and x is an element not belonging to S.

Next, we define reversible pushdown transducers that are basically deterministic finite state transducers which are equipped with a pushdown store. We define this model as usual with two tapes, namely, an output tape and an input tape whose inscription is the input word followed by an endmarker. In the forward computation the pushdown transducer decides its operation depending on the current state, the current input symbol, and the symbol on top of the pushdown store. It may perform a right or a stationary move on the input tape, may push onto or pop from the pushdown, and may rewrite the current tape square on the output tape which implies a right move of the output head. The output tape is initially filled with blank symbols.

Formally, we define a deterministic pushdown transducer (DPDT) as a system M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F , where Q is the set of internal states, Σ is the set of input symbols not containing the endmarker , Γ is the set of pushdown symbols not containing the bottom-of-pushdown symbol ⊥, ∆ is the set of output symbols not containing the blank symbol , q 0 ∈ Q is the initial state, F ⊆ Q is the set of accepting states, and

δ : Q × Σ × Γ ⊥ → Q × ({pop, top} ∪ { push(x) | x ∈ Γ }) × ∆ × {0, 1}
is the partial transition function. An image (q, op, d, m) is indicating that the DPDT has to enter the state q while performing an action op on the pushdown store (which can be either a pop, a top (that is, do nothing) or a push action), append the symbol d to the output tape if d = (otherwise, the output head stays in position and no output symbol is written) and move the inputhead forward if m = 1 (keep it in current position if m = 0). Such an image is determined deterministically from a pre-image (p, a, g) which indicates that the automaton is currently in state p, reading the input symbol a (which may be the endmarker ) with the symbol g on the top of the pushdown (g = ⊥ if the pushdown store is empty).

It is understood that the head of the input tape never moves beyond the endmarker (that is, a head move m cannot be equal to 1 if the scanned symbol a is ) and that, in any configuration, the bottom-of-pushdown symbol appears exactly once at the bottom of the pushdown store (that is, the pushdown action op is different from pop if the top of the pushdown g is ⊥).

A configuration of a DPDT M is a quintuple (u, p, v, γ, β), where u ∈ Σ * is the already read part of the input to the left of the input head, p ∈ Q is the current state, v ∈ Σ * is the still remaining part of the input, γ ∈ Γ * ⊥ is the current content of the pushdown store, the leftmost symbol being the top symbol, and β ∈ ∆ * is the already written part of the output. The initial configuration for input w is set to (λ, q 0 , w , ⊥, λ). During the course of its computation, M runs through a sequence of configurations. One step from a configuration to its successor configuration, denoted by , is defined as follows.

Let (u, p, av, gγ, β) be a configuration for p ∈ Q, u ∈ Σ * , av ∈ Σ * with |a| = 1, gγ ∈ Γ * ⊥ with |g| = 1, and β ∈ ∆ * . Then we define:

(u, p, av, gγ, β) (ua, q, v, γ γ, βd) if δ(p, a, g) = (q, op, d, 1); (u, p, av, gγ, β) (ua, q, v, γ γ, β) if δ(p, a, g) = (q, op, , 1);
(u, p, av, gγ, β) (u, q, av, γ γ, βd)

if δ(p, a, g) = (q, op, d, 0); (u, p, av, gγ, β) (u, q, av, γ γ, β) if δ(p, a, g) = (q, op, , 0);
where d ∈ ∆ and γ is equal to λ, g or xg respectively if op is equal to pop, top, or push(x) for some x ∈ Γ. The reflexive transitive closure of is denoted by * . A step is said to be stationary if neither the input head is moved nor an output symbol is emitted. A corresponding transition of δ is a stationary transition.

A DPDT halts if the transition function is undefined for the current configuration. The output written by a DPDT M on input w ∈ Σ * is denoted by M (w) ∈ ∆ * and is defined as M (w) = β, if (λ, q 0 , w , ⊥, λ) * (w, q, , γ, β) with γ ∈ Γ * ⊥, q ∈ F , and M halts. Otherwise, M (w) is undefined. Now, the transduction defined by M is the set

T (M ) = { (w, M (w)) | w ∈ Σ * and M (w) is defined } .
We remark that M may also be considered as a partial function mapping some w ∈ Σ * to v ∈ ∆ * . If we build the projection on the first components of T (M ), denoted by L(M ), then the transducer degenerates to a deterministic language acceptor. In general, the family of all transductions performed by some device of type X is denoted by T (X). Now, we turn to reversible DPDTs. Basically, reversibility is meant with respect to the possibility of stepping the computation back and forth. So, the machines have also to be backward deterministic. That is, any configuration must have at most one predecessor which, in addition, is computable by a device of the same type. In particular, the machines reread the symbols which they have read in a preceding forward computation step. So, for reverse computation steps the input and output heads are either moved to the left or stay stationary.

Figuratively, one can imagine that in a forward step, first the current symbols are read and then the heads are moved, whereas in a backward step first the heads are moved and then the symbols are read.

A DPDT is reversible (REV-DPDT) if for any two distinct transitions δ(p, a, g) = (q, op, d, m) and δ(p , a , g ) = (q , op , d , m ) if q = q , then the following conditions are satisfied: (a,d,h) = (a ,d ,h ) where h = g if op = top and h = x if op = push(x) for some x ∈ Γ (respectively h = g if op = top and h = x if op = push(x ) for some x ∈ Γ).

Condition 1 means that transitions reaching the same state have to move both heads in the same way. Condition 2 ensures that for any configuration the predecessor configuration can uniquely be determined from the state (which then implies the head movements), the input symbol read and the output symbol written, if at least one transition pops from the pushdown (Condition 2a). The same is ensured if both transitions push the same symbol while the input symbol read and the output symbol written are the same (Condition 2b). In this case, the predecessor states are identical and the only difference between the transitions might be the symbols g and g on the top of the stack in the pre-image configuration. Finally, the predecessor configuration can uniquely be determined from the state, the input symbol read, the output symbol written, and the symbol on top of the stack (in the image configuration), otherwise (Condition 2c).

A consequence of the definition of reversibility is that any configuration of a REV-DPDT has at most one predecessor configuration. In [START_REF] Kutrib | Reversible pushdown automata[END_REF] reversible pushdown automata are considered that are required to be reversible only on reachable configurations that appear in any computation that starts from an initial configuration. This gives a wider class of automata. However, to justify the notion of reversibility, in [START_REF] Kutrib | Reversible queue automata[END_REF] it has been shown that it makes a difference for machines, that is, there are machines that are reversible on reachable but not on all configurations, but it does not make a difference for languages which notion is chosen. So, from the perspective of languages and language classes it is safe to stick with either notion of reversibility.

In this paper, we start the investigation of reversible DPDTs and limit ourselves to DPDTs that are length-preserving, that is, transducers M such that |w| = |M (w)| for each input w where M (w) is defined. It will turn out that even length-preserving transductions are sufficient for our separations. We differentiate between the following notions. We call a DPDT a Mealy pushdown transducer (M-DPDT) if in every step but possibly a last stationary one on the endmarker an input symbol is read, an output symbol is written, and both heads proceed one position to the right. We call a DPDT strongly length-preserving (s-DPDT) if both heads are moved synchronously, that is, either both move rightward or both stay stationary. A DPDT is said to be of bounded delay (bd-DPDT) if in any configuration (u, p, v , γ, β) that evolves from some initial configuration (λ, q 0 , uv , ⊥, λ) the difference |u| -|β| is bounded by some fixed constant. Finally, unrestricted (length-preserving) DPDTs are said to be weakly length-preserving (w-DPDT).

In order to clarify the definitions we present an example.

Example 1. The injective and length-preserving transduction

τ = (a n #b m #c #a n , a n #b 2 #c m-#a n ) | m, n ≥ 1 and 0 ≤ < m
can be computed by some REV-w-DPDT M = {q 0 , q 1 , q 2 , q 3 , q 4 , q 5 , q f } , {a, b, c, #} , {a, b} , {a, b, c, #} , , ⊥, , δ, q 0 , {q f } where the transition function δ is as follows (see Figure 1): δ(q 0 , a, ⊥) = (q 0 , push(a), a, 1), δ(q 0 , a, a) = (q 0 , push(a), a, 1), δ(q 0 , #, a) = (q 1 , top, , 1), δ(q 1 , b, a) = (q 1 , push(b), , 1), δ(q 1 , b, b) = (q 1 , push(b), , 1), δ(q 1 , #, b) = (q 2 , top, #, 1), δ(q 2 , c, b) = (q 3 , top, b, 0),

δ(q 2 , #, b) = (q 4 , top, #, 0), δ(q 3 , c, b) = (q 2 , pop, b, 1), δ(q 4 , #, b) = (q 4 , pop, c, 0), δ(q 4 , #, a)
= (q 5 , top, #, 1), δ(q 5 , a, a) = (q 5 , pop, a, 1), δ(q 5 , , ⊥) = (q f , top, , 0). The reversibility of M is easily verified by inspecting the transition function and checking the conditions of the definition. In addition, the transduction τ is clearly injective. We note that the projection of τ to the first component is accepted by some reversible pushdown automaton.

q 0 q 1 q 2 q 3 q 4 q 5 q f a, | a,→ push(a) #, a | ,→ top b, | ,→ push(b) #, b | #,→ top c, b | b, ↓ top c, b | b,→ pop #, b | #,→ top #, b | c, ↓ pop #, a | #,→ top a, a | a,→ pop , ⊥ | , ↓ top

Computational Capacity

We turn to consider the computational capacity of reversible DPDTs. In particular, whenever two types of devices have different language acceptance power, then trivial transductions applied to a language from their symmetric difference would be a witness for separating also the power of the transducers. However, in the following we consider transductions of languages that are accepted by both types of devices in question. In this way, we are in fact separating the capabilities of computing transductions.

The Role Played by Stationary Transitions

We start with a normalization result stating that stationary moves can be eliminated in every length-preserving reversible DPDT. To this end, the following lemma is used.

Lemma 2 Every length-preserving reversible DPDT can be converted into an equivalent length-preserving reversible DPDT of the same type that never performs more than m consecutive steps without moving its input head or emitting an output symbol in any halting computation, where m ≥ 0 is a constant.

Proof. Let M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F be a length-preserving reversible DPDT. We show how M can be converted into an equivalent length-preserving reversible DPDT M = Q, Σ, Γ, ∆, , ⊥, , δ , q 0 , F of the same type having the required property. To this end, the transition function δ is modified with respect to stationary transitions as follows.

(1) Two consecutive top-transitions are merged into one. That is, every pair of the form δ(p, a, g) = (q, top, , 0) and δ(q, a, g) = (r, top, , 0) is replaced by δ (p, a, g) = (r, top, , 0). Since M is deterministic every application of the first transition is followed by an application of the second transition, and since M is reversible every application of the second transition is preceded by an application of the first transition. In fact, the conditions for being reversible are satisfied. This can be seen as follows: Let δ (p , a , g ) = (r, op, d , m ) be another transition that yields state r. Then m = 0 and d = since M is reversible. Moreover, if op = pop, then (a, ) = (a , ) since M is reversible. Otherwise, we have (a, , g) = (a , , h ), where h equals g or x, respectively if op = top or op = push(x) for some x. This implies that the transitions δ (p, a, g) = (r, top, , 0) and δ (p , a , g ) = (r, op, d , m ) satisfy the condition for reversibility. So, the construction step preserves reversibility and yields an equivalent automaton.

(2) A push-transition and a following top-transition are merged into one push-transition. That is, every pair of the form δ(p, a, g) = (q, push(x), , 0) and δ(q, a, x) = (r, top, , 0) is replaced by δ (p, a, g) = (r, push(x), , 0). As before, the construction step clearly yields an equivalent automaton and preserves reversibility. Namely, let δ (p , a , g ) = (r, op, d , m ) be another transition that yields state r. Then m = 0 and d = since M is reversible. Moreover, if op = push(x) then (a, , x) = (a , , x) since M is reversible. So, a = a and, trivially, (a, ) = (a , ) implies p = p . If op = pop then (a, ) = (a , ) since M is reversible. Thus, a = a . If op = top then (a, , x) = (a , , g ) since M is reversible. Similarly, if op = push(y) then (a, , x) = (a , , y). So, in any case for op the transitions δ (p, a, g) = (r, push(x), , 0) and δ (p , a , g ) = (r, op, d , m ) satisfy the condition for reversibility.

(3) A push-transition and a following pop-transition are merged into one top-transition. That is, every pair of the form δ(p, a, g) = (q, push(x), , 0) and δ(q, a, x) = (r, pop, , 0) is replaced by δ (p, a, g) = (r, top, , 0). To see that the new transition preserves reversibility we assume that there is another transition δ (p , a , g ) = (r, op, d , m ). As before, we conclude m = 0 and d = since M is reversible. Moreover, since δ(q, a, x) is a pop-transition, we know (a, ) = (a , ) since M is reversible. Thus, a = a , and the transitions δ (p, a, g) = (r, top, , 0) and δ (p , a , g ) = (r, op, d , m ) satisfy the condition for reversibility.

Next, the three steps are repeated until no more merging is possible, which concludes the construction of M .

It remains to be shown that there is a constant m ≥ 0 such that the REV-DPDT M never performs more than m consecutive steps without moving its input head or emitting an output symbol in any halting computation.

Due to the construction, any sequence of consecutive stationary transitions in any computation of M possibly starts with a sequence of pop-and top-moves, where no two top-moves appear consecutively. Then several push-moves may follow. After a push-move there is never a pop-or top-move.

Assume that there is a computation on some input such that at the beginning of a sequence of stationary transitions on some input symbol a ∈ Σ at least |Q| • |Γ| + 1 consecutive pop-or top-moves are performed. If these steps appear before any non-stationary transition, M starts each computation with an infinite loop on input aΣ * or and, thus, does not halt.

Next, assume that at least |Q| • |Γ| + 1 consecutive pop-or topmoves appear after some non-stationary transition and define the mapping

ρ : Σ * × Q × Σ * × Γ * ⊥ × ∆ * → Q × Γ ⊥ that
maps a configuration to its state and the topmost pushdown symbol. Then there is a (partial) computation

c k-1 c k * c k+i * c k+i+j-1 c k+i+j ,
where the transition from c k-1 to c k reads some input and moves the input head and all the other transitions are stationary. Moreover, we have ρ(c k+i ) = ρ(c k+i+j ), for some minimal 0 ≤ i, 1 ≤ j such that i + j ≤ |Q| • |Γ| + 1. Then, for i = 0, the transition leading from c k-1 to c k yields the same state as the transition leading from c k+j-1 to c k+j . However, the former moves the input head while the latter does not. So, the computation is not reversible.

For i ≥ 1 we know that ρ(c k+i-1 ) and ρ(c k+i+j-1 ) are different since i has been chosen to be minimal. Let (q, x) = ρ(c k+i ) = ρ(c k+i+j ) and assume that δ (p, a, g) = (q, op, , 0) is the transition leading from c k+i-1 to c k+i and δ (p , a, g ) = (q, op , , 0) is the transition leading from c k+i+j-1 to c k+i+j . By assumption, op and op are either pop-or top-transitions. If one of them is a pop-transition then (a, ) has to be different from (a, ) in order to be reversible, a contradiction. If both transitions are top-transitions (a, , g) has to be different from (a, , g ). However, since both transitions are top-transitions we have g = x = g , a contradiction.

Therefore, any sequence of consecutive stationary transitions starts with at most |Q| • |Γ| pop-or top-moves. If there are at least |Q| • |Γ| + 1 subsequent push-moves, the computation runs into an infinite loop with stationary transitions and, thus, M does not halt. If, otherwise, there are strictly less than |Q| • |Γ| + 1 push-moves, the length of the whole sequence of stationary transitions is bounded by the constant m = 2 • |Q| • |Γ| that depends on M only.

The next goal is to perform all constantly many stationary transitions in a sequence together with a non-stationary transition at once. To this end, the problem that the initial state can be reachable in stationary moves has to be overcome. Otherwise, the reversibility can not be guaranteed since the initial configuration and some configuration that leads to the initial configuration may have a common successor configuration.

Lemma 3 Every length-preserving reversible DPDT whose initial state is reachable by stationary transitions can be converted into an equivalent lengthpreserving reversible DPDT of the same type that never performs more than m consecutive stationary moves in any halting computation, where m ≥ 0 is a constant, and that never enters an initial configuration again.

Proof. Let M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F be a length-preserving reversible DPDT. By Lemma 2 we may assume that M satisfies the first condition. Since M is reversible an inspection of the transition function shows whether q 0 is reachable by stationary transitions. If not, nothing has to be done. Now assume that q 0 is reachable by stationary transitions. Due to the reversibility, it is reachable only by stationary transitions. The idea of the construction of an equivalent length-preserving reversible DPDT of the same type M = Q ∪ {p 0 }, Σ, Γ ∪ { }, ∆, , ⊥, , δ , p 0 , F with the required second property is as follows. A new pushdown symbol is used that acts similar as the bottom-of-pushdown symbol. Whenever the initial state is entered by a top or pop transition, now a new state p 0 is entered that tests if the pushdown is 'empty'. If so, it pushes a new copy of and changes to state q 0 . In this way, the initial configuration at the beginning of the computation is unique since it is the only one with ⊥ on the top of the pushdown. Accordingly, the transition function δ is modified as follows.

First, in all transitions the bottom-of-pushdown symbol is replaced by . This preserves the reversibility. Next, it is observed that, for any input symbol a, transitions of the form δ(p, a, g) = (q 0 , top, , 0) and transitions of the form δ(p, a, g) = (q 0 , pop, , 0) cannot exist at the same time. If both types would exist, the fact (a, ) = (a, ) would violate the reversibility. Now the new initial state p 0 is involved by adding the transitions (1) δ (p 0 , a, ⊥) = (q 0 , push( ), , 0), (2) δ (p 0 , a, ) = (q 0 , push( ), , 0), and (3) δ (p 0 , a, g) = (q 0 , top, , 0), for all a ∈ Σ and g ∈ Γ. Transitions of the form δ(p, a, ) = (q 0 , top, , 0) are replaced by (4) δ (p, a, ) = (p 0 , top, , 0), and transitions of the form δ(p, a, g) = (q 0 , pop, , 0) are replaced by ( 5) δ (p, a, g) = (p 0 , pop, , 0) (recall that only transitions of one of the forms may exist).

The construction clearly does neither change the transduction computed, nor does it change the type of the transducer. It remains to be shown that the construction preserves reversibility. Transitions (1) and ( 2) are reversible since the predecessor state is p 0 in both cases. Since = g, transitions (1) and ( 3) are reversible, as well as transitions ( 2) and (3). Further transitions entering state q 0 must be push-transitions that push symbols different from ⊥ and . So, the reversibility is preserved with respect to these transitions as well. The transitions entering state p 0 , namely transitions of the form (4) or [START_REF] Kondacs | On the power of quantum finite state automata[END_REF], are present in δ where they enter state q 0 . Since M is reversible, the modified transitions do not violate the reversibility either. We conclude that M satisfies the required properties, is equivalent to M , and is of the same type as M .

To conclude the consideration of stationary transitions we present the result that every length-preserving reversible DPDT can be transformed into an equivalent reversible one that moves at least one head in every but possibly the last step of a computation. The basic idea of the proof of the next proposition is to simulate a possibly empty sequence of stationary transitions and one following non-stationary transition at once. Proposition 4 Every length-preserving reversible DPDT can be converted into an equivalent length-preserving reversible DPDT of the same type that always halts and moves its input head or emits an output symbol in every but possibly the last step of a computation.

Proof. Let M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F be a REV-DPDT. By Lemma 3 we may assume that M performs at most m consecutive stationary transitions in any halting computation, where m is a constant, and that never enters an initial configuration again.

Since M is reversible, any state is reached solely by stationary transitions or solely by non-stationary transitions. To figure out which case applies to a certain state it is sufficient to inspect the transition function. Moreover, to check whether a sequence of stationary transitions starting from a given configuration is finite, we have to simulate at most m + 1 steps of M .

In order to construct an equivalent length-preserving reversible DPDT of the same type with the properties claimed, basically, the idea is to simulate a possibly empty sequence of stationary transitions and one following non-stationary transition at once. If M runs into an infinite loop of stationary transitions or performs stationary transitions on the endmarker, then the sequence of stationary transitions is simulated without a following non-stationary transition.

The DPDT M = Q , Σ, Γ , ∆, , ⊥, , δ , q 0 , F is constructed as follows. Recall that M simulates at most some m + 1 steps of M at once during which it has access to no more than the topmost m + 1 pushdown symbols. On the other hand, it cannot push more than m + 1 symbols onto the store. So, we add a register to the states in which M can store up to 2m pushdown symbols of M (the topmost ones), and consider every string of m + 1 pushdown symbols of M to be a single pushdown symbol of M . Let F + = { q + | q ∈ F } be a copy of F . Then define

Q = (Q ∪ F + ) × Γ ≤2m , Γ = Γ m+1 , q 0 = (q 0 , λ), F = (F ∪ F + ) × Γ ≤2m . Given (p, x i x i-1 • • • x 1 ) ∈ Q×Γ ≤2m , a ∈ Σ , and z m+1 z m • • • z 1 ∈ Γ , the transi- tion δ ((p, x i x i-1 • • • x 1 ), a, z m+1 z m • • • z 1
) is defined if and only if p is reached by non-stationary transitions in M . In this case, it is defined by the computation of M starting in configuration c 0 = (λ, p, a,

x i x i-1 • • • x 1 z m+1 z m • • • z 1 , λ).
First assume that the computation starts with a possibly empty sequence of stationary transitions followed by a non-stationary transition. That is, the computation is c 0 c 1 • • • c n , where n ≤ m + 1. We distinguish two cases: If the last step moves the input head we have c n = (a, q, λ, y j y j-1

• • • y 1 , d) and define δ ((p, x i x i-1 • • • x 1 ), a, z m+1 z m • • • z 1 ) = ((q, γ), op, d ,
γ = y j y j-1 • • • y 1 , op = pop if 0 ≤ j ≤ 2m, γ = y j y j-1 • • • y m+2 , op = top if 2m + 1 ≤ j ≤ 3m + 1, γ = y j y j-1 • • • y 2m+3 , op = push(y 2m+2 • • • y m+2 ) if 3m + 2 ≤ j ≤ 4m + 2.
Note that in the second and third alternatives, M could not modify the symbols

z m+1 z m • • • z 1 and, therefore, y m+1 y m • • • y 1 = z m+1 z m • • • z 1 .
The second case is similar. If the last step emits an output symbol without moving the input head we have c n = (λ, q, a, y j y j-1

• • • y 1 , d) with d ∈ ∆ and define δ ((p, x i x i-1 • • • x 1 ), a, z m+1 z m • • • z 1 ) = ((q, γ), op, d, 0)
, where γ and op are as for the first case.

Next, assume that the computation of M starts with a sequence of stationary transitions and halts without performing a non-stationary transition. Then we have c n = (λ, q, a, y j y j-1

• • • y 1 , λ) and δ ((p, x i x i-1 • • • x 1 ), a, z m+1 z m • • • z 1 ) re- mains undefined for a = or q / ∈ F . If a = and q ∈ F we define the transition δ ((p, x i x i-1 • • • x 1 ), , z m+1 z m • • • z 1 ) = ((q + , x i x i-1 • • • x 1 ), top, , 0).
Finally, if the computation of M is an infinite sequence of stationary transitions then δ ((p,

x i x i-1 • • • x 1 ), a, z m+1 z m • • • z 1 )
remains undefined. Moreover, the transition function δ remains undefined for states whose first component belongs to F + .

If the initial state q 0 of M is reached by non-stationary moves, the initial configuration of M does not need to be treated in any special way. However, if q 0 is reached by stationary moves, we proceed as follows. First, all transitions of δ defined so far are checked whether they are based on a computation c 0 c 1 • • • c n of M that includes an initial configuration. If yes, the transition is undefined again. This can safely be done since by assumption the initial configuration only appears at the beginning of any computation of M . Next, the transition δ ((q 0 , λ), a, ⊥) is defined as above, for any input symbol a.

Finally, the completion of the definition of δ for the situations in which the bottom-of-pushdown symbol is the topmost symbol is straightforward. This concludes the construction of M .

Given an input w, the computation of M is unambiguously split into sequences of steps each of which is performed by M at once. If M accepts, so does M . Conversely, every step of M corresponds to a sequence of steps of M . So, we have T (M ) = T (M ).

To give evidence that M is reversible we argue with configurations. Except for possibly the initial configuration and halting configurations on the endmarker, any configuration of M includes a state of M that is reachable with non-stationary moves. The unique predecessor configuration is determined by running M backwards until either the initial configuration appears or another configuration with a state of M that is reachable with non-stationary moves is reached. So, the reversibility of M follows from the reversibility of M . Since by assumption the initial configuration of M never occurs again, also the steps involving the initial configuration of M are reversible. Finally, also the configurations including states from F + have a unique predecessor that can be determined by running M backwards as above.

In particular, the normalization result eliminates stationary moves from reversible computations. This implies the first comparison between families under consideration.

Theorem 5 The families T (REV-M-DPDT) and T (REV-s-DPDT) coincide.

Proof. The inclusion T (REV-M-DPDT) ⊆ T (REV-s-DPDT) follows from the definition. Conversely, applying Proposition 4 to a given REV-s-DPDT yields a REV-M-DPDT. We conclude T (REV-M-DPDT) ⊇ T (REV-s-DPDT) and, thus, T (REV-M-DPDT) = T (REV-s-DPDT).

However, the equivalence of both transduction families gets lost if irreversible computations are allowed.

Theorem 6 There is a strict inclusion between the families T (M-DPDT) and T (s-DPDT).

Proof. The inclusion T (M-DPDT) ⊆ T (s-DPDT) follows from the definition.

To define the transduction that witnesses the properness of the inclusion we first consider the function f : {a, b} + × {a, b} + → {a, b, c} + which is defined by

f (x 1 x 2 • • • x n , y 1 y 2 • • • y m ) = x n x n-1 • • • x n-m+1 if m < n, x n x n-1 • • • x 1 c m-n if m ≥ n.

Bounded Delay versus Strongly Length-Preserving

We turn to examine the computational capacity gained in the possibility of having the input head and output head asynchronous but not too far from each other. Their distance has to be bounded by a constant. For any alphabet Σ with a ∈ Σ and such that |Σ| ≥ 2, we consider the witness transduction lRotate = { (aw, wa) | w ∈ Σ * }.

Proposition 7

The transduction lRotate is realized by a REV-bd-DPDT.

Proof. We first informally describe a bd-DPDT T realizing lRotate. Actually T does not use the pushdown, it is basically the identity transducer (one state with self-loops on every input letter copying this letter to the output) to which a preliminary step (from the initial state) and a final step (to the unique final state) are added: from the initial state reading the input letter a, the transducer enters the central looping state without producing an output symbol and moves its input head; symmetrically, from the central looping state reading the endmarker, the transducer enters the unique final state and emits the output symbol a.

Next, we transform T into a REV-bd-DPDT without changing the delay. First, the self-loops are divided into two steps, in order to satisfy the head move constraints required by the definition of reversibility [START_REF] Guillon | Reversible pushdown transducers[END_REF]. Second, we use the pushdown to save information about the history of the computation, namely, the pushdown contains the number of times the loops have been taken (in unary). In this way, in a backward computation, the device is able to detect the first time the central strongly connected component was entered.

Formally, we define the REV-bd-DPDT T as follows (see Figure 2):

T = {q, s, t, f } , Σ, {a} , ∆, , ⊥, , δ, q, {f }
where the alphabets Σ and ∆ are equal and contain the symbol a, and, for all σ ∈ Σ, the transition function δ is defined by: δ(q, a, ⊥) = (s, top, , 1) δ(s, σ, a) = δ(s, σ, ⊥) = (t, top, σ, 0) δ(t, σ, a) = δ(t, σ, ⊥) = (s, push(a), , 1) δ(s, , a) = δ(s, , ⊥) = (f, top, a, 0)

The next result yields the separation. The transduction lRotate is not even realized by an irreversible s-DPDT.

Proposition 8

The transduction lRotate cannot be realized by any s-DPDT.

Proof. By contradiction, assume that lRotate is realized by some s-DPDT T . Suppose that in the successful computation of T on input ab, the first nonstationary step is δ(p, a, g) = (q, op, d, 1), for some states p and q, g ∈ Γ ⊥ , and d ∈ ∆ . Since T is strongly length-preserving, we have d = and furthermore d is the first symbol emitted. So, d = b, since the output associated to ab is ba. Since T is deterministic, a computation on input aa will have the same first non-stationary step and, therefore, a b is emitted during the computation. This is a contradiction since the output aa associated to the input aa does not contain the symbol b.

Since the two inclusions T (REV-s-DPDT) ⊆ T (REV-bd-DPDT) and T (s-DPDT) ⊆ T (bd-DPDT) follow from the definitions, Propositions 7 and 8 imply the following separations.

Theorem 9 The family T (REV-bd-DPDT) strictly includes the family T (REV-s-DPDT), and the family T (bd-DPDT) strictly includes the family T (s-DPDT).

Weakly Length-Preserving versus Bounded Delay

The most powerful variant of length-preserving transducers works weakly length-preserving, where now the distance between input head and output head may be arbitrary. We first show this yields strictly more computational capacity. To this end, we use the transduction

mSwap = { (a m #b n , b n #a m ) | m, n ≥ 0 }.

Proposition 10

The transduction mSwap is realized by a REV-w-DPDT.

Proof. The transduction mSwap is realized by the REV-w-DPDT M depicted in Figure 3 whose state set is {q, s, t, f }, where q is the initial state and f is the sole final state. The transducer M uses only one pushdown symbol, denoted a, meaning that it can be viewed as a counter transducer. The transition function δ of M is defined as follows:

δ(q, a, ⊥) = δ(q, a, a) = (q, push(a), , 1)

δ(q, #, ⊥) = δ(q, #, a) = (s, top, , 1) δ(s, b, ⊥) = δ(s, b, a) = (t, top, b, 0) δ(t, b, ⊥) = δ(t, b, a) = (s, top, , 1) δ(s, , ⊥) = δ(s, , a) = (f, top, #, 0) δ(f, , a) = (f, pop, a, 0)
So defined, the transducer M realizes mSwap. In fact, in any successful computation on some input word a m #b n , m, n ≥ 0, when the transducer performs the transition from q to s, the configuration becomes (a m #, s, b n , a m ⊥, λ). Similarly, when it performs the transition from s to f , the configuration becomes (a m #b n , f, , a m ⊥, b n #). Finally, since transducers are required to halt in order to accept, M has to perform the self-loop around f until having emptied the pushdown. Hence, when it halts, the configuration is (a m #b n , f, , ⊥, b n #a m ). For every such input word, the successful computation described above exists. Thus, R realizes the transduction mSwap. Moreover, it is immediately verified that R is reversible.

The next result yields the separation: the transduction mSwap is not even realized by an irreversible bd-DPDT.

Proposition 11

The transduction mSwap is not realizable by any bd-DPDT.

Proof. By contradiction, suppose that a bd-DPDT T realizes mSwap, and let the delay be bounded by some k ≥ 0. Consider the input words in a k+1 #b * , which are all valid inputs for the transduction. On each of these words, by the determinism of T , when the input head reaches the (k + 1)st symbol a at least one symbol of the output has been written (otherwise, the output head is more than k cells delayed). If the first output letter produced so far is a or #, we get a contradiction for the input a k+1 #b whose associated output begins by b. If it is b, then we get a contradiction for the input word a k+1 #, whose associated output begins by #. Hence, no bd-DPDT realizes mSwap.

Since the two inclusions T (REV-bd-DPDT) ⊆ T (REV-w-DPDT) and T (bd-DPDT) ⊆ T (w-DPDT) follow from the definitions, Propositions 10 and 11 imply the following separations.

Theorem 12

The family T (REV-w-DPDT) strictly includes the family T (REV-bd-DPDT), and the family T (w-DPDT) strictly includes the family T (bd-DPDT).

Irreversibility versus Reversibility

In the previous sections we have established the finite hierarchies dependent on the modes of transductions for reversible as well as general devices. Here we compare the computational capacities of general and reversible classes with each other. A witness transduction is

aOccur = { (a n #w#a n , a n #a |w| #a n ) | n ≥ 0, w ∈ {a, b} + , |w| a ≥ 1 }.
It is not hard to see that aOccur is realized even by the weakest not necessarily reversible device in question, that is, by some M-DPDT. However, even reversible pushdown transducers with bounded delay cannot realize it.

Proposition 13

The transduction aOccur cannot be realized by any reversible bounded-delay pushdown transducer.

Proof. Assume that a REV-bd-DPDT M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F realizes aOccur, and let the delay be bounded by some k ≥ 0. By Proposition 4 we may safely assume that M always halts and never performs a stationary move in every but possibly the last step of a computation. First, we look at the initial parts of the computations on input prefixes a n , where n is large enough, and we want to show that the pushdown contents have to be different after the processing of infinitely many different prefixes a n . By contradiction, we assume that there are only a finite number of pushdown contents that appear after processing the prefixes a n , for all n ≥ 0. Since the delay is bounded, there are only finitely many possible delays. The number of states is finite as well. So, there must be two numbers n 1 and n 2 such that the delay of the output head, the current state, and the pushdown contents are identical after processing a n1 and a n2 . Then, for the suffix #a#a n1 both computations would continue successfully. From this contradiction we conclude that the pushdown contents have to be different after the processing of infinitely many different prefixes a n .

We conclude that the pushdown height grows with n. Therefore, M eventually runs through cycles that increase the pushdown height, say, (λ, q 0 , a n #, ⊥, λ) * (a i , q, a n-i #, γ 0 , β 0 ) * (a i+j , q, a n-i-j #, γ 1 γ 0 , β 0 β 1 ) * (a i+2j , q, a n-i-2j #, γ 1 γ 1 γ 0 , β 0 β 1 β 1 ), for j > 0 and γ 1 = λ. Here, we may safely assume that M moves its input head when it enters the state q. On prefixes a n with n from the set

N = { i + xj | x ≥ 0 } the transducer M runs through complete cycles.
Second, we look at the computations on the input factors between the # symbols. To this end, we choose some fixed number m ≥ k + 1, only numbers n from the set N , and let ≥ 1 be large enough. Then we consider factors (b m a) whose processing starts in configurations (a n , q, #(b m a) , γ, β) where γ is of the form γ * 1 γ 0 . Since the computations are on cyclic input factors (b m a) * and start with cyclic topmost pushdown contents γ * 1 , the computations themselves will be cyclic. We can always unroll the cycle such that it matches the b m a blocks. That is,

(a n , q, #(b m a) , γ, β) * (a n #(b m a) i , p, (b m a) -i , γ 0 , β 0 ) * (a n #(b m a) i+j , p, (b m a) -i-j , γ 1 , β 1 )
We now want to obtain that the pushdown height during a cycle on the input factor between the # symbols remains constant. To this end, we show by way of contradiction that the pushdown height neither decreases nor increases during such a cycle. For the first case, we assume that the pushdown height decreases during such a cycle, that is,

|γ 2 | < |γ 1 | < |γ 0 | and γ 1 = γγ x
1 γ 0 , γ 2 = γγ y 1 γ 0 with y < x. Then there are two numbers n 1 < n 2 from the set N , two numbers r 1 < r 2 , and two numbers s 1 , s 2 ≥ 1 such that

(a n1 , q, #(b m a) , γ, β) * (a n1 #(b m a) i+r1j , p, (b m a) -i-r1j , γγ x 1 γ 0 , a n1 #a s1 ) and (a n2 , q, #(b m a) , γ, β) * (a n2 #(b m a) i+r2j , p, (b m a) -i-r2j , γγ x 1 γ 0 , a n2 #a s2 ).
This implies the halting computation

(a n1 , q, #(b m a) -(r2-r1)j #a n2 , γ, β) * (a n1 #(b m a) i+r1j , p, (b m a) -i-r2j #a n2 , γγ x 1 γ 0 , a n1 #a s1 ) * (a n1 #(b m a) -(r2-r1)j #a n2 , p + , , γ f , a n1 #a s #a n2 )
for some accepting state p + and some s ≥ 1. We conclude from the contradiction that the pushdown height does not decrease during a cycle on the input factor between the # symbols.

For the second case, we assume that the pushdown height increases during such a cycle, that is,

|γ 2 | > |γ 1 | > |γ 0 | and γ 1 = γ 2 γγ x 1 γ 0 , γ 2 = γ 1+z 2
γγ y 1 γ 0 with z ≥ 1. Then there are two numbers n 1 < n 2 from the set N (recall that is large enough), a number r ≥ 0, two numbers x 1 , x 2 ≥ 1, and two numbers

s 1 , s 2 ≥ 1 such that (a n1 , q, #(b m a) , γ, β) * (a n1 #(b m a) i+rj , p, (b m a) -i-rj , γ t 2 γγ x1 1 γ 0 , a n1 #a s1 ) and (a n2 , q, #(b m a) , γ, β) * (a n2 #(b m a) i+rj , p, (b m a) -i-rj , γ t 2 γγ x2 1 γ 0 , a n2 #a s2 ),
where we safely may assume t > 2(n 2 + 2) + k, since r can be large enough since is large enough. Since M does not perform stationary moves, on input a n1 #(b m a) i+rj #a n2 there are at most 2(n 2 + 2) + k steps left until the end of the computation. During these steps at most the topmost t pushdown symbols can be accessed. So, as before, we derive a contradiction since there is a successful computation with prefix a n1 # and suffix #a n2 . We conclude that the pushdown height also does not increase during a cycle on the input factor between the # symbols, that is, it remains constant in a cycle. So, we have γ 1 = γγ x 1 γ 0 = γ 2 . Finally, we consider the configurations when M moves its input head on an a in the factor between the # symbols.

Eventually, this happens within the cycle:

(a n #b m , p 1 , a(b m a) -1 , γ, β) * (a n #(b m a) i b m , p 2 , a(b m a) -i-1 , γ0 , β0 ) * (a n #(b m a) i+j b m , p 2 , a(b m a) -i-j-1 , γ0 , β1 ) * (a n #(b m a) i+ij b m , p 2 , a(b m a) -i-ij-1 , γ0 , β2 ).
Since M is reversible, from the second configuration we uniquely can run it backwards for i(m + 1) steps in which the input head is moved. This yields the configuration (a n #b m , p 1 , a(b m a) -1 , γ, β). Since M is of bounded delay, the suffixes of β0 and β2 are of the form a + and are long enough. Therefore, running M backwards for i(m + 1) steps in which the input head is moved from the fourth configuration, must be the same backwards computation as running backwards from the second configuration. So, running backwards from the fourth configuration yields (

a n #(b m a) ij b m , p 1 , a(b m a) -ij-1 , γ, β3
) and, thus, p 1 appears in the cycle. Since a n #(b m a) ij b m #a n is successfully transduced so is a n #b m #a n , a contradiction. We conclude that the transduction aOccur is not realized by any reversible bounded-delay pushdown transducer.

Since any reversible transducer is a special case of a general one of the same type and the transduction aOccur is realized by an M-DPDT, we have the following inclusions. To compare the transducers working in weak mode, we use a variant of the transduction mSwap without center marker, that is, we define the transduction

Swap = { (a m b n , b n a m ) | m, n ≥ 0 }.

Proposition 15

The transduction Swap is realized by a w-DPDT.

Proof. A w-DPDT realizing Swap starts to read the leading a's and stores them onto the pushdown without emitting symbols. Then it reads and emits the following b's without changing the pushdown content. Finally, on the endmarker it emits the a's from the pushdown. A precise construction is shown in Figure 4.

We can show that the transduction swap is not realizable by a reversible transducer.

Proposition 16

The transduction swap cannot be realized by any reversible pushdown transducer.

Proof. In contrast to the assertion, assume that there exists a REV-w-DPDT M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F which realizes Swap. By Proposition 4 we may safely assume that M always halts and never performs a stationary move in every but possibly the last step of a computation. Later we modify M and have to preserve reversibility. In order to simplify matters concerning this possibly last step on the endmarker, we do the following. Let F be the primed copy of F . Then we add F to the state set of M and exchange F by F . Whenever δ(p, , g) is undefined, state p belongs to F , and state p is reached by a non-stationary transition, we define δ(p, , g) = (p , top, , 0). Whenever δ(q, , g) = (p, op, , 0) is defined and state p belongs to F , we redefine δ(q, , g) = (p , op, , 0). In the former case we have added one stationary transition that becomes the last transition in a successful computation which previously ended with a non-stationary step. In the latter case we have replaced the stationary last step in a successful computation by a stationary transition that leads to a primed copy of the accepting state. Since there are no outgoing transitions from the new final states from F , this modification neither violates the reversibility nor the transduction realized.

After this preparation, we observe that the transitions performed during any successful computation of M satisfy:

δ(p, a, g) = (q, op, d, m) =⇒ d = (1) δ(p, b, g) = (q, op, d, m) =⇒ d = a (2)
δ(p, x, g) = (q, op, a, m) =⇒ x =

where p, q are states, g ∈ Γ ⊥ , m ∈ {0, 1}, and d ∈ {a, b} . Indeed, if M would not satisfy (1) then it would fail, since it might produce a symbol before having checked the existence of a symbol b in the suffix of the input. Similarly, M would fail if it does not satisfy (2) because it might emit a symbol a before having completely emitted the b's, which should form a prefix of the output. Lastly, (3) is implied by ( 1) and ( 2). Next, we turn to show how to obtain a reversible pushdown automaton A that accepts the language { a n b n | n ≥ 0 } from M . Since no reversible pushdown automaton can recognize this language [10, Lemma 6], we obtain a contradiction that shows the theorem.

The first step of the construction of A is to modify M such that it only accepts inputs from a * while preserving all the properties seen above as well as reversibility. To this end, it is sufficient to remove every transition reading or emitting a b from δ. By the properties above there is no transition that reads an a and emits a b or vice versa. So, this construction step can safely be done without changing anything for the computations on inputs from a * . Let M be the transducer obtained in this way. It is reversible, since we only removed transitions from M . Moreover, its transitions still satisfy the three conditions given above.

In particular, on input a * transducer M first reads the a's without emitting anything. When the endmarker is reached, M emits the a's read and halts in an accepting state from F . The next step is to construct the reversible pushdown automaton A = Q, {a, b}, Γ, , ⊥, δ , q 0 , F from M . The transition function δ is defined as follows:

δ (p, a, g) = (q, op, 1) ⇐⇒ δ(p, a, g) = (q, op, , 1) δ (p, b, g) = (q, op, 1) ⇐⇒ δ(p, , g) = (q, op, a, 0) δ (p, , g) = (q, op, 0) ⇐⇒ δ(p, , g) = (q, op, , 0) for each p, q ∈ Q, g ∈ Γ ⊥ , and op ∈ {push(x) | x ∈ Γ} ∪ {top, pop}.

In this way, A simulates M , but whenever M emits an a while reading the endmarker, A reads a b. So, for each successful transduction of M on an input a n , we obtain an accepting computation of A on input a n b n , and vice versa. Hence, A accepts the language { a n b n | n ≥ 0 }.

Finally, it is not hard to verify that A is reversible since M is reversible and the construction of δ does not violate reversibility.

It is worth mentioning that A moves its input head in any but a possible last step on the endmarker. The pushdown automata considered in [START_REF] Kutrib | Reversible pushdown automata[END_REF] do not have an input endmarker. However, the proof that the language { a n b n | n ≥ 0 } is not accepted by any reversible pushdown automaton does not rely on the endmarker. It literally applies in this case as well.

So, we have shown the following theorem.

Theorem 17 The family T (w-DPDT) strictly includes T (REV-w-DPDT).

The next goal is to develop a witness transduction that shows the missing incomparability results, that is, it should be realizable by some M-DPDT but not by any REV-w-DPDT. To this end, let L bin = ((aa+a)(bb+b)) * (aa+a+λ) be a regular language and define the transduction

3Occur = { (a n #w#a n , a n #a |w| #a n ) | n ≥ 0, w ∈ L bin }.
As for the transduction aOccur it is not hard to see that 3Occur is realized by the weakest not necessarily reversible device in question, that is, by some M-DPDT. In order to show that 3Occur cannot be realized by any REV-w-DPDT we will use Kolmogorov complexity and incompressibility arguments. General information on Kolmogorov complexity and the incompressibility method can be found, for example, in [START_REF] Li | An Introduction to Kolmogorov Complexity and Its Applications[END_REF]. Let w ∈ {0, 1} + be an arbitrary binary string. The Kolmogorov complexity C(w) of w is defined to be the minimal size of a binary program describing w. The following key argument for the incompressibility method is well known. There are binary strings w of any length so that |w| ≤ C(w).

Next, we encode words w ∈ {0, 1} + as follows. From left to right the digits are represented alternating by a's and b's so that a 0 is represented by a single letter and a 1 by a double letter. For example, the word 010110 is encoded as abbabbaab. Let t(w) denote the code of w. Clearly, for any word w ∈ {0, 1} + , its code t(w) belongs to the regular language L bin .

Proposition 18 There exists no REV-w-DPDT that realizes the transduction 3Occur.

Proof. In contrast to the assertion, assume that there exists a REV-w-DPDT M = Q, Σ, Γ, ∆, , ⊥, , δ, q 0 , F which realizes 3Occur. By Proposition 4 we may safely assume that M always halts and never performs a stationary move in every but possibly the last step of a computation.

First, we consider successful computations of M on input prefixes a n , where n is large enough. On these input prefixes, no combination of state and pushdown content may appear twice. If otherwise

(λ, q 0 , a n #w#a n , ⊥, λ) * (a m1 , q 1 , a n-m1 #w#a n , γ 1 , β 1 ) + (a m1+m2 , q 1 , a n-m1-m2 #w#a n , γ 1 , β 2 )
is the beginning of a successful computation, then so is (λ, q 0 , a n-m2 #w#a n , ⊥, λ) * (a m1 , q 1 , a n-m1-m2 #w#a n , γ 1 , β 1 ), but there is no pair in 3Occur whose first component is a n-m2 #w#a n , a contradiction.

We conclude that the pushdown height grows with n. Therefore, M eventually runs through cycles that increase the pushdown height, say, (λ, q 0 , a n #, ⊥, λ) * (a t1 , q 1 , a n-t1 #, γ 1 , β 1 ) + (a t1+c1 , q 1 , a n-t1-c1 #, γ 2 γ 1 , β 2 ) + (a t1+2c1 , q 1 , a n-t1-2c1 #, γ 2 γ 2 γ 1 , β 3 ), for t 1 ≥ 0, c 1 > 0, and γ 2 = λ. Next, we turn to the input suffixes. For all n ≥ 0, we define the mapping h n : {a, b} * → N as follows. If on input a n #w#a n the pushdown content of M after processing the prefix a n # is γ then h n maps w to the number of symbols at the bottom of the pushdown that are no more seen in the remaining computation on suffix w#a n . Clearly, if all symbols from γ are touched during the remaining computation then h n maps to zero.

We now want the show that h n (w) < |γ 2 γ 1 | for all n large enough and all w ∈ L bin . By contradiction, we assume that for some n large enough there exists a w ∈ L bin such that h

n (w) ≥ |γ 2 γ 1 |. Since the computation (λ, q 0 , a n #w#a n , ⊥, λ) * (a t1+c1 , q 1 , a n-t1-c1 #w#a n , γ 2 γ 1 , β 2 ) * (a n #w#a n , q f , , γ, β) is successful and h n (w) ≥ |γ 2 γ 1 |, the computation (λ, q 0 , a n+c1 #w#a n , ⊥, λ) * (a t1+c1 , q 1 , a n-t1 #w#a n , γ 2 γ 1 , β 2 ) * (a t1+2c1 , q 1 , a n-t1-c1 #w#a n , γ 2 γ 2 γ 1 , β 3 ) * (a n+c1 #w#a n , q f , , γ, β )
is successful as well, a contradiction. We conclude that, for all n large enough and all w ∈ L bin , h n (w) < |γ 2 γ 1 |. The next step is to show that there is some constant k such that the value of h n (w) is reached for the last time, that is, the height of the pushdown is h n (w) for the last time, when the input head is scanning one of the last k input symbols. By way of contradiction, we distinguish two cases, namely, the input head is scanning some symbol of the factor w# or the input head is scanning some symbol a of the suffix a n and the distance to the end of input is larger than k. In the first case, we assume that the input head is scanning some symbol of the factor w#, say in a configuration (a n #u, p 1 , v#a n , γ, β), where w = uv and |γ| = h n (w). Note that the computation continues from this configuration successfully and, by definition, u belongs to L bin . We consider the input a n #u#a n and, thus, the computation continuing in configuration (a n #u, p 1 , #a n , γ, β). Assume the configuration after the next move of the input head is (a n #u#, p 2 , a n , γ , β ). We derive |γ | ≤ h n (w) + 1. Since the remaining computation is on unary input a n , a rough estimation gives that there are at most |Γ| |γ | • |Q| different possibilities for the topmost |γ | pushdown symbols and a state. Since n has been chosen large enough, the computation continues in cycles with respect to the state and the topmost |γ | pushdown symbols. The maximal length of the cycle solely depends on |Q| and |Γ|. So, there are at least two different numbers n 1 and n 2 such that the computations on inputs a n #u#a n1 and a n #u#a n2 are both successful, a contradiction that concludes the first case.

In the second case, we assume that the value of h n (w) is reached for the last time when the input head is scanning some symbol a of the suffix a n , say in a configuration (a n #w#a s1 , p 1 , a s2 , γ, β), where n = s 1 + s 2 and |γ| = h n (w). Again, the computation continues from this configuration successfully. Since h n (w) < |γ 2 γ 1 | the value of h n (w) is bounded from above by a constant k 0 that depends solely on |Q| and |Γ|. As in the first case the remaining computation is on unary input a s2 and, thus, there are at most |Γ| k0 •|Q| different possibilities for the topmost |γ| pushdown symbols and a state. This number of possibilities is also a constant, say k, that depends solely on |Q| and |Γ|. Assume now s 2 ≥ k. Then the argument of the first case applies that says that the computation continues in cycles with respect to the state and the topmost k 0 pushdown symbols, where the length of the cycle is at most k. So, extending the suffix a n by as many symbols a as are read during a cycle, yields a successful computation on an input that is not the first component of any pair in 3Occur, a contradiction.

Summarizing so far, we conclude that, for all n large enough and all w ∈ L bin , h n (w) < |γ 2 γ 1 | and the value of h n (w) is reached for the last time when the input head is scanning one of the last k input symbols, where k is some constant.

The last step in the proof is to apply incompressibility arguments to obtain a contradiction to the assumption that the REV-w-DPDT M realizes 3Occur.

To this end, we choose a (long enough) word w ∈ {0, 1} * with C(w) ≥ |w|, consider a successful computation of M on a |t(w)| #t(w)#a |t(w)| , and show that w can be compressed via M .

First, we describe a program P which reconstructs w from a description of M , the length |t(w)|, the last two letters z 1 z 2 of t(w) as well as the state p 1 , the number s 2 of remaining input symbols, and the pushdown content γ of the configuration in which the value of h n (w) is reached for the last time.

The program P first simulates the remaining computation of M beginning in the configuration in which the value of h n (w) is reached for the last time. That is, it simulates the computation (λ, p 1 , a s2 , γ, λ) * (a s2 , q f , , γ , β), where M halts accepting in the latter configuration. Next, P enumerates all words x of length |t(w)| from L bin whose last two letters are z 1 z 2 and simulates M on each candidate a |t(w)| #x#a |t(w)| . If the simulation halts accepting in state q f with pushdown content γ and output a |t(w)| #a |t(w)| #a |t(w)| we have x = t(w) and, thus, reconstructed w.

In order to show the correctness of the reconstruction, assume contrarily that there is another input y = t(w) in L bin ending with z 1 z 2 , for which the simulation of M halts accepting in state q f with pushdown content γ and output a |t differing only in their inputs, such that x j = y j for i ≤ j ≤ n, and x i-1 = y i-1 . Since x and y both end with z 1 z 2 , we have i ≤ n -1, and since x = y, we have i ≥ 2. Now, x i is either a or b, say b. That is, x i = y i = b and x i-1 = y i-1 . This implies that precisely one of x i-1 and y i-1 is b, say, x i-1 = b and y i-1 = a.

The word y 1 y 2 • • • y i b belongs to L bin . Moreover, it can be extended to some word y 1 y 2 • • • y i by i+2 • • • y n that belongs to L bin as well. Since M is deterministic we obtain the computation (λ, q 0 , a n #y

1 y 2 • • • y i by i+2 • • • y n #a n , ⊥, λ) * (a n #y 1 y 2 • • • y i-1 , p, y i by i+2 • • • y n #a n , γ 1 , β 1 )
that must continue successfully. Therefore, the computation (λ, q 0 , a n #x

1 x 2 • • • x i by i+2 • • • y n #a n , ⊥, λ) * (a n #x 1 x 2 • • • x i-1 , p, x i by i+2 • • • y n #a n , γ 1 , β 1 )
must continue successfully as well. However, since x i-1 = x i = b the word x 1 x 2 • • • x i-1 x i by i+2 • • • y n contains the factor bbb and, thus, does not belong to L bin , a contradiction. We conclude that program P , in fact, reconstructs t(w) and, thus, the word w. Finally, we determine the Kolmogorov complexity C(w) of w. Recall that P reconstructs w from a description of M , the length |t(w)|, the last two letters z 1 z 2 of t(w) as well as the state p 1 , the number s 2 of remaining input symbols, and the pushdown content γ of the configuration in which the value of h n (w) is reached for the last time. We conclude C(w) < |w|, for w long enough, contradicting that C(w) ≥ |w|. Therefore, M cannot realize 3Occur.

The relations between the families of transductions shown are summarized in Figure 5.

1 .

 1 m = m and (d = ⇐⇒ d = ); 2. depending on the pushdown operations op and op : (a) if op = pop or op = pop, then (a, d) = (a , d ); (b) if op = op = push(x) for some x ∈ Γ, then (a, d) = (a , d ) implies p = p ; (c) otherwise,

Figure 1 :

 1 Figure1: A REV-w-DPDT realizing the transduction τ (Example 1). Edges corresponding to transitions δ(p, a, g) = (q, op, d, m) are labeled a, g | d, m, where the symbol stands for "any pushdown symbol", ↓ stands for m = 0, and → stands for m = 1. The pushdown operation op is indicated in the second line of a label (technically speaking, an edge using the symbol represents several transitions: one with the empty pushdown symbol ⊥, the other ones with the symbols from Γ).

  1), where d = if d = λ and d = d otherwise, and

Figure 2 :

 2 Figure 2: A REV-bd-DPDT realizing the transduction lRotate. The symbol σ represents any symbol of the input alphabet.

Figure 3 :

 3 Figure 3: A REV-w-DPDT realizing mSwap.

Theorem 14

 14 The family T (bd-DPDT) strictly includes the family T (REV-bd-DPDT), and the families T (s-DPDT) and T (M-DPDT) strictly include the family T (REV-s-DPDT) = T (REV-M-DPDT).

Figure 4 :

 4 Figure 4: A w-DPDT realizing the transduction Swap.

  (w)| #a |t(w)| #a |t(w)| . Let n = |t(w)| and x = x 1 x 2 • • • x n and y = y 1 y 2 • • • y n .From the accepting configurations, run M backwards (using the reversibility of M ) for as long as the suffixes of x and y are identical. This eventually reaches configurations(a n #x 1 x 2 • • • x i-1 , p, x i x i+1 • • • x n #a n , γ 1 , β 1 ) and (a n #y 1 y 2 • • • y i-1 , p, y i y i+1 • • • y n #a n , γ 1 , β 1 )

  So, C(w) is given by the length of the binary representation of these ingredients. Let |P | be the constant size of the program P , and |M | be the constant size of M . The length of t(w) can be written with O(log(|w|)) bits and the last two letters z 1 z 2 with O(2 • log(|Σ|)) bits. For the state p 1 , O(log(|Q|)) bits are sufficient. Since s 2 ∈ O(|w|), it is represented by O(log(|w|)) bits. Finally, recall that the length of the pushdown content γ is bounded from above by the constant k 0 . So, O(k 0 • log(|Γ|)) bits are sufficient to represent γ. In total, we obtain C(w) ∈ |P | + |M | + O(log(|w|)) + O(2 • log(|Σ|)) + O(log(|Q|)) + O(k 0 • log(|Γ|)) = O(log(|w|)) ⊆ o(|w|).

T

  (M-DPDT) T (s-DPDT) T (bd-DPDT) T (w-DPDT) T (REV-M-DPDT) T (REV-s-DPDT) T (REV-bd-DPDT) T (REV-w-DPDT)

Figure 5 :

 5 Figure 5: Relations between the families of transductions discussed, where an arrow denotes a proper inclusion. All families which are not linked by a path are pairwise incomparable.

* (a n #(b m a) i+2j , p, (b m a) -i-2j , γ 2 , β 2 ),where β 0 , β 1 , and β 2 are of the form a n #a + .

Acknowledgments

This work was supported by the European COST Action IC 1405: Reversible Computation -Extending Horizons of Computing.

We note that |f (x, y)| = |y| for all x, y ∈ {a, b} + . Then, consider transductions

and their union τ = τ 1 ∪ τ 2 . We now claim that τ can be realized by an s-DPDT, but not by any M-DPDT. For the first claim we now describe an s-DPDT M for τ . Basically, M reads and emits every symbol of the prefix u#v up to the symbol $ 1 or $ 2 . Additionally, u#v is pushed on the pushdown store.

In case of a separating symbol $ 1 , M remains on $ 1 and removes v R # from the pushdown store. Then, the remaining input is read and for every symbol read one symbol from u R is popped from the pushdown store and emitted. If the remaining input is shorter than u R then only a prefix of u R is emitted, otherwise additional symbols c are emitted if needed. In case of a separating symbol $ 2 , the remaining input is read and for every symbol read one symbol from v R is popped from the pushdown store and emitted. Again, if the remaining input is shorter than v R then only a prefix of v R is emitted, otherwise additional symbols c are emitted if needed. Clearly, M is an s-DPDT that realizes τ . Now, we assume that τ is realized by an M-DPDT M . Since M reads and emits a symbol in every step, it is possible to consider M as a realtime DPDA A that works over an alphabet of paired symbols where the left symbol is the input read and the right symbol is the output written. Hence, A accepts the language { (x 1 , y 1 )(x 2 , y 2 )

Next, we intersect L(A) with the regular language (a, a) + (#, #)(a, a) + {($ 1 , $ 1 ), ($ 2 , $ 2 )}(a, a) + (a, c) and obtain that language

is realtime deterministic context free. However, it is shown in [START_REF] Igarashi | A pumping lemma for real-time deterministic context-free languages[END_REF] by using a particular pumping lemma for realtime deterministic context-free languages that

A similar argument can be applied to L and shows that L(A) is not realtime deterministic context free which gives a contradiction and concludes the proof of the theorem.

We would like to note that the input part of the witness transduction τ used in the above proof is a regular language which is clearly accepted by DPDAs as well as by realtime DPDAs. Thus, the separation of the families T (M-DPDT) and T (s-DPDT) relies in fact on the power of the different types of pushdown transducers and not on the different computational power of the underlying pushdown automata.