1 Search Results for "Razet, Beno�t"


Document
Average Analysis of Glushkov Automata under a BST-Like Model

Authors: Cyril Nicaud, Carine Pivoteau, and Benoît Razet

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


Abstract
We study the average number of transitions in Glushkov automata built from random regular expressions. This statistic highly depends on the probabilistic distribution set on the expressions. A recent work shows that, under the uniform distribution, regular expressions lead to automata with a linear number of transitions. However, uniform regular expressions are not necessarily a satisfying model. Therefore, we rather focus on an other model, inspired from random binary search trees (BST), which is widely used, in particular for testing. We establish that, in this case, the average number of transitions becomes quadratic according to the size of the regular expression.

Cite as

Cyril Nicaud, Carine Pivoteau, and Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 388-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{nicaud_et_al:LIPIcs.FSTTCS.2010.388,
  author =	{Nicaud, Cyril and Pivoteau, Carine and Razet, Beno\^{i}t},
  title =	{{Average Analysis of Glushkov Automata under a BST-Like Model}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{388--399},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.388},
  URN =		{urn:nbn:de:0030-drops-28809},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.388},
  annote =	{Keywords: Glushkov automata, random binary search tree, regular expression}
}
  • Refine by Author
  • 1 Nicaud, Cyril
  • 1 Pivoteau, Carine
  • 1 Razet, Benoît

  • Refine by Classification

  • Refine by Keyword
  • 1 Glushkov automata
  • 1 random binary search tree
  • 1 regular expression

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail