Konferenzpaper

Herausgeberliste: Champarnaud, JM; Maurel, D

Jahr der Veröffentlichung: 2003

Seiten: 148-157

Zeitschrift: Lecture notes in computer science

Bandnummer: 2608

ISSN: 0302-9743

ISBN: 3-540-40391-4

Konferenz: 7th International Conference on Implementation and Application of Automata

Verlag: Springer

Serientitel: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
The state complexities of basic operations on nondeterministic finite automata (NFA) are investigated. In particular, we consider Boolean operations, catenation operations - concatenation, iteration, lambda-free iteration - and the reversal on NFAs that accept finite and infinite languages over arbitrary alphabets. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. For the complementation. tight bounds in the order of magnitude are proved. It turns out that the state complexities of operations on NFAs and deterministic finite automata (DFA) are quite different. For example, the reversal and concatenation have exponential state complexity on DFAs but linear complexity on NFAs. Conversely, the complementation can be done with linear complexity on DFAs but needs exponentially many states on NFAs.

Harvard-Zitierstil: Holzer, M. and Kutrib, M. (2003) State complexity of basic operations on nondeterministic finite automata, Lecture notes in computer science (Schriftenreihe), 2608, pp. 148-157

APA-Zitierstil: Holzer, M., & Kutrib, M. (2003). State complexity of basic operations on nondeterministic finite automata. Lecture notes in computer science (Schriftenreihe). 2608, 148-157.