{"id":842,"date":"2015-12-14T19:47:58","date_gmt":"2015-12-14T18:47:58","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=842"},"modified":"2016-12-29T16:25:41","modified_gmt":"2016-12-29T15:25:41","slug":"register-transducers","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/6-transducers\/register-transducers","title":{"rendered":"Register transducers"},"content":{"rendered":"

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\u00a0streaming<\/em>). This is where register automata come in, a model also known as streaming transducers.\u00a0 In the end, we will prove that it is equivalent to deterministic two-way automata with output.<\/p>\n

A register transducer<\/em> consists of the following ingredients:
\n\u2022 an input alphabet \"\Sigma\";
\n\u2022 an output alphabet \"\Gamma\";
\n\u2022 a set of states \"Q\" with a distinguished initial state \"q_0 \in Q\";
\n\u2022 a set of registers \"R\";
\n\u2022 a transition function<\/p>\n

  <\/span>   <\/span>\"\[\delta : Q \times \Sigma \to Q \times \underbrace{(R \to (R \cup \Gamma)^*)}_{\text{register update}\]\"<\/p>\n

\u2022 an output function<\/p>\n

  <\/span>   <\/span>\"\[out : Q \to (R \cup \Gamma)^*\]\"<\/p>\n

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<\/p>\n

  <\/span>   <\/span>\"\[f : R \to (R \cup \Gamma)^*\]\"<\/p>\n

Then, in parallel, each register \"r\" is\u00a0set to \"f(r)\", with the register names replaced by\u00a0their contents. For example\u00a0if <\/p>\n

  <\/span>   <\/span>\"\[f(r)= rar\]\"<\/p>\n

with \"a\" being an input letter, then register \"r\" is replaced by its previous contents, then \"a\", and then its previous contents again.<\/p>\n

After the entire word has been processed, with the last state used being \"q\", then the automaton outputs \"out(q)\", with register names\u00a0replaced by\u00a0their contents.<\/p>\n

Copyless restriction.\u00a0<\/strong>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\u00a0copyless restriction.\u00a0<\/em>We say that a register update<\/p>\n

  <\/span>   <\/span>\"\[f : R \to (R \cup \Gamma)^*\]\"<\/p>\n

is\u00a0copyless\u00a0<\/em>if\u00a0every register \"r \in R\" appears in at most one word\u00a0\"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.<\/p>\n

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

Future oracle.\u00a0<\/strong>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.<\/p>\n

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.<\/p>\n

Theorem.\u00a0<\/strong>For every register transducer with a\u00a0future\u00a0oracle, there is\u00a0register transducer\u00a0(without any oracle), which defines the same function from words to words.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

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\u00a0streaming). This […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":789,"menu_order":3,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-842","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/842"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=842"}],"version-history":[{"count":4,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/842\/revisions"}],"predecessor-version":[{"id":1246,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/842\/revisions\/1246"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/789"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}