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 条
  • [21] Decimations of languages and state complexity
    Krieger, Dalia
    Miller, Avery
    Rampersad, Narad
    Ravikumar, Bala
    Shallit, Jeffrey
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (24-25) : 2401 - 2409
  • [22] State Complexity of Union and Intersection for Two-Way Nondeterministic Finite Automata
    Kunc, Michal
    Okhotin, Alexander
    FUNDAMENTA INFORMATICAE, 2011, 110 (1-4) : 231 - 239
  • [23] The State Complexity of Star-Complement-Star
    Jiraskova, Galina
    Shallit, Jeffrey
    DEVELOPMENTS IN LANGUAGE THEORY (DLT 2012), 2012, 7410 : 380 - 391
  • [24] NONDETERMINISTIC FINITE AUTOMATA - RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
    Holzer, Markus
    Kutrib, Martin
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2009, 20 (04) : 563 - 580
  • [25] State Complexity of Finite Partial Languages
    Kutrib, Martin
    Wendlandt, Matthias
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2022, 2022, 13439 : 170 - 183
  • [26] State complexity of finite partial languages
    Kutrib, Martin
    Wendlandt, Matthias
    THEORETICAL COMPUTER SCIENCE, 2023, 966
  • [27] State complexity of permutation on finite languages over a binary alphabet
    Cho, Da-Jung
    Goc, Daniel
    Han, Yo-Sub
    Ko, Sang-Ki
    Palioudakis, Alexandros
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2017, 682 : 67 - 78
  • [28] Concatenation of Regular Languages and Descriptional Complexity
    Jiraskova, Galina
    THEORY OF COMPUTING SYSTEMS, 2011, 49 (02) : 306 - 318
  • [29] State Complexity of Binary Coded Regular Languages
    Geffert, Viliam
    Palisinova, Dominika
    Szabari, Alexander
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2022, 2022, 13439 : 72 - 84
  • [30] State complexity of the concatenation of regular tree languages
    Piao, Xiaoxue
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2012, 429 : 273 - 281
12345