Languages given by Finite Automata over the Unary Alphabet
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910743595581440 |
|---|---|
| author | Czerwiński, Wojciech Dębski, Maciej Gogasz, Tomasz Hoi, Gordon Jain, Sanjay Skrzypczak, Michał Stephan, Frank Tan, Christopher |
| author_facet | Czerwiński, Wojciech Dębski, Maciej Gogasz, Tomasz Hoi, Gordon Jain, Sanjay Skrzypczak, Michał Stephan, Frank Tan, Christopher |
| contents | This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let $n$ denote the maximum of the number of states of the input finite automata considered in the corresponding results. The following main results are obtained:
(1) Given two unary NFAs recognising $L$ and $H$, respectively, one can decide whether $L \subseteq H$ as well as whether $L = H$ in time $2^{O((n \log n)^{1/3})}$. The previous upper bound on time was $2^{O((n \log n)^{1/2})}$ as given by Chrobak (1986), and this bound was not significantly improved since then.
(2) Given two unary UFAs (unambiguous finite automata) recognising $L$ and $H$, respectively, one can determine a UFA recognising $L \cup H$ and a UFA recognising complement of $L$, where these output UFAs have the number of states bounded by a quasipolynomial in $n$. However, in the worst case, a UFA for recognising concatenation of languages recognised by two $n$-state UFAs, uses $2^{Θ((n \log^2 n)^{1/3})}$ states.
(3) Given a unary language $L$, if $L$ contains the word of length $k$, then let $L(k)=1$ else let $L(k)=0$. Let $ω_L$ be the $ω$-word $L(0)L(1)\ldots$ and let $\cal L$ be a fixed $ω$-regular language. The last section studies how difficult it is to decide, given an $n$-state UFA or NFA |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06435 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Languages given by Finite Automata over the Unary Alphabet Czerwiński, Wojciech Dębski, Maciej Gogasz, Tomasz Hoi, Gordon Jain, Sanjay Skrzypczak, Michał Stephan, Frank Tan, Christopher Formal Languages and Automata Theory Logic 03D05, 68Q15, 68Q17, 68Q45 This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let $n$ denote the maximum of the number of states of the input finite automata considered in the corresponding results. The following main results are obtained: (1) Given two unary NFAs recognising $L$ and $H$, respectively, one can decide whether $L \subseteq H$ as well as whether $L = H$ in time $2^{O((n \log n)^{1/3})}$. The previous upper bound on time was $2^{O((n \log n)^{1/2})}$ as given by Chrobak (1986), and this bound was not significantly improved since then. (2) Given two unary UFAs (unambiguous finite automata) recognising $L$ and $H$, respectively, one can determine a UFA recognising $L \cup H$ and a UFA recognising complement of $L$, where these output UFAs have the number of states bounded by a quasipolynomial in $n$. However, in the worst case, a UFA for recognising concatenation of languages recognised by two $n$-state UFAs, uses $2^{Θ((n \log^2 n)^{1/3})}$ states. (3) Given a unary language $L$, if $L$ contains the word of length $k$, then let $L(k)=1$ else let $L(k)=0$. Let $ω_L$ be the $ω$-word $L(0)L(1)\ldots$ and let $\cal L$ be a fixed $ω$-regular language. The last section studies how difficult it is to decide, given an $n$-state UFA or NFA |
| title | Languages given by Finite Automata over the Unary Alphabet |
| topic | Formal Languages and Automata Theory Logic 03D05, 68Q15, 68Q17, 68Q45 |
| url | https://arxiv.org/abs/2302.06435 |