Document Open Access Logo

Syntactic Minimization Of Nondeterministic Finite Automata

Authors Robert S. R. Myers, Henning Urbat

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.78.pdf
  • Filesize: 0.85 MB
  • 16 pages

Document Identifiers

Author Details

Robert S. R. Myers
  • London, United Kingdom
Henning Urbat
  • Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany

Funding

  • Urbat, Henning: Supported by Deutsche Forschungsgemeinschaft (DFG) under project SCHR 1118/15-1.

Cite AsGet BibTex

Robert S. R. Myers and Henning Urbat. Syntactic Minimization Of Nondeterministic Finite Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.78

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Algebraic language theory
  • Nondeterministic automata
  • NP-completeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jiří Adámek, Stefan Milius, Robert S. R. Myers, and Henning Urbat. On continuous nondeterminism and state minimality. In Bart Jacobs, Alexandra Silva, and Sam Staton, editors, Proc. 30th Conference on Mathematical Foundations of Programming Science (MFPS'14), volume 308 of Electron. Notes Theor. Comput. Sci., pages 3-23. Elsevier, 2014. Google Scholar
  2. Michael A. Arbib and Ernest G. Manes. Fuzzy machines in a category. Bulletin of the Australian Mathematical Society, 13(2):169–210, 1975. Google Scholar
  3. Alex Brodsky and Nicholas Pippenger. Characterizations of 1-way quantum finite automata. SIAM J. Comput., 31:73-91, 1999. Google Scholar
  4. Janusz Brzozowski and Hellis Tamm. Theory of átomata. Theoretical Computer Science, 539:13-27, 2014. Google Scholar
  5. Janusz A. Brzozowski. Derivatives of regular expressions. J. ACM, 11(4):481-494, 1964. Google Scholar
  6. Marek Chrobak. Finite automata and unary languages. Theoretical Computer Science, 47:149-158, 1986. Google Scholar
  7. François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. In Afonso Ferreira and Horst Reichel, editors, Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), pages 144-157. Springer, 2001. Google Scholar
  8. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  9. Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing nondeterministic finite automata with SAT solvers. In Anssi Yli-Jyrä, András Kornai, Jacques Sakarovitch, and Bruce Watson, editors, Proc. 8th International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP'09), pages 81-92. Springer, 2010. Google Scholar
  10. Hermann Gruber and Markus Holzer. Finding lower bounds for nondeterministic state complexity is hard. In Oscar H. Ibarra and Zhe Dang, editors, Proc. 10th International Conference on Developments in Language Theory (DLT'06), pages 363-374. Springer, 2006. Google Scholar
  11. Hermann Gruber and Markus Holzer. Computational complexity of NFA minimization for finite and unary languages. In Remco Loos, Szilárd Zsolt Fazekas, and Carlos Martín-Vide, editors, Proc. 1st International Conference on Language and Automata Theory and Applications (LATA'07), pages 261-272. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, 2007. Google Scholar
  12. D.A. Higgs and K.A. Rowe. Nuclearity in the category of complete semilattices. Journal of Pure and Applied Algebra, 57(1):67-78, 1989. Google Scholar
  13. Tao Jiang, Edward McDowell, and B. Ravikumar. The structure and complexity of minimal NFA’s over a unary alphabet. International Journal of Foundations of Computer Science, 02(02):163-182, 1991. Google Scholar
  14. Tao Jiang and B. Ravikumar. Minimal NFA problems are hard. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez Artalejo, editors, Proc. 18th International Colloquium on Automata, Languages, and Programming (ICALP'91), pages 629-640. Springer, 1991. Google Scholar
  15. Tao Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117-1141, 1993. Google Scholar
  16. Peter Jipsen. Categories of algebraic contexts equivalent to idempotent semirings and domain semirings. In Wolfram Kahl and Timothy G. Griffin, editors, Proc. 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS'12), pages 195-206. Springer, 2012. Google Scholar
  17. Peter T. Johnstone. Stone spaces. Cambridge University Press, 1982. Google Scholar
  18. T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617-627, 1970. Google Scholar
  19. Michel Latteux, Yves Roos, and Alain Terlutte. Minimal NFA and biRFSA languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 43(2):221-237, 2009. Google Scholar
  20. Sylvain Lombardy and Jacques Sakarovitch. The universal automaton. In Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], pages 457-504, 2008. Google Scholar
  21. Saunders Mac Lane. Categories for the working mathematician. Springer, 2 edition, 1998. Google Scholar
  22. Andreas Malcher. Minimizing finite automata is computationally hard. Theor. Comput. Sci., 327(3):375-390, 2004. Google Scholar
  23. George Markowsky. The factorization and representation of lattices. Transactions of the American Mathematical Society, 203:185-200, 1975. Google Scholar
  24. M. Andrew Moshier. A relational category of formal contexts (preprint), 2016. Google Scholar
  25. Robert S. R. Myers, Jiří Adámek, Stefan Milius, and Henning Urbat. Coalgebraic constructions of canonical nondeterministic automata. Theor. Comput. Sci., 604:81-101, 2015. Google Scholar
  26. Robert. S. R. Myers, Stefan Milius, and Henning Urbat. Nondeterministic syntactic complexity. In Stefan Kiefer and Christine Tasson, editors, Proc. 24th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'21). Springer, 2021. URL: http://arxiv.org/abs/2101.03039.
  27. Jean-Éric Pin. Mathematical foundations of automata theory. Available at http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf, September 2020.
  28. K. A. Rowe. Nuclearity. Canadian Mathematical Bulletin, 31(2):227–235, 1988. Google Scholar
  29. Hellis Tamm. New interpretation and generalization of the Kameda-Weiner method. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16), volume 55 of LIPIcs, pages 116:1-116:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  30. Hellis Tamm and Esko Ukkonen. Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science, 328(1):135-149, 2004. Google Scholar
  31. Jens Zumbrägel. Classification of finite congruence-simple semirings with zero. Journal of Algebra and Its Applications, 7, March 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact