The Magic Number Problem for Subregular Language Families
We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has alpha states, for all n and alpha satisfying n less or equal to alpha less or equal to exp(2...
| 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.1653v1 |
| _version_ | 1818485158721880064 |
|---|---|
| author | Markus Holzer Sebastian Jakobi Martin Kutrib |
| author_facet | Markus Holzer Sebastian Jakobi Martin Kutrib |
| author_sort | Markus Holzer |
| collection | DOAJ |
| description | We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has alpha states, for all n and alpha satisfying n less or equal to alpha less or equal to exp(2,n). A number alpha not satisfying this condition is called a magic number (for n). It was shown in [11] that no magic numbers exist for general regular languages, while in [5] trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, combinational languages, star-free, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic. |
| first_indexed | 2024-12-10T16:04:48Z |
| format | Article |
| id | doaj.art-b77da2bdaff547fd97512e12a254a339 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-10T16:04:48Z |
| publishDate | 2010-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-b77da2bdaff547fd97512e12a254a3392022-12-22T01:42:19ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802010-08-0131Proc. DCFS 201011011910.4204/EPTCS.31.13The Magic Number Problem for Subregular Language FamiliesMarkus HolzerSebastian JakobiMartin KutribWe investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has alpha states, for all n and alpha satisfying n less or equal to alpha less or equal to exp(2,n). A number alpha not satisfying this condition is called a magic number (for n). It was shown in [11] that no magic numbers exist for general regular languages, while in [5] trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, combinational languages, star-free, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.http://arxiv.org/pdf/1008.1653v1 |
| spellingShingle | Markus Holzer Sebastian Jakobi Martin Kutrib The Magic Number Problem for Subregular Language Families Electronic Proceedings in Theoretical Computer Science |
| title | The Magic Number Problem for Subregular Language Families |
| title_full | The Magic Number Problem for Subregular Language Families |
| title_fullStr | The Magic Number Problem for Subregular Language Families |
| title_full_unstemmed | The Magic Number Problem for Subregular Language Families |
| title_short | The Magic Number Problem for Subregular Language Families |
| title_sort | magic number problem for subregular language families |
| url | http://arxiv.org/pdf/1008.1653v1 |
| work_keys_str_mv | AT markusholzer themagicnumberproblemforsubregularlanguagefamilies AT sebastianjakobi themagicnumberproblemforsubregularlanguagefamilies AT martinkutrib themagicnumberproblemforsubregularlanguagefamilies AT markusholzer magicnumberproblemforsubregularlanguagefamilies AT sebastianjakobi magicnumberproblemforsubregularlanguagefamilies AT martinkutrib magicnumberproblemforsubregularlanguagefamilies |