Minimalizations of NFA using the universal automaton

被引：16

作者：

Polák, L ^{[1
]}

机构：

[1] Masaryk Univ, Dept Math, Brno 66295, Czech Republic

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2005年 / 16卷 / 05期

关键词：

minimalization of NFA; universal automaton;

D O I：

10.1142/S0129054105003431

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

As is well known, each minimal NFA for a regular language L is isomorphic to a subautomaton of the so-called universal automaton U for L. We explore and compare various conditions on sets of states of U which are related to the fact that induced subautomata of U accept the whole language L. The methods of several previous works on minimalizations of NFA can be modified so that they fit in our approach. We also propose a new algorithm which is easy to implement.

引用

页码：999 / 1010

页数：12

共 12 条

[1] [Anonymous], P S MATH THEOR AUT N
[2] ARNOLD A, 1992, B EATCS, V47, P166
[3] CARREZ C, 1970, MINIMALIZATION NONDE
[4] CONWAY JH, 1971, REGULAR ALGEBRA FINI
[5] Denis F, 2002, FUND INFORM, V51, P339
[6] A NOTE ON THE SPACE COMPLEXITY OF SOME DECISION-PROBLEMS FOR FINITE AUTOMATA
JIANG, T
RAVIKUMAR, B
[J]. INFORMATION PROCESSING LETTERS, 1991, 40 (01) : 25 - 31
[7] ON STATE MINIMIZATION OF NONDETERMINISTIC FINITE AUTOMATA
KAMEDA, T
WEINER, P
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1970, C 19 (07) : 617 - &
[8] LOMBARDY S, 2002, SPRINGER LECT NOTES, V2380, P170
[9] Matz O., 1995, BRICS NOTES SERIES, P74
[10] POLAK L, 2003, SPRINGER LECT NOTES, V2710, P411

← 1 2 →