2023/02/13 by Czerwiński, Wojciech, Dębski, Maciej, Gogasz, Tomasz +5
#03D05 #68Q15 #68Q17 #68Q45 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)
paper · doi:10.48550/arxiv.2302.06435
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 ⊆ 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 ∪ 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 log2 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)… 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