Transducing Reversibly with Finite State Machines

Abstract

Finite state machines are investigated towards their ability to reversibly compute transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are backward deterministic and hence are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to three types of length-preserving transductions as well as to the property of working reversibly. It is possible to settle all inclusion relations between the families of transductions. Finally, the standard closure properties are investigated and the non-closure under almost all operations can be shown.

1 Introduction

One main motivation for the study of computational devices performing reversible computations is the physical observation that a loss of information results in heat dissipation [13]. It is therefore of great interest to avoid such situations and to privilege computations in which every configuration has a unique successor configuration as well as a unique predecessor configuration so that at every point of the computation no information gets lost. Reversibility has been studied for many computational devices starting with Lecerf’s [15] and Bennett’s [5] investigations for Turing machines, where it is shown that for every (possibly irreversible) Turing machine an equivalent reversible Turing machine can be constructed. This result has been achieved also for deterministic space-bounded Turing machines in [14]. For deterministic multi-head finite automata, the results depend on whether or not two-way motion of the heads is allowed. It is shown in [16] that the general model and the reversible model coincide for two-way multi-head finite automata, whereas the reversible model is weaker than the general model in case of one-way motion [12]. A similar result has been obtained in [10] for deterministic pushdown automata. In both cases, the loss of information in computations is inevitable. Reversible computations in deterministic finite automata $(\mathrm {DFA}$) have been introduced in [3] and it is shown in [17] that there are regular languages which cannot be accepted by any (one-way) reversible deterministic finite automaton. On the other hand, it is known due to [9] that the general model and the reversible model coincide if the input head is two-way. Recent results on reversible regular languages are given in [8], where it is shown that it is NL-complete to decide whether a given one-way $\mathrm {DFA}$ accepts a reversible language. Additionally, exponential upper and lower bounds for the conversion of one-way $\mathrm {DFA}$s to equivalent reversible $\mathrm {DFA}$s are given.

Computational models are not only interesting from the vantage point of accepting some input, but also from the viewpoint of transforming some input into some output. For example, a parser for a formal 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. The simplest model in this context is the finite state transducer which is a finite automaton with an output alphabet that assigns to each input accepted at least one output word. Transductions computed by different variants of such transducers are studied in detail in [7]. Deterministic and nondeterministic pushdown transducers are investigated in [2]. Furthermore, characterizations of pushdown transductions as well as applications to the parsing of context-free languages are given. A more general theory of transducing devices has been outlined already 1969 in [1]. More recently, transducing variants of stack automata have been considered in [6], whereas the parallel model of cellular automata has been investigated in [11] towards its transducing capabilities.

Here, we study reversible deterministic finite state transducers ($\text {DFST}$). Since reversible devices should be able to preserve information and $\text {DFST}$s use and produce information concerning the input and the output, the transition function in $\text {DFST}$s will be defined depending on the input and the output. Thus, reversible $\text {DFST}$s may be considered as reversible Turing machines (see, for example, [4, 5]) with a one-way input tape and a one-way output tape. To start with a weak form of transductions and, again, from the viewpoint of information preserving computations, we are here considering essentially length-preserving transductions. In Sect. 2 we give the formal definition of a reversible $\text {DFST}$ ($\text {REV-DFST}$) and define Mealy, strongly, and weakly length-preserving $\text {DFST}$s which basically differ by the fact whether or not both heads have to move synchronously. In Sect. 3, we compare the three notions of length-preserving transducers. It turns out that the Mealy $\text {DFST}$s are equivalent to strongly length-preserving $\text {DFST}$s, but weaker than weakly length-preserving $\text {DFST}$s. These results hold for the reversible case as well. Moreover, the reversible models turn out to be weaker than the general model. In addition, we obtain the decidability of the question whether or not the transduction realized by an arbitrary Mealy $\text {DFST}$ can be realized by a Mealy $\text {REV-DFST}$ as well. In the affirmative case, the Mealy $\text {REV-DFST}$ can effectively be constructed. Finally, we discuss in Sect. 4 the usually investigated closure properties for reversible and length-preserving $\text {DFST}$s. We obtain closure under intersection, but non-closure under union, complementation, composition, inversion, concatenation, iteration, and reversal.

2 Preliminaries

We write $\varSigma ^*$ for the set of all words over the finite alphabet $\varSigma$. The empty word is denoted by $\lambda$, and we set $\varSigma ^+ = \varSigma ^* \setminus \{\lambda \}$. The reversal of a word w is denoted by $w^R$, and for the length of w we write |w|. We use $\subseteq$ for inclusions and $\subset$ for strict inclusions.

First, we define reversible deterministic finite state transducers. We define this model as usual with two tapes, namely, an input and an output tape. The model can be seen as a restricted variant of a Turing machine having a one-way read-only input tape and a one-way output tape. In the forward computation the transducer decides its operation depending on the current state, the current input symbol, and the symbol at the current square of the output tape. It may perform a right move on the input tape and may rewrite the current tape square on the output tape and afterwards may perform a right move on the output tape as well. The output tape is initially filled with blank symbols.

Formally, we define a deterministic finite state transducer ($\text {DFST}$) as a system $M=\langle Q,\varSigma ,\varDelta ,q_0,\delta ,F \rangle$, where Q is the set of internal states, $\varSigma$ is the set of input symbols, $\varDelta$ is the set of output symbols containing the blank symbol , $q_0$ is the initial state, $F\subseteq Q$ is the set of accepting states, and

is the partial transition function.

A configuration of $\text {DFST}$ M at some time $t \ge 0$ is a quadruple (v, p, w, z), where $v\in \varSigma ^*$ is the already read part of the input to the left of the input head, $p \in Q$ is the current state, $w\in \varSigma ^*$ is the still unread part of the input to the right of the input head, and $z \in \varDelta ^+$ is the already written part of the output, the rightmost symbol of z being the currently scanned symbol on the output tape. The initial configuration for input w is set to . During the course of its computation, M runs through a sequence of configurations. One step from a configuration to its successor configuration is denoted by $\vdash$ and defined as follows. For $p\in Q$, $a\in \varSigma$, $v,w\in \varSigma ^*$, $z\in \varDelta ^*$, and $b \in \varDelta$, let (v, p, aw, zb) be a configuration. Then we define

The reflexive transitive closure of $\vdash$ is denoted by $\vdash ^*$.

A $\text {DFST}$ halts if the transition function is undefined for the current configuration. The output written by a $\text {DFST}$ M on input $w \in \varSigma ^*$ is denoted by and is defined as $M(w)=v$, if with $q\in F$, v is the non-blank part of $v'$, and M halts. Otherwise, M(w) is defined to be the empty set. Now, the transduction defined by M is the set $T(M)=\{\, (w,M(w)) \mid w \in \varSigma ^* \text{ and } M(w)\ne \emptyset \,\}$. We remark that M may also be considered as a partial function mapping some $w \in \varSigma ^*$ to . 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 $\mathrm {X}$ is denoted by $\mathscr {T}(X)$.

Now, we turn to reversible $\text {DFST}$. 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. In particular, the machines reread the symbols which they have read in a preceding forward computation step. So, for reverse computation steps each head is either moved to the left or stays 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 $\text {DFST}$ is said to be reversible, abbreviated as $\text {REV-DFST}$, if for any two distinct transitions

$$ \begin{array}{rcl} \delta (p, x_0, x_1) &{}=&{} (q, y_1, d_0, d_1) \quad \text {and}\\ \delta (p', x_0', x_1') &{}=&{} (q', y_1', d_0', d_1'), \end{array} $$

if $q=q'$, then $(d_0,d_1)=(d'_0,d'_1)$ and $(x_0,y_1) \ne (x_0',y_1')$. The first condition means that transitions reaching the same state have to move both heads in the same way. The second condition ensures that for any configuration the predecessor state can uniquely be determined from the state (which then implies the head movements), the input symbol read and the output symbol written.

A consequence of the definition of reversibility is the following property usually required for reversible devices.

Lemma 1

For any $\text {REV-DFST}$ holds that any configuration has at most one predecessor configuration.

In this paper, we consider in particular length-preserving $\text {DFST}$ and differentiate between three notions. We call a $\text {DFST}$ a Mealy transducer ($\text {M-DFST}$) if the transition function $\delta$ maps from $Q\times \varSigma \times \varDelta$ to . That is, in every time step an input symbol is read, an output symbol is written, and both heads proceed one position to the right. We call a $\text {DFST}$ strongly length-preserving ($\text {s-DFST}$) if the transition function $\delta$ maps from $Q\times \varSigma \times \varDelta$ to . That is, both heads are moved synchronously. Finally, we call a $\text {DFST}$ M weakly length-preserving ($\text {w-DFST}$), if $|w|=|M(w)|$, for all $(w,M(w))\in T(M)$. That is, the length of the input word read and the length of the output word written is equal at the end of the transduction.

In order to clarify the definitions we present an example.

Example 2

The transduction $\{\, ( a^nb^m, a^nbc^{m-1} ) \mid m \ge 1, n\ge 0 \,\}$ can be computed by some Mealy $\text {REV-DFST}$ . For every a, the transducer writes an a on the output tape and makes a right move. When the first b appears in the input, it changes its state, emits b and makes a right move. Subsequently, M writes for every b a c in the output and makes a right move. Formally, the transition function $\delta$ is defined as

The reversibility of M is easily verified by inspecting the transition function and checking the two conditions of the definition. Thus, the transduction defined by M belongs to $\mathscr {T}(\text {M-REV-DFST})$. We note that the projection of T(M) to the first component L(M) is the regular language $\{\, a^nb^m \mid m \ge 1, n\ge 0 \,\}$ which is known to be irreversible. $\blacksquare$

3 Computational Capacity

We turn to consider the computational capacity of reversible $\text {DFST}$s. 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 separating in fact the capabilities of computing transductions. We start with a normalization result stating that every length-preserving $\text {DFST}$ can be transformed into an equivalent one that moves at least one head in every step of its computation. Moreover, the construction preserves reversibility.

Lemma 3

Every $\text {w-DFST}$ ($\text {s-DFST}$, $\text {M-DFST})$ M can be converted into an equivalent $\text {w-DFST}$ ($\text {s-DFST}$, $\text {M-DFST})$ $M'$ such that in any computation step of $M'$ at least one head is moved. Moreover, if M is reversible then $M'$ is reversible as well.

The construction given in Lemma 3 leads to the following corollary.

Corollary 4

The families $\mathscr {T}(\text {M-DFST})$ and $\mathscr {T}(\text {s-DFST})$ as well as the families $\mathscr {T}(\text {M-REV-DFST})$ and $\mathscr {T}(\text {s-REV-DFST})$ are equal.

Proof

Both inclusions $\mathscr {T}(\text {M-DFST}) \subseteq \mathscr {T}(\text {s-DFST})$ and $\mathscr {T}(\text {M-REV-DFST}) \subseteq \mathscr {T}(\text {s-REV-DFST})$ follow from the definition. On the other hand, the construction in the proof of Lemma 3 leads to an equivalent $\text {M-DFST}$ ($\text {M-REV-DFST}$) for a given $\text {s-DFST}$ ($\text {s-REV-DFST}$).    $\square$

Theorem 5

Let M be a Mealy transducer. Then it is NL-complete to decide whether T(M) can be realized by a reversible Mealy transducer. If the question is answered in the affirmative, an equivalent reversible Mealy transducer can effectively be constructed.

Proof

Given a Mealy transducer $M=\langle Q,\varSigma ,\varDelta ,q_0,\delta ,F \rangle$, we construct a deterministic finite automaton $M'=\langle Q,\varSigma \times \varDelta ,q_0,\delta ',F \rangle$, where for $q,q'\in Q$, $x\in \varSigma$ and $y\in \varDelta$, $\delta '(q,(x,y))=q'$ if and only if . Since a Mealy machine moves its heads in every step, it sees in every computation step a blank symbol on the output tape and, thus, no other situations have to be considered. Both machines work deterministically, so for each pair $(w,w')\in T(M)$ there is a word $(w,w')\in L(M')$ and vice versa. In particular, the construction reveals that there are no two distinct transitions $\delta '(q,(x,y))$ and $\delta '(q,(x,y'))$. Moreover, the construction preserves reversibility: If M is reversible, then for any two distinct transitions $\delta (p, x_0, x_1) = (q, y, 1, 1)$ and $\delta (p', x_0', x_1') = (q', y', 1, 1)$ we have that $q=q'$ implies $(x_0,y) \ne (x_0',y')$. So, for the constructed transitions $\delta '(p,(x_0,y))=q$ and $\delta '(p',(x'_0,y'))=q'$ the equality $q=q'$ implies $(x_0,y) \ne (x_0',y')$ as well, which means that $M'$ is reversible.

