A Congruence-based Perspective on Automata Minimization Algorithms

2019/06/14 by Ganty, Pierre, Gutiérrez, Elena, Valero, Pedro
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1906.06194

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.

Related

• Minimization of Automata
• Minimisation of Deterministic Parity and Buchi Automata and Relative\n Minimisation of Deterministic Finite Automata
• Incremental construction of minimal acyclic finite-state automata
• Minimal Nondeterministic Finite Automata and Atoms of Regular Languages
• Syntactic Minimization of Nondeterministic Finite Automata