On complementing unambiguous automata and graphs with many cliques and cocliques

DOI10.1016/j.ipl.2022.106270OpenAlexW3163870168MaRDI QIDQ2671818

Emil Indzhev, Stefan Kiefer

Publication date: 3 June 2022

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

graphsformal languagesstate complexityunambiguous automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

On the transformation of two-way finite automata to unambiguous finite automata ⋮ Image-binary automata

Cites Work

• Partial orders on words, minimal elements of regular languages, and state complexity
• State complexity of some operations on binary regular languages
• Operations on Unambiguous Finite Automata
• A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
• Unambiguity in Automata Theory

This page was built for publication: On complementing unambiguous automata and graphs with many cliques and cocliques