Nondeterministic State Complexity of Star-Free Languages

被引：0

作者：

Holzer, Markus ^{[1
]}

Kutrib, Martin ^{[1
]}

Meckel, Katja ^{[1
]}

机构：

[1] Univ Giessen, Inst lnformat, D-35392 Giessen, Germany

来源：

IMPLEMENTATION AND APPLICATION OF AUTOMATA | 2011年 / 6807卷

关键词：

FINITE AUTOMATA; REGULAR LANGUAGES; OPERATIONS; EVENTS; SIZE;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained in [8] for the operation problem of star-free languages accepted by deterministic finite automata.

引用

页码：178 / 189

页数：12

共 50 条

[31] On State Complexity of Finite Word and Tree Languages
Gandhi, Aniruddh
Khoussainov, Bakhadyr
Liu, Jiamou
DEVELOPMENTS IN LANGUAGE THEORY (DLT 2012), 2012, 7410 : 392 - 403
[32] On the average state and transition complexity of finite languages
Gruber, Hermann
Holzer, Markus
THEORETICAL COMPUTER SCIENCE, 2007, 387 (02) : 155 - 166
[33] State complexity of binary coded regular languages
Geffert, Viliam
Palisinova, Dominika
Szabari, Alexander
THEORETICAL COMPUTER SCIENCE, 2024, 990
[34] INTERSECTION AND UNION OF REGULAR LANGUAGES AND STATE COMPLEXITY
BIRGET, JC
INFORMATION PROCESSING LETTERS, 1992, 43 (04) : 185 - 190
[35] State Complexity Investigations on Commutative Languages - the Upward and Downward Closure, Commutative Aperiodic and Commutative Group Languages
Hoffmann, Stefan
DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2021, 2021, 13037 : 64 - 75
[36] NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY
Holzer, Markus
Jakobi, Sebastian
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (07) : 837 - 855
[37] State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Gao, Yuan
Yu, Sheng
FUNDAMENTA INFORMATICAE, 2012, 116 (1-4) : 79 - 92
[38] State complexity of union and intersection of square and reversal on k regular languages
Gao, Yuan
Kari, Lila
Yu, Sheng
THEORETICAL COMPUTER SCIENCE, 2012, 454 : 164 - 171
[39] State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
Hoffmann, Stefan
INFORMATION AND COMPUTATION, 2024, 301
[40] On the State Complexity of Scattered Substrings and Superstrings
Okhotin, Alexander
FUNDAMENTA INFORMATICAE, 2010, 99 (03) : 325 - 338

← 1 2 3 4 5 →