Abstract
We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.
| Original language | English |
|---|---|
| Pages (from-to) | 93-106 |
| Number of pages | 14 |
| Journal | Fundamenta Informaticae |
| Volume | 90 |
| Issue number | 1-2 |
| DOIs | |
| Publication status | Published - 2009 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics