Two-way and register are the same

Mikołaj Bojańczyk

zajęcia / courses

Two-way and register are the same

Here we show that two-way automata and register automata describe the same functions from words to words.

Theorem. The following devices recognise the same partial functions from words to words:

deterministic two-way automaton with output
deterministic register automaton with regular lookahead.

Note that we have already claimed (but not proved) that for deterministic register automata, the regular lookahead can be removed.

From register automata to two-way automata

Let us show the implication from 2 to 1, i.e. how to convert a deterministic register automaton with regular lookahead. Recall that in a register automaton with registers $R$ and output alphabet $\Gamma$ , a register update is a function $R \to (R \cup \Gamma)^*$ . We draw a register update like this:

In the above picture, we assume that the inputs to the registers are read from top to bottom, formally speaking we would need to specify an ordering on the incoming edges for every register name at the right. When it reads an input word, the register automaton executes a sequence of register updates, as in the following picture:

In the above picture, we assume that there is a single designated output register, and the output produced by the automaton is simply the contents of this output register at the end of the run. This assumption can be made when regular lookahead is available. Let $\Delta$ be the finite set of register operations that can be triggered by individual transition. Therefore a run of the register automaton can be viewed as transforming an input word into a word over $\Delta^*$ .

Lemma 1. There is an NFA with output which takes an input word to the sequence of register updates that it triggers.

Proof. Just by simulating the automaton and using nondeterminism to guess the run of the regular lookahead. $\Box$

Lemma 2. If $f : \Sigma^* \to \Delta^*$ is recognised by an NFA with output and $g : \Delta^* \to \Gamma^*$ is recognised by a deterministic two-way automaton, then their composition $g \circ f$ is recognised by a deterministic two-way automaton.

Proof. Recall that NFA with output are equivalent to Eilenberg bimachines. An Eilenberg bimachine is the same thing as an oracle in a deterministic two-way automaton, and therefore $g \circ f$ is recognised by a deterministic two-way automaton with an oracle. Then, the oracle can be removed. $\Box$

Combining Lemmas 1 and 2 above, in order to show that a register automaton can be simulated by a deterministic two-way automaton, it suffices to show that there is a deterministic two-way automaton which inputs a sequence of register updates, and which outputs the contents of the designated output register at the end. The automaton views the register operations are a graph, where the vertices are pairs $(x,r)$ where $x$ is a position in the input word and $r$ is a register name. This graph is a tree, thanks to the copylesss assumption. The two-way automaton begins by going to $(x,r)$ where $x$ is the last position and $r$ is the designated output register. Then it does a depth-first search traversal through the tree, outputting letters during this run. In order to do this, the automaton needs to only remember the current register $r$ and the edge of the tree that was previously processed, as in the following picture:

From two-way automata to register automata

The idea is classical, dating back to the proof of Rabin and Scott that two-way automata (as accept/reject devices) can be made one way. Suppose that we have read a prefix of the input word. We need to remember what are the outputs that are produced by the two-way automaton on: a) the unique from the initial configuration to the first time that it reaches the current position; and b) runs that begin and end in the current position. Here is a picture:

More formally, one can describe the situation after reading a prefix $w$ of the input by a function

$f_w : Q \cup \set{\mbox{initial}} \to Q \cup \set{\mbox{reject}} \cup (\Gamma^* \times (Q \cup \set{\mbox{accept}}))$

whose definition is according to the picture above. The natural idea would be to store, for each argument of the above function, the value of the function. The state of the transducer would be used to store the finite part of the function, and the registers (one for each argument) would be used to store the output words used in the function. The problem with this idea is that it would lead to register updates that are not copyless. This problem would arise if there would be two transitions that move to the left and lead to the same target state, as in the following picture:

In such a situation, the register corresponding to state $r$ would need to be used twice in the register update. The solution to this observation is that in an actual accepting run of the two-way automaton, only one of the transitions would be used. The reason is that if both transitions would be used, then the automaton would enter a loop. To use this observation, we use the following lemma, whose straightforward proof is omitted.

Lemma. Consider a deterministic two-way automaton with input alphabet $\Sigma$ and states $Q$ . Consider the function $g : \Sigma^* \to (\Sigma \times \mathsf{P}(Q))^*$ which additionally labels each input position by the set of states used by (the unique) accepting run of the automaton in that position. Then $g$ is recognised by an NFA with output.

Register automata with regular lookahead are closed under precomposing with functions computed by NFA with output; for this one convert the NFA with output into a lookahead DFA with output, and then use the regular lookahead of the register automaton. Therefore, we can assume that a register automaton has access to the states in the accepting run (possibly none if there is no accepting states). It can then compute the function $f_w$ with its domain restricted to states used in the accepting run; and here the natural construction works because it is copyless.

COMMENTS

Krzysztof

January 30, 2017

Tu jest pusto.

zajęcia / courses

Two-way and register are the same

Two-way and register are the same

Leave a Reply