Register transducers

Mikołaj Bojańczyk

zajęcia / courses

Two-way automata are easy to describe, but a pain to work with. For example, it is difficult to show that they cannot do something, or it is difficult to show that they are closed under composition. Finally, it would be nice to have a one way model for efficiency reasons (the buzzword here is streaming). This is where register automata come in, a model also known as streaming transducers. In the end, we will prove that it is equivalent to deterministic two-way automata with output.

A register transducer consists of the following ingredients:
• an input alphabet $\Sigma$ ;
• an output alphabet $\Gamma$ ;
• a set of states $Q$ with a distinguished initial state $q_0 \in Q$ ;
• a set of registers $R$ ;
• a transition function

$\delta : Q \times \Sigma \to Q \times \underbrace{(R \to (R \cup \Gamma)^*)}_{\text{register update}$

• an output function

$out : Q \to (R \cup \Gamma)^*$

The automaton is run as follows. The registers store words over the output alphabet. Initially, every register stores the empty word. When the automaton is in state $q$ and it reads a letter $a$ , transition function is applied to $(q,a)$ , yielding a new state $p$ and a register update

$f : R \to (R \cup \Gamma)^*$

Then, in parallel, each register $r$ is set to $f(r)$ , with the register names replaced by their contents. For example if

$f(r)= rar$

with $a$ being an input letter, then register $r$ is replaced by its previous contents, then $a$ , and then its previous contents again.

After the entire word has been processed, with the last state used being $q$ , then the automaton outputs $out(q)$ , with register names replaced by their contents.

Copyless restriction. The model, as defined above, goes beyond two-way automata with output. For example, one could initially set a register to $a$ , and then duplicate its contents in every step, thus creating an output of exponential length. To avoid this, one introduces the following copyless restriction. We say that a register update

$f : R \to (R \cup \Gamma)^*$

is copyless if every register $r \in R$ appears in at most one word $f(s)$ , and in that word it appears at most once. The intuition is that the register contents are physical objects and can only be moved around and not duplicated.

From now on, when we say register automaton, we assume that all register updates in the transition function are copyless. The output function need not be copyless, since it is applied only once, and requiring it to be copyless does not weaken the model.

Future oracle. A register automaton with a future oracle is defined as follows. The future oracle is a an automaton over the input alphabet, which is deterministic from right to left. If the states of the future oracle are $P$ , then the transition function of the register automaton using this oracle is the same as in the definition of a register automaton, except that instead of seeing the current input letter from $\Sigma$ , one sees the state of the future oracle in $P$ , as obtained by reading the remaining input, beginning at the end of the input and ending in the first position that has not been read yet.

We now show that future oracles can be eliminated. In this particular model, past oracles do not make much sense, since they can be simulated by the state of the automaton.

Theorem. For every register transducer with a future oracle, there is register transducer (without any oracle), which defines the same function from words to words.

zajęcia / courses

Register transducers

Register transducers

Leave a Reply