Derived-Term Automata of Multitape Rational Expressions

Abstract

We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator ${\displaystyle \mid }$ to build multitape expressions such as ${\displaystyle (a^{+}\mid x+b^{+}\mid y)^{*}}$. We define expansionswhich generalize the concept of derivative of a rational expression, but relieved from the need of a free monoid. We propose an algorithm based on expansions to build multitape automata from multitape expressions.

Bibtex (lrde.bib)

```@InProceedings{	  demaille.16.ciaa,
author	= {Akim Demaille},
title		= {Derived-Term Automata of Multitape Rational Expressions},
booktitle	= {Proceedings of Implementation and Application of Automata,
21st International Conference (CIAA'16)},
editor	= {Yo-Sub Han and Kai Salomaa},
year		= 2016,
publisher	= {Springer},
pages		= {51--63},
isbn		= {978-3-319-40946-7},
doi		= {10.1007/978-3-319-40946-7_5},
anurl		= {http://dx.doi.org/10.1007/978-3-319-40946-7_5},
series	= {Lecture Notes in Computer Science},
volume	= 9705,
month		= jul,
abstract	= {We introduce (weighted) rational expressions to denote
series over Cartesian products of monoids. To this end, we
propose the operator \$\mid\$ to build multitape expressions
such as \$(a^+\mid x + b^+\mid y)^*\$. We define expansions,
which generalize the concept of derivative of a rational
expression, but relieved from the need of a free monoid. We
propose an algorithm based on expansions to build multitape
automata from multitape expressions.}
}```