Document Open Access Logo

A Congruence-based Perspective on Automata Minimization Algorithms

Authors Pierre Ganty , Elena Gutiérrez , Pedro Valero

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.77.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Pierre Ganty
  • IMDEA Software Institute, Madrid, Spain
Elena Gutiérrez
  • IMDEA Software Institute, Madrid, Spain, Universidad Politécnica de Madrid, Spain
Pedro Valero
  • IMDEA Software Institute, Madrid, Spain, Universidad Politécnica de Madrid, Spain

Funding

  • Ganty, Pierre: Supported by the Spanish Ministry of Economy and Competitiveness project No. PGC2018-102210-B-I00, BOSCO - Foundations for the development, analysis and understanding of BlOck chains and Smart COntracts, by the Madrid Regional Government project No. S2018/TCS-4339, BLOQUES - Contratos inteligentes y Blockchains Escalables y Seguros mediante Verificación y Análisis, and by a Ramón y Cajal fellowship RYC-2016-20281.
  • Gutiérrez, Elena: Supported by BES-2016-077136 grant from the Spanish Ministry of Economy, Industry and Competitiveness.

Cite AsGet BibTex

Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Congruence-based Perspective on Automata Minimization Algorithms. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.77

Abstract

In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Regular languages
Keywords
  • Double-Reversal Method
  • Minimization
  • Automata
  • Congruences
  • Regular Languages

Metrics

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

Related Versions

References

  1. Jirí Adámek, Filippo Bonchi, Mathias Hülsbusch, Barbara König, Stefan Milius, and Alexandra Silva. A Coalgebraic Perspective on Minimization and Determinization. In FoSSaCS, volume 7213 of Lecture Notes in Computer Science, pages 58-73. Springer, 2012. Google Scholar
  2. Jean Berstel, Luc Boasson, Olivier Carton, and Isabelle Fagnot. Minimization of automata, 2010. URL: http://arxiv.org/abs/1010.5318.
  3. Filippo Bonchi, Marcello M. Bonsangue, Helle Hvid Hansen, Prakash Panangaden, Jan J. M. M. Rutten, and Alexandra Silva. Algebra-coalgebra duality in Brzozowski’s minimization algorithm. ACM Trans. Comput. Log., 15(1):3:1-3:29, 2014. Google Scholar
  4. Janusz A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, 12(6):529-561, 1962. Google Scholar
  5. Janusz A. Brzozowski and Hellis Tamm. Theory of átomata. Theor. Comput. Sci., 539:13-27, 2014. Google Scholar
  6. Julius R. Büchi. Finite Automata, their Algebras and Grammars - Towards a Theory of Formal Expressions. Springer, 1989. Google Scholar
  7. Jean-Marc Champarnaud, Ahmed Khorsi, and Thomas Paranthoën. Split and join for minimizing: Brzozowski’s algorithm. In Stringology, pages 96-104. Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University, 2002. Google Scholar
  8. Aldo de Luca and Stefano Varricchio. Finiteness and Regularity in Semigroups and Formal Languages. Springer Publishing Company, Incorporated, 1st edition, 2011. Google Scholar
  9. Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Congruence-based Perspective on Automata Minimization Algorithms (extended version), 2019. URL: http://arxiv.org/abs/1906.06194.
  10. John E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations, pages 189-196. Elsevier, 1971. Google Scholar
  11. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation - (2. ed.). Addison-Wesley-Longman, 2001. Google Scholar
  12. Szabolcs Iván. Complexity of atoms, combinatorially. Inf. Process. Lett., 116(5):356-360, 2016. Google Scholar
  13. Bakhadyr Khoussainov and Anil Nerode. Automata Theory and Its Applications. Birkhauser Boston, Inc., Secaucus, NJ, USA, 2001. Google Scholar
  14. Edward F. Moore. Gedanken-experiments on sequential machines. Automata studies, 23(1):60–60, 1956. Google Scholar
  15. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  16. Manuel Vázquez de Parga, Pedro García, and Damián López. A polynomial double reversal minimization algorithm for deterministic finite automata. Theor. Comput. Sci., 487:17-22, 2013. 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