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.
| Original language | English |
|---|---|
| Pages (from-to) | 2537-2548 |
| Number of pages | 12 |
| Journal | Theoretical Computer Science |
| Volume | 410 |
| Issue number | 27-29 |
| DOIs | |
| Publication status | Published - 2009 Jun 28 |
Bibliographical note
Funding Information:Han was supported by the IT R&D program of MKE/IITA 2008-S-024-01 and Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)