License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.495
URN: urn:nbn:de:0030-drops-30386
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3038/
Go to the corresponding LIPIcs Volume Portal

Gulan, Stefan

Graphs Encoded by Regular Expressions

pdf-format:
46.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{gulan:LIPIcs:2011:3038,
  author =	{Stefan Gulan},
  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 =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3038},
  URN =		{urn:nbn:de:0030-drops-30386},
  doi =		{10.4230/LIPIcs.STACS.2011.495},
  annote =	{Keywords: Digraphs, Regular Expressions, Finite Automata, Forbidden Minors}
}

Keywords: Digraphs, Regular Expressions, Finite Automata, Forbidden Minors
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI