Aggregation-based minimization of finite state automata

Johanna Björklund (Corresponding author), Loek Cleophas

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Downloads (Pure)


We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O(n2r2|Σ|), where n is the number of states of the input automaton M, r is the maximal out-degree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft’s partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M, optimisation techniques from the field of model checking become applicable.
Originele taal-2Engels
Pagina's (van-tot)177-194
Aantal pagina's18
TijdschriftActa Informatica
Nummer van het tijdschrift3
StatusGepubliceerd - jun 2021


Duik in de onderzoeksthema's van 'Aggregation-based minimization of finite state automata'. Samen vormen ze een unieke vingerafdruk.

Citeer dit