2026-07-26T00:46:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19395 2024-03-06T11:03:56Z ddc:004 open_access

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 Nondeterministic Finite Automata Unambiguous Finite Automata Upper Bounds on Runtime Conditional Lower Bounds Languages over the Unary Alphabet This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary and n the number of states of the finite automata considered. The following main results are obtained: 1) Equality and inclusion of NFAs can be decided within time 2^O((n log n)^{1/3}); previous upper bound 2^O((n log n)^{1/2}) was by Chrobak (1986) via DFA conversion. 2) The state complexity of operations of UFAs (unambiguous finite automata) increases for complementation and union at most by quasipolynomial; however, for concatenation of two n-state UFAs, the worst case is an UFA of at least 2^Ω(n^{1/6}) states. Previously the upper bounds for complementation and union were exponential-type and this lower bound for concatenation is new. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Maciej Dębski and Tomasz Gogasz and Gordon Hoi and Sanjay Jain and Michał Skrzypczak and Frank Stephan and Christopher Tan 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.22 urn:nbn:de:0030-drops-193959 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.22 eng https://creativecommons.org/licenses/by/4.0/legalcode