2021/05/16 by Emil Indzhev, Indzhev, Emil, Stefan Kiefer +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.07470
version implementing referees' suggestions
openalex publication_date 2021/05/16 · arxiv created 2022/03/15 · arxiv updated 2022/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for any unambiguous finite automaton with n states there exists an unambiguous finite automaton with √(n+1) ⋅ 2n/2 states that recognizes the complement language. This builds and improves upon a similar result by Jirásek et al. [Int. J. Found. Comput. Sci. 29 (5) (2018)]. Our improvement is based on a reduction to and an analysis of a problem from extremal graph theory: we show that for any graph with n vertices, the product of the number of its cliques with the number of its cocliques (independent sets) is bounded by (n+1) 2n.