STATE COMPLEXITY AND APPROXIMATION

被引：2

作者：

Gao, Yuan ^{[1
]}

Yu, Sheng ^{[1
]}

机构：

[1] Univ Western Ontario, Dept Comp Sci, London, ON, Canada

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2012年 / 23卷 / 05期

关键词：

Regular languages; state complexity; finite automata; undecidability; approximation; combined operations; 2 COMBINED OPERATIONS; TRANSITION COMPLEXITY; CATENATION; BOUNDS;

D O I：

10.1142/S0129054112400461

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We discuss a number of essential questions concerning the state complexity research. The questions include why many basic problems were not studied earlier, whether there is a general algorithm for state complexity of combined operations, and whether there is a new and effective approach in this area of research. The concept of state complexity approximation is also discussed. We show that state complexity approximation can be used to obtain good results when the exact state complexities are difficult to find and when the exact state complexities are too complex to comprehend. We also list a number of questions for future research in this area.

引用

页码：1085 / 1098

页数：14

共 33 条

[1] Enumeration and generation with a string automata representation [J].

Almeida, Marco ;

Moreira, Nelma ;

Reis, Rogerio .

THEORETICAL COMPUTER SCIENCE, 2007, 387 (02) :93-102

[2]

[Anonymous], THEORY AUTOMATA

[3]

[Anonymous], 1990, Introduction to Algorithms

[4] STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION [J].

Cui, Bo ;

Gao, Yuan ;

Kari, Lila ;

Yu, Sheng .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2011, 22 (08) :1797-1812

[5] Lower bounds for the transition complexity of NFAs [J].

Domaratzki, Michael ;

Salomaa, Kai .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (07) :1116-1130

[6] Transition complexity of language operations [J].

Domaratzki, Michael ;

Salomaa, Kai .

THEORETICAL COMPUTER SCIENCE, 2007, 387 (02) :147-154

[7]

ELLUL K, 2002, THESIS U WATERLOO ON

[8] Estimation of state complexity of combined operations [J].

Esik, Zoltan ;

Gao, Yuan ;

Liu, Guangwu ;

Yu, Sheng .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (35) :3272-3280

[9] TEST SELECTION BASED ON FINITE STATE MODELS [J].

FUJIWARA, S ;

BOCHMANN, GV ;

KHENDEK, F ;

AMALOU, M ;

GHEDAMSI, A .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1991, 17 (06) :591-603

[10]

Gao Y., 2009, Proc. of Descriptional Complexity of Formal Systems, P163

← 1 2 3 4 →