Multitape Rational Expressions

Authors

Akim Demaille

Where

Proceedings of Implementation and Application of Automata21st International Conference (CIAA'16)

Place

Seoul, South Korea

Type

inproceedings

Publisher

Springer

Projects

Vcsn

Date

2016-04-26

Abstract

We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this endwe propose the operator $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^+∣x + b^+∣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.

Bibtex (lrde.bib)

@InProceedings{	  demaille.16.ciaa,
  author	= {Akim Demaille},
  title		= {Multitape Rational Expressions},
  booktitle	= {Proceedings of Implementation and Application of Automata,
		  21st International Conference (CIAA'16)},
  year		= 2016,
  publisher	= {Springer},
  series	= {Lecture Notes in Computer Science},
  address	= {Seoul, South Korea},
  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.},
  note		= {accepted}
}