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 条
  • [1] Nondeterministic state complexity of star-free languages
    Holzer, Markus
    Kutrib, Martin
    Meckel, Katja
    THEORETICAL COMPUTER SCIENCE, 2012, 450 : 68 - 80
  • [2] QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
    Brzozowski, Janusz
    Liu, Bo
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (06) : 1261 - 1276
  • [3] On the Shuffle of Star-Free Languages
    Castiglione, Giusi
    Restivo, Antonio
    FUNDAMENTA INFORMATICAE, 2012, 116 (1-4) : 35 - 44
  • [4] Alternating finite automata and star-free languages
    Salomaa, K
    Yu, S
    THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) : 167 - 176
  • [5] Operations on Subregular Languages and Nondeterministic State Complexity
    Hospodar, Michal
    Mlynarcik, Peter
    Olejar, Viktor
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2022, 2022, 13439 : 112 - 126
  • [6] Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
    Han, Yo-Sub
    Salomaa, Kai
    Wood, Derick
    FUNDAMENTA INFORMATICAE, 2009, 90 (1-2) : 93 - 106
  • [7] On the expressiveness of spider diagrams and commutative star-free regular languages
    Delaney, Aidan
    Stapleton, Gem
    Taylor, John
    Thompson, Simon
    JOURNAL OF VISUAL LANGUAGES AND COMPUTING, 2013, 24 (04) : 273 - 288
  • [8] Square, Power, Positive Closure, and Complementation on Star-Free Languages
    Davies, Sylvie
    Hospodar, Michal
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2019, 2019, 11612 : 98 - 110
  • [9] Nondeterministic complexity in subclasses of convex languages
    Hospodar, Michal
    Jiraskova, Galina
    Mlynarcik, Peter
    THEORETICAL COMPUTER SCIENCE, 2019, 787 : 89 - 110
  • [10] State complexity of union and intersection of star on k regular languages
    Gao, Yuan
    Kari, Lila
    Yu, Sheng
    THEORETICAL COMPUTER SCIENCE, 2012, 429 : 98 - 107
12345