A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton

DOI10.4230/LIPIcs.ICALP.2018.138zbMath1499.68193arXiv1711.03993OpenAlexW2963341173MaRDI QIDQ5002825

Mikhail Raskin

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1711.03993

zbMATH Keywords

lower boundunambiguous automatalanguage complement

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

On complementing unambiguous automata and graphs with many cliques and cocliques ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ Universality Problem for Unambiguous VASS ⋮ The Containment Problem for Unambiguous Register Automata ⋮ On the relative succinctness of sentential decision diagrams ⋮ State complexity of unambiguous operations on finite automata ⋮ Image-binary automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unambiguous finite automata over a unary alphabet
• State complexity of operations on two-way finite automata over a unary alphabet
• Partial orders on words, minimal elements of regular languages, and state complexity
• Finite automata and unary languages
• Complementing unary nondeterministic automata
• Complementing two-way finite automata
• Operations on Unambiguous Finite Automata
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Unambiguity in Automata Theory
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Structurally Unambiguous Finite Automata

This page was built for publication: A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton