Derived-Term Automata of Multitape Expressions with Composition

Authors

Akim Demaille

Journal

Scientific Annals of Computer Science

Type

article

Publisher

“A.I. Cuza” University Press, Iac si

Projects

Vcsn

Date

2017-12-29

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 transducersand 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.

Bibtex (lrde.bib)

@Article{	  demaille.17.sacs,
  title		= {Derived-Term Automata of Multitape Expressions with
		  Composition},
  author	= {Akim Demaille},
  journal	= {Scientific Annals of Computer Science},
  volume	= {27},
  number	= {2},
  organization	= {``A.I. Cuza'' University, Ia\c si, Rom\^ania},
  year		= {2017},
  pages		= {137--176},
  doi		= {10.7561/SACS.2017.2.137},
  publisher	= {``A.I. Cuza'' University Press, Ia\c si},
  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 \emph{expansions}. This approach generates small
		  automata, and even allows us to support a composition
		  operator.}
}