Myers RS, Urbat H (2021)
Publication Type: Conference contribution
Publication year: 2021
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 202
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Tallinn, EST
ISBN: 9783959772013
DOI: 10.4230/LIPIcs.MFCS.2021.78
Nondeterministic automata may be viewed as succinct programs implementing deterministic automata, i.e. complete specifications. Converting a given deterministic automaton into a small nondeterministic one is known to be computationally very hard; in fact, the ensuing decision problem is PSPACE-complete. This paper stands in stark contrast to the status quo. We restrict attention to subatomic nondeterministic automata, whose individual states accept unions of syntactic congruence classes. They are general enough to cover almost all structural results concerning nondeterministic state-minimality. We prove that converting a monoid recognizing a regular language into a small subatomic acceptor corresponds to an NP-complete problem. The NP certificates are solutions of simple equations involving relations over the syntactic monoid. We also consider the subclass of atomic nondeterministic automata introduced by Brzozowski and Tamm. Given a deterministic automaton and another one for the reversed language, computing small atomic acceptors is shown to be NP-complete with analogous certificates. Our complexity results emerge from an algebraic characterization of (sub)atomic acceptors in terms of deterministic automata with semilattice structure, combined with an equivalence of categories leading to succinct representations.
APA:
Myers, R.S., & Urbat, H. (2021). Syntactic Minimization of Nondeterministic Finite Automata. In Filippo Bonchi, Simon J. Puglisi (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Tallinn, EST: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Myers, Robert S.R., and Henning Urbat. "Syntactic Minimization of Nondeterministic Finite Automata." Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, EST Ed. Filippo Bonchi, Simon J. Puglisi, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.
BibTeX: Download