A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910734685831168 |
|---|---|
| author | Petrov, Semyon Okhotin, Alexander |
| author_facet | Petrov, Semyon Okhotin, Alexander |
| contents | This paper establishes a lower bound on the number of states necessary in the worst case to simulate an $n$-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every $n$, there is a language recognized by an $n$-state 2NFA that requires a UFA with at least $\sum_{k=1}^{n} (k - 1)! \cdot k! \cdot \mathrm{stirling2}(n, k) \cdot \mathrm{stirling2}(n+1, k)$ = $Ω\big( n^{2n+2} / e^{2n} \big)$ states, where $\mathrm{stirling2}(n, k)$ denotes Stirling's numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which is constructed for the universal language for $n$-state 2NFAs, and describes every possible behaviour of these automata during their computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06283 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata Petrov, Semyon Okhotin, Alexander Formal Languages and Automata Theory 68Q45 This paper establishes a lower bound on the number of states necessary in the worst case to simulate an $n$-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every $n$, there is a language recognized by an $n$-state 2NFA that requires a UFA with at least $\sum_{k=1}^{n} (k - 1)! \cdot k! \cdot \mathrm{stirling2}(n, k) \cdot \mathrm{stirling2}(n+1, k)$ = $Ω\big( n^{2n+2} / e^{2n} \big)$ states, where $\mathrm{stirling2}(n, k)$ denotes Stirling's numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which is constructed for the universal language for $n$-state 2NFAs, and describes every possible behaviour of these automata during their computation. |
| title | A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata |
| topic | Formal Languages and Automata Theory 68Q45 |
| url | https://arxiv.org/abs/2412.06283 |