10.4230/LIPICS.STACS.2011.495
Gulan, Stefan
Stefan
Gulan
Graphs Encoded by Regular Expressions
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
Digraphs
Regular Expressions
Finite Automata
Forbidden Minors
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
2011
2011-03-11
2011-03-11
2011-03-11
en
urn:nbn:de:0030-drops-30386
10.4230/LIPIcs.STACS.2011
978-3-939897-25-5
1868-8969
10.4230/LIPIcs.STACS.2011
LIPIcs, Volume 9, STACS 2011
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
2013
9
42
495
506
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2011
9
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
704279 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pages 495-506