Determination of finite automata accepting subregular languages

被引：37

作者：

Bordihn, Henning ^{[2
]}

Holzer, Markus ^{[1
,3
]}

Kutrib, Martin ^{[1
]}

机构：

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

[2] Univ Potsdam, Inst Informat, D-14482 Potsdam, Germany

[3] Tech Univ Munich, Inst Informat, D-85748 Garching, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 35期

关键词：

State complexity; Determination; Subregular languages; Finite automata; EVENTS; DEFINITE;

D O I：

10.1016/j.tcs.2009.05.019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：3209 / 3222

页数：14

共 22 条

[1] ROOTS OF STAR EVENTS [J].