Derived-Term Automata of 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 end, we propose the operator mid to build multitape expressions such as (a^+∣x + b^+∣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.}
}