Back to Search
Start Over
NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Source :
- International Journal of Foundations of Computer Science. 20:563-580
- Publication Year :
- 2009
- Publisher :
- World Scientific Pub Co Pte Lt, 2009.
-
Abstract
- Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.
- Subjects :
- Deterministic finite automaton
Theoretical computer science
Nested word
DFA minimization
Powerset construction
Computer Science (miscellaneous)
Quantum finite automata
Automata theory
Nondeterministic finite automaton
ω-automaton
Computer Science::Formal Languages and Automata Theory
Mathematics
Subjects
Details
- ISSN :
- 17936373 and 01290541
- Volume :
- 20
- Database :
- OpenAIRE
- Journal :
- International Journal of Foundations of Computer Science
- Accession number :
- edsair.doi...........dd02d317bbe012bf32ade896aa2c34fc