Conversely, given a deterministic finite automaton $M'=\langle Q,\varSigma \times \varDelta ,q_0,\delta ',F \rangle$ with no two distinct transitions $\delta '(q,(x,y))$ and $\delta '(q,(x,y'))$, we construct a Mealy transducer $M=\langle Q,\varSigma ,\varDelta ,q_0,\delta ,F \rangle$, where for $q,q'\in Q$, $x\in \varSigma$ and $y\in \varDelta$, if and only if $\delta '(q,(x,y))=q'$. Since $M'$ is deterministic and meets the property there are not two distinct transitions $\delta '(q,(x,y))$ and $\delta '(q,(x,y'))$, M is deterministic as well. So, by construction, for each word $(w,w')\in L(M')$ there is a pair $(w,w')\in T(M)$ and vice versa. Again, the construction preserves reversibility: Let $M'$ be reversible. Since Mealy machines move both heads in each computation step, for M the first condition of working reversibly is fulfilled. For every pair of a state and an input symbol, $M'$ has a unique predecessor state, since it is reversible. Thus the second condition of reversibility of M can be concluded. So, M is reversible as well.

Now, let $L(M')$ be the language of a deterministic finite automaton $M'$ that has been constructed from a Mealy transducer M. For each transduction $M(zxz')=uyu'$ with $|z| =|u|$, $x\in \varSigma$, and $y\in \varDelta$, there is no transduction $M(zxz'')=uy'u''$ with $y\ne y'$ since M works deterministically. It can be concluded that the property that there are no two distinct transitions $\delta '(q,(x,y))$ and $\delta '(q,(x,y'))$ is met by any automaton accepting $L(M')$.

So far, we have shown that given a Mealy transducer M there exists an equivalent reversible Mealy transducer $\hat{M}$ if and only if the $\mathrm {DFA}$ $M'$ constructed from M accepts a language that can be accepted by some reversible $\mathrm {DFA}$ $\hat{M}'$, where a $\mathrm {DFA}$ is reversible, if every input letter a induces an injective partial mapping from the state set to itself via the mapping $\delta _a:Q\rightarrow Q$ with $p\mapsto \delta (p,a)$. In [8] it has been shown that the regular language reversibility problem – given a $\mathrm {DFA}$ $M'$, decide whether $L(M')$ is accepted by any reversible $\mathrm {DFA}$ – is NL-complete. If the question is answered in the affirmative, an equivalent reversible $\mathrm {DFA}$ can effectively be constructed.

These results together with the constructions shown above prove the assertion.    $\square$

We turn to show that the condition to work reversibly strictly weakens the computational capacity of Mealy transducers, thus, separating the families $\mathscr {T}(\text {M-REV-DFST})$ and $\mathscr {T}(\text {M-DFST})$. Note that the witness transduction relies on an input language that is accepted by the weaker devices.

Theorem 6

The family $\mathscr {T}(\text {M-REV-DFST})$ is strictly included in the family $\mathscr {T}(\text {M-DFST})$.

Proof

We consider the Mealy transducer $M=\langle Q,\varSigma ,\varDelta ,q_0,\delta ,F \rangle$ depicted in Fig. 1 which is irreversible due to the transitions and .

Fig. 1.

A Mealy transducer for which no equivalent reversible Mealy transducer exists, though the input language is reversible regular.

In order to show that there is no equivalent reversible Mealy transducer we apply the constructions of the proof of Theorem 5. The minimal deterministic finite automaton $M'=\langle Q,\varSigma \times \varDelta ,q_0,\delta ',F \rangle$ constructed from M is obtained by merging the two accepting states $q_5$ and $q_6$ in Fig. 1. In [8] it has been shown that the language $L(M')$ can be accepted by a reversible $\mathrm {DFA}$ if and only if there do not exist useful states $p,q\in Q$, a pair $(x,y)\in \varSigma \times \varDelta$, and a word $w\in (\varSigma \times \varDelta )^*$ such that $p\ne q$, $\delta '(p,(x,y))=\delta '(q,(x,y))$, and $\delta '(q,(x,y)w)=q$.

Due to the two transitions $\delta '(q_1,(b,b))=\delta '(q_2,(b,b))$, and the computation path $\delta '(q_1, (b,b)(a',a))=q_1$, it follows that there is no equivalent reversible $\mathrm {DFA}$ and, thus, there is no reversible Mealy transducer realizing the transduction T(M).    $\square$

Our next result separates the families of reversible weakly and reversible strongly length-preserving finite state transducers. We define the transduction $\tau _1=\{\,(aab^m\mathtt {\$}b^n, ab^m\mathtt {\$}b^{n+1})\mid m,n\ge 0 \,\}$ that is realized by a $\text {w-REV-DFST}$ as shown in the following example.

Example 7

The transduction $\tau _1$ is realized by the $\text {w-REV-DFST}$

where the transition function $\delta$ is as follows.

The reversibility of M is easily verified by inspecting the transition function. $\blacksquare$

Theorem 8

The transduction $\tau _1$ is a witness for the strictness of the inclusion $\mathscr {T}(\text {s-REV-DFST})\subset \mathscr {T}(\text {w-REV-DFST})$. Moreover, transduction $\tau _1$ belongs to $\mathscr {T}(\text {w-REV-DFST})\setminus \mathscr {T}(\text {s-DFST})$.

Proof

By Example 7, transduction $\tau _1$ belongs to $\mathscr {T}(\text {w-REV-DFST})$. The inclusion itself follows for structural reasons. It remains to be shown that $\tau _1$ does not belong to the family $\mathscr {T}(\text {s-DFST})$. In contrast to the assertion assume $\tau _1$ is realized by the $\text {s-DFST}$ $M=\langle Q, \varSigma , \varDelta , q_0,\delta , F\rangle$.

We consider input prefixes and let be the computation on the input prefix $aab^m$ (since both heads of M must move synchronously, the output head scans the after $ab^{m+1}$). Now, the computation is extended by a further input symbol b as with $x\in \varDelta$. Since x cannot be rewritten anymore, it must be either b or $\mathtt {\$}$.

If $x=b$, then the computation cannot be the beginning of a computation realizing $\tau _1$, since on input $aab^{m+1}$ the output $ab^{m+2}$ has been written, but the input $aab^{m+1}\mathtt {\$}b^n$ has to be transformed into $ab^{m+1}\mathtt {\$}b^{n+1}$. On the other hand, if $x=\mathtt {\$}$ then the computation cannot be the beginning of a computation realizing $\tau _1$ either, since on input $aab^{m+1}$ the output $ab^{m+1}\mathtt {\$}$ has been written, but the input $aab^{m+2}\mathtt {\$}b^n$ has to be transformed into $ab^{m+2}\mathtt {\$}b^{n+1}$. The contradiction shows the assertion.    $\square$

For the next separation, again, the witness transduction relies on an input language that is accepted by the weaker devices. We define the transduction $\tau _2=\{\,(a^m\mathtt {\$}b^n, a^{m-1}\mathtt {\$}b^{n+1})\mid m\ge 1, n\ge 0 \,\}$ that is realized by a $\text {w-DFST}$ as shown in the following example.

Example 9

The transduction $\tau _2$ is realized by the $\text {w-DFST}$

where the transition function $\delta$ is as follows.

Transducer M is not reversible due to, for example, the first two rules. $\blacksquare$

Theorem 10

The transduction $\tau _2$ is a witness for the strictness of the inclusion $\mathscr {T}(\text {w-REV-DFST})\subset \mathscr {T}(\text {w-DFST})$.

Proof

By Example 9, transduction $\tau _2$ belongs to $\mathscr {T}(\text {w-DFST})$. The inclusion itself follows for structural reasons. It remains to be shown that $\tau _2$ does not belong to the family $\mathscr {T}(\text {w-REV-DFST})$. In contrast to the assertion assume $\tau _2$ is realized by the $\text {w-REV-DFST}$ $M=\langle Q, \varSigma , \varDelta , q_0,\delta , F\rangle$.

We consider input prefixes $a^m$, for m large enough. While M processes these prefixes, its input head always sees the symbol a, regardless of the moves of the input head. The transition function, besides on the input symbol a, depends on the current state and the output symbol currently scanned by the output head. Within at most $|Q|\cdot |\varDelta |$ transitions, one pair of these parameters appears twice. Let $c_0\vdash c_1 \vdash \cdots \vdash c_t$, for some $t\ge 0$, be the sequence of configurations passed through by M while processing the prefix $a^m$. Assume that the first time where such pairs of parameters appear twice is in $c_i$ and $c_{i+j}$ with $i,j\ge 1$. Let $c_i=(u_i,q_i,v_i,w_ix_i)$ with $u_iv_i\in a^*$, $q_i\in Q$, $x_i\in \varDelta$, and $w_i\in \varDelta ^*$. Then we conclude $\delta (q_{i-1},a,x_{i-1})=(q_i, y, d_0, d_1)$ and $\delta (q_{i+j-1},a,x_{i+j-1})=(q_i, y, d_0, d_1)$. Since on the right-hand sides the states are identical and M is reversible, $d_0$ as well as $d_1$ are the same in both transitions. If $d_1=1$ then in both configurations the output head scans a blank. If $d_1=0$ then in both configurations the output head scans the currently written symbol $y\in \varDelta$. However, the two transitions violate the reversibility of M. The contradiction shows that the assumption $i\ge 1$ was wrong.

Now let $i=0$. Then M runs through cycles of length j, that is, the sequence of configurations passed through is $c_0\vdash c_1 \vdash \cdots \vdash c_j \vdash \cdots$, with , , and , for some $k,\ell \ge 0$ (since the computation is in a cycle, state and currently scanned output symbol are identical, that is, $q_0$ and ). If $k\ne \ell$ and M transduces $a^m\mathtt {\$}b^n$ to $a^{m-1}\mathtt {\$}b^{n+1}$, then it also transduces $a^{m+k}\mathtt {\$}b^n$ to $a^{m-1+\ell }\mathtt {\$}b^{n+1}$ which does not belong to $\tau _2$. Therefore, we derive $k=\ell$. But this implies which cannot be the beginning of a computation realizing $\tau _2$, since the number of a’s written is already too large by one. So, we have a contradiction to the assumption that $\tau _2$ is realized by some $\text {w-REV-DFST}$.    $\square$

The relations between the families of transductions shown in this section are summarized in Fig. 2.

Fig. 2.

Relations between the families of transductions discussed, where an arrow denotes a proper inclusion.

4 Closure Properties

In this section, we will essentially show that the families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ (hence also $\mathscr {T}(\text {s-REV-DFST})$) are not closed under the usually studied operations for transductions. We start with the easy observation that any transduction realized by some $\text {DFST}$ M has to be functional, that is, any input w is transduced into at most one output M(w). This fact will be used in the following lemma.

Lemma 11

The families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ are neither closed under union nor under complementation.

Proof

Consider the two transductions $\tau _1=\{\,(a^m\mathtt {\$}b^n,a^m\mathtt {\$}b^n)\mid m,n\ge 0 \,\}$ and $\tau _2=\{\,(a^m\mathtt {\$}b^n,c^m\mathtt {\$}d^n)\mid m, n\ge 0 \,\}$, that can be realized by some $\text {M-REV-DFST}$ ($\text {w-REV-DFST}$). But the transduction $\tau _1 \cup \tau _2$ is no longer functional, since some inputs have to be transduced to at least two different words. Thus, transduction $\tau _1 \cup \tau _2$ cannot be computed by any $\text {M-REV-DFST}$ ($\text {w-REV-DFST}$).

Since the complement of a transduction realized by a $\text {DFST}$ is in general not functional, we obtain the non-closure under complementation for the families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ as well.    $\square$

However, using the well-known Cartesian product construction for the family of transductions realized by $\text {M-REV-DFST}$s the closure under intersection can be shown.

Lemma 12

Family $\mathscr {T}(\text {M-REV-DFST})$ is closed under intersection.

Next, we consider the composition $M \circ M'$ of two transducers M and $M'$ which means that the output produced by M is considered as input for $M'$.

Lemma 13

The family $\mathscr {T}(\text {M-REV-DFST})$ is not closed under composition.

Proof

We consider the $\text {M-DFST}$ M depicted in Fig. 1. It has been shown in Theorem 6 that T(M) cannot be computed by any $\text {M-REV-DFST}$. Now, M is reconstructed to $M'$ in such a way that every edge e labeled with (x, y) is changed to $(x,y_i)$ where i is a unique number for the edge e. Clearly, $M'$ is an $\text {M-REV-DFST}$, since the output symbol uniquely indicates the predecessor state. Next, we construct another $\text {M-REV-DFST}$ $M''$ with a single state that translates every symbol $x_i$ to x. So, $M''(M'(w))=M(w)$, for every word w. Since T(M) cannot be computed by any $\text {M-REV-DFST}$, it can be concluded that the composition $M' \circ M''$ cannot be computed by any $\text {M-REV-DFST}$.    $\square$

Theorem 14

The family $\mathscr {T}(\text {w-REV-DFST})$ is not closed under composition.

Proof

Let with

be an $\text {M-REV-DFST}$ that computes the transduction

$$ \tau _1=\{\,(a^m\mathtt {\$}b^n ,cca^{m-2}\mathtt {\$}b^n)\mid m\ge 2, n\ge 0 \,\} \cup \{\,(a\mathtt {\$}b^n ,c\mathtt {\$}_0 b^n)\mid n\ge 0 \,\}. $$

Let with

be a $\text {w-REV-DFST}$ that realizes

$$ \tau _2=\{\,(cca^{m}\mathtt {\$}b^n ,a^{m+1}\mathtt {\$}b^{n+1})\mid m, n\ge 0 \,\} \cup \{\,(c\mathtt {\$}_0 b^n ,\mathtt {\$}b^{n+1})\mid m, n\ge 0 \,\}. $$

The transduction realized by the composition $M \circ M'$ is

$$\{\,(a^m\mathtt {\$}b^n, a^{m-1}\mathtt {\$}b^{n+1})\mid m\ge 1, n\ge 0 \,\}$$

which cannot be computed by any $\text {w-REV-DFST}$ due to Theorem 10.    $\square$

Let T(M) be a transduction computed by some $\text {DFST}$ M. Then the inverse transduction $T^{-1}(M)$ is defined as $\{\, (w,w') \mid (w',w) \in T(M) \,\}$.

Lemma 15

The families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ are not closed under inversion.

Proof

Let M be a $\text {M-REV-DFST}$ computing $\{\, (w,a^{\vert w\vert })\mid w\in \{ a,b\}^* \,\}$. For any $n\ge 0$, M transduces $2^n$ words to the same image $a^n$. Thus, the inverse transduction is no longer functional and hence cannot be computed by any $\text {M-REV-DFST}$ or $\text {w-REV-DFST}$.    $\square$

For the non-closure under reversal we need the following lemma stating that in length-preserving transductions the distance between input head and output head is always bounded by some constant.

Lemma 16

Let M be a $\text {w-DFST}$ with state set Q and w be any input such that $M(w)\ne \emptyset$. Then the length difference between the words on the input tape and the output tape during the transduction of w is at most $\vert Q\vert$.

Lemma 17

The families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ are not closed under reversal.

Lemma 18

The families $\mathscr {T}(\text {w-REV-DFST})$ and $\mathscr {T}(\text {M-REV-DFST})$ are neither closed under concatenation nor under iteration.

Proof

We consider two transductions $\{\,(\mathtt {\$}b^mea^n,\mathtt {\$}b^mea^n)\mid m,n\ge 0\,\} \cup \{(\lambda ,\lambda )\}$ and $\{\,(\texttt {\#}b^mea^n,\texttt {\#}d^mec^n)\mid m,n\ge 0\,\} \cup \{(\lambda ,\lambda )\}$ that can be computed by some $\text {M-REV-DFST}$s M and $M'$. Since the transductions T(M) and $T(M')$, hence also $T(M) \cup T(M')$, are contained in the concatenation $T(M)T(M')$, we can apply a similar argumentation as in Lemma 17 and obtain that $T(M)T(M')$ cannot be computed by any $\text {w-REV-DFST}$ which gives the non-closure under concatenation.

For the non-closure under iteration we consider the transduction

$$\{\,(a^n\mathtt {\$}b^m\mathtt {\$}a^l,a^n\mathtt {\$}b^m\mathtt {\$}c^l )\mid m,n,l\ge 0 \,\} $$

that can be computed by some $\text {M-REV-DFST}$ M. Let us consider an input word $w=a^n\mathtt {\$}b^m\mathtt {\$}a^l\mathtt {\$}b^{m'}\mathtt {\$}a^{l'}$ with $l>2$ and $m,n,m',l'\ge 0$ for the transduction $T(M)^*$.

Since $l>2$, we always can find four non-negative integers $l_1,l_2,l'_1,l'_2$ such that $l=l_1+l_2=l_1'+l_2'$ with $(l_1,l_2)\ne (l_1',l_2')$. Then both $(w,a^n\mathtt {\$}b^m \mathtt {\$}c^{l_1}a^{l_2}\mathtt {\$}b^{m'} \mathtt {\$}c^{l'})$ and $(w,a^n\mathtt {\$}b^m \mathtt {\$}c^{l'_1}a^{l'_2}\mathtt {\$}b^{m'} \mathtt {\$}c^{l'})$ belong to $T(M)^*$. So, the transduction is no longer functional and cannot be realized by any $\text {w-REV-DFST}$.    $\square$

The closure properties obtained in this section are summarized in Table 1.

Table 1. Closure properties of the transduction families discussed.