| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438027 | Theoretical Computer Science | 2009 | 12 Pages |
Abstract
We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
