LIPIcs.STACS.2011.495.pdf
- Filesize: 0.67 MB
- 12 pages
Document
Graphs Encoded by Regular Expressions
Author
-
Part of:
Volume:
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-03-11
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.STACS.2011.495
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.
Subject Classification
Keywords
- Digraphs
- Regular Expressions
- Finite Automata
- Forbidden Minors
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads