Publications/demaille.17.ictac

Authors

Akim Demaille, Thibaud Michaud

Where

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

Place

Hanoi, Vietnam

Type

inproceedings

Publisher

Springer

Projects

Vcsn

Date

2017-07-05

Abstract

Quotient operators have been rarely studied in the context of weighted rational expressions and automaton generation---in spite of the key role played by the quotient of words in formal language theory. To handle both left- and right-quotients we generalize an expansion-based construction of the derived-term (or Antimirov, or equation) automaton and rely on support for a transposition (or reversal) operator. The resulting automata may have spontaneous transitions, which requires different techniques from the usual derived-term constructions.

Bibtex (lrde.bib)

@InProceedings{	  demaille.17.ictac,
  author	= {Akim Demaille and Thibaud Michaud},
  title		= {Derived-Term Automata of Weighted Rational Expressions
		  with Quotient Operators},
  booktitle	= {Proceedings of the Thirteenth International Colloquium on
		  Theoretical Aspects of Computing (ICTAC)},
  year		= 2017,
  publisher	= {Springer},
  series	= {Lecture Notes in Computer Science},
  address	= {Hanoi, Vietnam},
  month		= oct,
  abstract	= {Quotient operators have been rarely studied in the context
		  of weighted rational expressions and automaton
		  generation---in spite of the key role played by the
		  quotient of words in formal language theory. To handle both
		  left- and right-quotients we generalize an expansion-based
		  construction of the derived-term (or Antimirov, or
		  equation) automaton and rely on support for a transposition
		  (or reversal) operator. The resulting automata may have
		  spontaneous transitions, which requires different
		  techniques from the usual derived-term constructions. },
  note		= {accepted}
}