State complexity of basic operations on suffix-free regular languages |
| |
| Authors: | Yo-Sub Han Kai Salomaa |
| |
| Affiliation: | 1. Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea;2. School of Computing, Queen’s University, Kingston, Ontario K7L 3N6, Canada |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
