Derived-Term Automata of Multitape Expressions with Composition
Akim Demaille · Scientific Annals of Computer Science · 2017
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 + |x+b + |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.