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 条
  • [41] On a structural property in the state complexity of projected regular languages
    Jiraskova, Galina
    Masopust, Tomas
    THEORETICAL COMPUTER SCIENCE, 2012, 449 : 93 - 105
  • [42] State Complexity of Chop Operations on Unary and Finite Languages
    Holzer, Markus
    Jakobi, Sebastian
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012, 2012, 7386 : 169 - 182
  • [43] Quotient Complexity of Ideal Languages
    Brzozowski, Janusz
    Jiraskova, Galina
    Li, Baiyu
    LATIN 2010: THEORETICAL INFORMATICS, 2010, 6034 : 208 - +
  • [44] Quotient Complexity of Closed Languages
    Brzozowski, Janusz
    Jiraskova, Galina
    Zou, Chenglong
    THEORY OF COMPUTING SYSTEMS, 2014, 54 (02) : 277 - 292
  • [45] THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES
    Jiraskova, Galina
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (01) : 101 - 124
  • [46] On the state complexity of closures and interiors of regular languages with subwords and superwords
    Karandikar, P.
    Niewerth, M.
    Schnoebelen, Ph.
    THEORETICAL COMPUTER SCIENCE, 2016, 610 : 91 - 107
  • [47] Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata
    Geffert, Viliam
    Pighizzini, Giovanni
    LATIN 2010: THEORETICAL INFORMATICS, 2010, 6034 : 196 - +
  • [48] Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata
    Geffert, Viliam
    Pighizzini, Giovanni
    ALGORITHMICA, 2012, 63 (03) : 571 - 587
  • [49] Nondeterministic Communication Complexity of Random Boolean Functions
    Pourmoradnasseri, Mozhgan
    Theis, Dirk Oliver
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017), 2017, 10185 : 528 - 541
  • [50] Ordering regular languages and automata: Complexity
    D'Agostino, Giovanna
    Martincigh, Davide
    Policriti, Alberto
    THEORETICAL COMPUTER SCIENCE, 2023, 949
12345