Derived-Term Automata of Multitape Rational Expressions

From LRDE

Abstract

We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mid} to build multitape expressions such as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.

Documents

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},
  address	= {Seoul, South Korea},
  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.}
}