KLEENE CLOSURE AND STATE COMPLEXITY

被引：6

作者：

Palmovsky, Matus ^{[1
]}

机构：

[1] Slovak Acad Sci, Math Inst, Gresakova 6, Kosice 04001, Slovakia

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2016年 / 50卷 / 03期

关键词：

Regular languages; finite automata; Kleene closure; state complexity; REGULAR LANGUAGES; FINITE AUTOMATA; MAGIC NUMBERS;

D O I：

10.1051/ita/2016024

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that the automaton presented by Maslov [Soviet Math. Doklady 11 (1970) 13731375] meets the upper bound 3/4 center dot 2(n) on the state complexity of Kleene closure. Our main result shows that the upper bounds 2(n-1) + 2(n-1-k) on the state complexity of Kleene closure of a language accepted by an n-state DFA with k final states are tight for every k with 1 <= k <= n in the binary case. We also study Kleene Closure on prefix-free languages. In the case of prefix-free languages, the Kleene closure may attain just three possible complexities n - 2, n - 1, and n. We give some survey of our computations.

引用

页码：251 / 261

页数：11

共 18 条

[1]

[Anonymous], 1970, Soviet Mathematics Doklady

[2]

BRZOZOWSKI JA, 1980, THEOR COMPUT SCI, V10, P19, DOI 10.1016/0304-3975(80)90069-9

[3]

Cevorova K., 2013, LECT NOTES COMPUT SC, V8031, P277

[4]

Gao Y., 2016, TECHNICAL REPORT

[5] State complexity of union and intersection of star on k regular languages [J].

Gao, Yuan ;

Kari, Lila ;

Yu, Sheng .

THEORETICAL COMPUTER SCIENCE, 2012, 429 :98-107

[6] Magic numbers in the state hierarchy of finite automata [J].

Geffert, Villam .

INFORMATION AND COMPUTATION, 2007, 205 (11) :1652-1670

[7]

Han Y., 2009, AUTOMATA FORMAL LANG, P99

[8]

Hopcroft J., 1971, STANCS71190 COMP SCI

[9] Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs [J].

Iwama, K ;

Kambayashi, Y ;

Takaki, K .

THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) :485-494

[10]

Iwama K., 1997, THEORET COMPUT SCI

← 1 2 →