User: Guest  Login
Document type:
Technical Report 
Author(s):
Hermann Gruber; Markus Holzer 
Title:
Finite Automata, Digraph Connectivity, and Regular Expression Size 
Abstract:
We study some descriptional complexity aspects of regular expressions. In particular, we give lower bounds on the minimum required size for the conversion of deterministic finite automata into regular expressions and on the required size of regular expressions resulting from applying some basic language operations on them, namely intersection, shuffle, and complement. Some of the lower bounds obtained are asymptotically tight, and, notably, the examples we present are over an alphabet of size tw...    »
 
Keywords:
finite automata; regular expressions; digraph; connectivity; descriptional complexity 
Year:
2007 
Year / month:
2007-12-01 00:00:00 
Pages:
25