Derived-Term Automata of Multitape Expressions with Composition

Scientific Annals of Computer Science

article

A. Demaille¹ 

[1] EPITA Research and Development Laboratory (LRDE)

关键词: Antimirov;    automaton;    derivatives;    derived term;    expansion;    extended rational expressions;    transducer;    multitape;    composition;   

DOI  :  10.7561/SACS.2017.2.137

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

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.

【 授权许可】

CC BY-ND