
Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, captured by a deterministic two-way transducer, can be described with a regular transducer expression (RTE). For infinite words, the transducer uses Muller acceptance and $��$-regular look-ahead. \RTEs are constructed from constant functions using the combinators if-then-else (deterministic choice), Hadamard product, and unambiguous versions of the Cauchy product, the 2-chained Kleene-iteration and the 2-chained omega-iteration. Our proof works for transformations of both finite and infinite words, extending the result on finite words of Alur et al.\ in LICS'14. In order to construct an RTE associated with a deterministic two-way Muller transducer with look-ahead, we introduce the notion of transition monoid for such two-way transducers where the look-ahead is captured by some backward deterministic B��chi automaton. Then, we use an unambiguous version of Imre Simon's famous forest factorization theorem in order to derive a "good" ($��$-)regular expression for the domain of the two-way transducer. "Good" expressions are unambiguous and Kleene-plus as well as $��$-iterations are only used on subexpressions corresponding to \emph{idempotent} elements of the transition monoid. The combinator expressions are finally constructed by structural induction on the "good" ($��$-)regular expression describing the domain of the transducer.
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, [INFO] Computer Science [cs]
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, [INFO] Computer Science [cs]
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
