Search Results

Documents authored by Gulan, Stefan

Document
DOI: 10.4230/LIPIcs.STACS.2011.495
Graphs Encoded by Regular Expressions

Authors: Stefan Gulan

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In the conversion of finite automata to regular expressions, an exponential blowup in size can generally not be avoided. This is due to graph-structural properties of automata which cannot be directly encoded by regular expressions and cause the blowup combinatorially. In order to identify these structures, we generalize the class of arc-series-parallel digraphs to the acyclic case. The resulting digraphs are shown to be reversibly encoded by linear-sized regular expressions. We further derive a characterization of our new class by a finite set of forbidden minors and argue that these minors constitute the primitives causing the blowup in the conversion from automata to expressions.
Cite as

Stefan Gulan. Graphs Encoded by Regular Expressions. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 495-506, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gulan:LIPIcs.STACS.2011.495,
  author =	{Gulan, Stefan},
  title =	{{Graphs Encoded by Regular Expressions}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{495--506},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.495},
  URN =		{urn:nbn:de:0030-drops-30386},
  doi =		{10.4230/LIPIcs.STACS.2011.495},
  annote =	{Keywords: Digraphs, Regular Expressions, Finite Automata, Forbidden Minors}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1754
An Optimal Construction of Finite Automata from Regular Expressions

Authors: Stefan Gulan and Henning Fernau

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

Abstract
We consider the construction of finite automata from their corresponding regular expressions by a series of digraph-transformations along the expression\'s structure. Each intermediate graph represents an extended finite automaton accepting the same language. The character of our construction allows a fine-grained analysis of the emerging automaton\'s size, eventually leading to an optimality result.
Cite as

Stefan Gulan and Henning Fernau. An Optimal Construction of Finite Automata from Regular Expressions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 211-222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{gulan_et_al:LIPIcs.FSTTCS.2008.1754,
  author =	{Gulan, Stefan and Fernau, Henning},
  title =	{{An Optimal Construction of Finite Automata from Regular Expressions}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{211--222},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1754},
  URN =		{urn:nbn:de:0030-drops-17544},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1754},
  annote =	{Keywords: Finite automata,regular expressions,descriptional complexity}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact