Derived-term Automata for Extended Weighted Rational Expressions

Authors

Akim Demaille

Where

Proceedings of the Thirteenth International Colloquium on Theoretical Aspects of Computing (ICTAC)

Place

Taipei, Taiwan

Type

inproceedings

Publisher

Springer

Projects

Vcsn

Date

2016-07-06

Abstract

We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different constructrational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata. These constructs are implemented in Vcsn, a free-software platform dedicated to weighted automata and rational expressions.

Documents

• Paper
• Report

Bibtex (lrde.bib)

@InProceedings{	  demaille.16.ictac,
  author	= {Akim Demaille},
  title		= {Derived-term Automata for Extended Weighted Rational
		  Expressions},
  booktitle	= {Proceedings of the Thirteenth International Colloquium on
		  Theoretical Aspects of Computing (ICTAC)},
  year		= 2016,
  publisher	= {Springer},
  series	= {Lecture Notes in Computer Science},
  address	= {Taipei, Taiwan},
  month		= oct,
  abstract	= {We present an algorithm to build an automaton from a
		  rational expression. This approach introduces support for
		  extended weighted expressions. Inspired by derived-term
		  based algorithms, its core relies on a different construct,
		  rational expansions. We introduce an inductive algorithm to
		  compute the expansion of an expression from which the
		  automaton follows. This algorithm is independent of the
		  size of the alphabet, and actually even supports infinite
		  alphabets. It can easily be accommodated to generate
		  deterministic (weighted) automata. These constructs are
		  implemented in Vcsn, a free-software platform dedicated to
		  weighted automata and rational expressions.}
}