Difference between revisions of "Publications/demaille.17.ictac"

From LRDE

(Created page with "{{Publication | published = true | date = 2017-07-05 | authors = Akim Demaille, Thibaud Michaud | title = Quotient Operators for Weighted Rational Expressions | booktitle = Pr...")
 
 
(6 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
| date = 2017-07-05
 
| date = 2017-07-05
 
| authors = Akim Demaille, Thibaud Michaud
 
| authors = Akim Demaille, Thibaud Michaud
| title = Quotient Operators for Weighted Rational Expressions
+
| title = Derived-Term Automata of Weighted Rational Expressions with Quotient Operators
 
| booktitle = Proceedings of the Thirteenth International Colloquium on Theoretical Aspects of Computing (ICTAC)
 
| booktitle = Proceedings of the Thirteenth International Colloquium on Theoretical Aspects of Computing (ICTAC)
 
| publisher = Springer
 
| publisher = Springer
 
| series = Lecture Notes in Computer Science
 
| series = Lecture Notes in Computer Science
 +
| volume = 10580
 +
| pages = 155 to 173
 
| address = Hanoi, Vietnam
 
| address = Hanoi, Vietnam
| abstract = Quotients of words play a key role in formal language theory, however they have been rarely studied in the context of weighted rational expressions. We define the left and right quotients of rational series, and introduce corresponding operators for weighted expressions. We generalize an alternative construction of the derived-term (or Antimirov, or equation) automaton, based on expansions, to handle these operators.
+
| 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.
 
| lrdeprojects = Vcsn
 
| lrdeprojects = Vcsn
 +
| lrdepaper = http://www.lrde.epita.fr/dload/papers/demaille.17.ictac.pdf
 
| lrdenewsdate = 2017-07-05
 
| lrdenewsdate = 2017-07-05
| note = accepted
 
 
| type = inproceedings
 
| type = inproceedings
 
| id = demaille.17.ictac
 
| id = demaille.17.ictac
Line 17: Line 19:
 
@InProceedings<nowiki>{</nowiki>   demaille.17.ictac,
 
@InProceedings<nowiki>{</nowiki>   demaille.17.ictac,
 
   author = <nowiki>{</nowiki>Akim Demaille and Thibaud Michaud<nowiki>}</nowiki>,
 
   author = <nowiki>{</nowiki>Akim Demaille and Thibaud Michaud<nowiki>}</nowiki>,
   title = <nowiki>{</nowiki>Quotient Operators for Weighted Rational Expressions<nowiki>}</nowiki>,
+
   title = <nowiki>{</nowiki>Derived-Term Automata of Weighted Rational Expressions
 +
  with Quotient Operators<nowiki>}</nowiki>,
 
   booktitle = <nowiki>{</nowiki>Proceedings of the Thirteenth International Colloquium on
 
   booktitle = <nowiki>{</nowiki>Proceedings of the Thirteenth International Colloquium on
 
  Theoretical Aspects of Computing (ICTAC)<nowiki>}</nowiki>,
 
  Theoretical Aspects of Computing (ICTAC)<nowiki>}</nowiki>,
Line 23: Line 26:
 
   publisher = <nowiki>{</nowiki>Springer<nowiki>}</nowiki>,
 
   publisher = <nowiki>{</nowiki>Springer<nowiki>}</nowiki>,
 
   series = <nowiki>{</nowiki>Lecture Notes in Computer Science<nowiki>}</nowiki>,
 
   series = <nowiki>{</nowiki>Lecture Notes in Computer Science<nowiki>}</nowiki>,
 +
  volume = <nowiki>{</nowiki>10580<nowiki>}</nowiki>,
 +
  pages = <nowiki>{</nowiki>155--173<nowiki>}</nowiki>,
 
   address = <nowiki>{</nowiki>Hanoi, Vietnam<nowiki>}</nowiki>,
 
   address = <nowiki>{</nowiki>Hanoi, Vietnam<nowiki>}</nowiki>,
 
   month = oct,
 
   month = oct,
   abstract = <nowiki>{</nowiki>Quotients of words play a key role in formal language
+
   abstract = <nowiki>{</nowiki>Quotient operators have been rarely studied in the context
  theory, however they have been rarely studied in the
+
  of weighted rational expressions and automaton
  context of weighted rational expressions. We define the
+
  generation---in spite of the key role played by the
  left and right quotients of rational series, and introduce
+
  quotient of words in formal language theory. To handle both
  corresponding operators for weighted expressions. We
+
  left- and right-quotients we generalize an expansion-based
  generalize an alternative construction of the derived-term
+
  construction of the derived-term (or Antimirov, or
  (or Antimirov, or equation) automaton, based on expansions,
+
  equation) automaton and rely on support for a transposition
  to handle these operators.<nowiki>}</nowiki>,
+
  (or reversal) operator. The resulting automata may have
  note = <nowiki>{</nowiki>accepted<nowiki>}</nowiki>
+
  spontaneous transitions, which requires different
 +
  techniques from the usual derived-term constructions. <nowiki>}</nowiki>
 
<nowiki>}</nowiki>
 
<nowiki>}</nowiki>
  
 
}}
 
}}

Latest revision as of 15:17, 29 October 2018

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.

Documents

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},
  volume	= {10580},
  pages		= {155--173},
  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. }
}