Series Parallel Digraphs with Loops |
| |
Authors: | Stefan Gulan |
| |
Affiliation: | 1. FB IV—Informatik, Universit?t Trier, 54286, Trier, Germany
|
| |
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 beyond the acyclic case. The resulting digraphs are shown to be reversibly encoded by linear-sized regular expressions. Also, a characterization of this new class by a set of seven forbidden substructures is given. Automata that require expressions of superlinear size must contain some of these substructures. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|