Nondeterministic state complexity of square root
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909013102297088 |
|---|---|
| author | Onishchenko, Sergey |
| author_facet | Onishchenko, Sergey |
| contents | We investigate the nondeterministic state complexity of the square-root operation $\sqrt{L}=\{\,w \mid ww\in L\,\}$ on regular languages represented by nondeterministic finite automata. For an $n$-state NFA accepting $L$, it was previously known that $\sqrt{L}$ can be accepted by an NFA with at most $n^{3}$ states, while the best lower bound was only (n-1)(n-2)(n-3). In this paper, we close this gap completely and prove that $n^{3}$ states are sufficient and necessary in the worst case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02957 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nondeterministic state complexity of square root Onishchenko, Sergey Formal Languages and Automata Theory We investigate the nondeterministic state complexity of the square-root operation $\sqrt{L}=\{\,w \mid ww\in L\,\}$ on regular languages represented by nondeterministic finite automata. For an $n$-state NFA accepting $L$, it was previously known that $\sqrt{L}$ can be accepted by an NFA with at most $n^{3}$ states, while the best lower bound was only (n-1)(n-2)(n-3). In this paper, we close this gap completely and prove that $n^{3}$ states are sufficient and necessary in the worst case. |
| title | Nondeterministic state complexity of square root |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2605.02957 |