Publications/demaille.16.ciaa

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 end, we propose the operator $\mid$ to build multitape expressions such as $(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

• Paper
• Report

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