Derived-term automata of multitape expressions with composition

Abstract

Rational expressions are powerful tools to define automata, but often restricted to single-tape automata. Our goal is to unleash their expressive power for transducers, and more generally, any multitape automaton; for instance $(a^+\mathbin{\vert} x + b^+\mathbin{\vert} y)^*$. We generalize the construction of the derived-term automaton by using expansions. This approach generates small automata, and even allows us to support a composition operator.