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: https://drops.dagstuhl.de/opus/volltexte/2011/3038/
Gulan, Stefan
Graphs Encoded by Regular Expressions
| pdf-format: |
|
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 | |
| Seminar: | 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) | |
| Issue date: | 2011 | |
| Date of publication: | 11.03.2011 |
