Publications/demaille.17.sacs

Authors

Akim Demaille

Journal

Scientific Annals of Computer Science

Type

article

Publisher

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

Projects

Vcsn

Date

2017-01-01

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

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