Finite Automata, Digraph Connectivity, and Regular Expression Size
Finite Automata, Digraph Connectivity, and Regular Expression Size
复制标题
有限自动机、有向图连通性和正则表达式大小
DOI：
10.1007/978-3-540-70583-3_4
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Holzer
中科院分区：
文献类型：
--
作者：
Hermann Gruber;M. Holzer
最近，Gelade 和 Neven [8] 给出了将确定性有限自动机转换为正则表达式所需的最小大小以及通过对其应用一些基本语言操作而产生的正则表达式所需大小的下限。我们加强和扩展了这些结果，获得了部分最优的下界，值得注意的是，所提供的示例是基于二进制字母表的，这是最好的可能。为此，我们开发了一种不同的、更通用的下界技术，该技术基于常规语言的星号高度。众所周知，对于受限类别的常规语言，可以根据接受该语言的最小有限自动机的转换结构下面的有向图来确定星形高度。通过这种方式，星形高度与循环等级相关联，循环等级是 Eggan 和 Buchi 提出的有向图的结构复杂性度量，用于衡量有向图的连通程度。
Recently 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, were given by Gelade and Neven [8]. We strengthen and extend these results, obtaining lower bounds that are in part optimal, and, notably, the presented examples are over a binary alphabet, which is best possible. To this end, we develop a different, more versatile lower bound technique that is based on the star height of regular languages. It is known that for a restricted class of regular languages, the star height can be determined from the digraph underlying the transition structure of the minimal finite automaton accepting that language. In this way, star height is tied to cycle rank, a structural complexity measure for digraphs proposed by Eggan and Buchi, which measures the degree of connectivity of directed graphs.