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.
|Title of host publication||Mathematical Foundations of Computer Science 2007 - 32nd International Symposium, MFCS 2007, Proceedings|
|Number of pages||12|
|Publication status||Published - 2007|
|Event||32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007 - Cesky Krumlov, Czech Republic|
Duration: 2007 Aug 26 → 2007 Aug 31
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007|
|Period||07/8/26 → 07/8/31|
Bibliographical noteFunding 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)