On the State Complexity of Star of Union and Star of Intersection

被引：12

作者：

Jiraskova, Galina ^{[2
]}

Okhotin, Alexander ^{[1
]}

机构：

[1] Univ Turku, Dept Math, FIN-20014 Turku, Finland

[2] Slovak Acad Sci, Math Inst, Kosice 04001, Slovakia

来源：

FUNDAMENTA INFORMATICAE | 2011年 / 109卷 / 02期

基金：

芬兰科学院;

关键词：

Descriptional complexity; finite automata; state complexity; combined operations; COMBINED OPERATIONS; REGULAR LANGUAGES; REVERSAL;

D O I：

10.3233/FI-2011-502

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2(m+n-1) - 2(m-1) - 2(n-1) + 1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2(mn) for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu ("State complexity of combined operations", Theoret. Comput. Sci., 383 (2007) 140-152).

引用

页码：161 / 178

页数：18

共 9 条

[1] State complexity of cyclic shift [J].