2026-07-20T07:31:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9142 2024-03-06T10:43:28Z ddc:004 open_access

A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton Raskin, Mikhail unambiguous automata language complement lower bound Unambiguous non-deterministic finite automata (UFA) are non-deterministic automata (over finite words) such that there is at most one accepting run over each input. Such automata are known to be potentially exponentially more succinct than deterministic automata, and non-deterministic automata can be exponentially more succinct than them. In this paper we establish a superpolynomial lower bound for the state complexity of the translation of an UFA to a non-deterministic automaton for the complement language. This disproves the formerly conjectured polynomial upper bound for this translation. This lower bound only involves a one letter alphabet, and makes use of the random graph methods. The same proof also shows that the translation of sweeping automata to non-deterministic automata is superpolynomial. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikhail Raskin 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.138 urn:nbn:de:0030-drops-91428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.138 eng https://creativecommons.org/licenses/by/3.0/legalcode