Nondeterministic State Complexity for Suffix-Free Regular Languages
We investigate the nondeterministic state complexity of basic operations for suffix-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 acc...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2010-08-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1008.1661v1 |
| _version_ | 1818395225035374592 |
|---|---|
| author | Yo-Sub Han Kai Salomaa |
| author_facet | Yo-Sub Han Kai Salomaa |
| author_sort | Yo-Sub Han |
| collection | DOAJ |
| description | We investigate the nondeterministic state complexity of basic operations for suffix-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 consider basic operations (catenation, union, intersection, Kleene star, reversal and complementation) and establish matching upper and lower bounds for each operation. In the case of complementation the upper and lower bounds differ by an additive constant of two. |
| first_indexed | 2024-12-14T06:13:43Z |
| format | Article |
| id | doaj.art-d8610c8f0d6d4afd92276f75ca00c273 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-14T06:13:43Z |
| publishDate | 2010-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-d8610c8f0d6d4afd92276f75ca00c2732022-12-21T23:14:05ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802010-08-0131Proc. DCFS 201018919610.4204/EPTCS.31.21Nondeterministic State Complexity for Suffix-Free Regular LanguagesYo-Sub HanKai SalomaaWe investigate the nondeterministic state complexity of basic operations for suffix-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 consider basic operations (catenation, union, intersection, Kleene star, reversal and complementation) and establish matching upper and lower bounds for each operation. In the case of complementation the upper and lower bounds differ by an additive constant of two.http://arxiv.org/pdf/1008.1661v1 |
| spellingShingle | Yo-Sub Han Kai Salomaa Nondeterministic State Complexity for Suffix-Free Regular Languages Electronic Proceedings in Theoretical Computer Science |
| title | Nondeterministic State Complexity for Suffix-Free Regular Languages |
| title_full | Nondeterministic State Complexity for Suffix-Free Regular Languages |
| title_fullStr | Nondeterministic State Complexity for Suffix-Free Regular Languages |
| title_full_unstemmed | Nondeterministic State Complexity for Suffix-Free Regular Languages |
| title_short | Nondeterministic State Complexity for Suffix-Free Regular Languages |
| title_sort | nondeterministic state complexity for suffix free regular languages |
| url | http://arxiv.org/pdf/1008.1661v1 |
| work_keys_str_mv | AT yosubhan nondeterministicstatecomplexityforsuffixfreeregularlanguages AT kaisalomaa nondeterministicstatecomplexityforsuffixfreeregularlanguages |