Complexity of Unary Exclusive Nondeterministic Finite Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916388608671744 |
|---|---|
| author | Kutrib, Martin Malcher, Andreas Wendlandt, Matthias |
| author_facet | Kutrib, Martin Malcher, Andreas Wendlandt, Matthias |
| contents | Exclusive nondeterministic finite automata (XNFA) are nondeterministic finite automata with a special acceptance condition. An input is accepted if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. We study the descriptional complexity of XNFA accepting unary languages. While the state costs for mutual simulations with DFA and NFA over general alphabets differ significantly from the known types of finite automata, it turns out that the state costs for the simulations in the unary case are in the order of magnitude of the general case. In particular, the state costs for the simulation of an XNFA by a DFA or an NFA are $e^{θ(\sqrt{n \cdot ln{n}})}$. Conversely, converting an NFA to an equivalent XNFA may cost $e^{θ(\sqrt{n \cdot ln{n}})}$ states as well. All bounds obtained are also tight in the order of magnitude. Finally, we investigate the computational complexity of different decision problems for unary XNFA and it is shown that the problems of emptiness, universality, inclusion, and equivalence are coNP-complete, whereas the general membership problem is NL-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06967 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of Unary Exclusive Nondeterministic Finite Automata Kutrib, Martin Malcher, Andreas Wendlandt, Matthias Formal Languages and Automata Theory Computational Complexity Exclusive nondeterministic finite automata (XNFA) are nondeterministic finite automata with a special acceptance condition. An input is accepted if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. We study the descriptional complexity of XNFA accepting unary languages. While the state costs for mutual simulations with DFA and NFA over general alphabets differ significantly from the known types of finite automata, it turns out that the state costs for the simulations in the unary case are in the order of magnitude of the general case. In particular, the state costs for the simulation of an XNFA by a DFA or an NFA are $e^{θ(\sqrt{n \cdot ln{n}})}$. Conversely, converting an NFA to an equivalent XNFA may cost $e^{θ(\sqrt{n \cdot ln{n}})}$ states as well. All bounds obtained are also tight in the order of magnitude. Finally, we investigate the computational complexity of different decision problems for unary XNFA and it is shown that the problems of emptiness, universality, inclusion, and equivalence are coNP-complete, whereas the general membership problem is NL-complete. |
| title | Complexity of Unary Exclusive Nondeterministic Finite Automata |
| topic | Formal Languages and Automata Theory Computational Complexity |
| url | https://arxiv.org/abs/2409.06967 |