Minimization of finite state automata through partition aggregation

J. Björklund, L.G.W.A. Cleophas

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

We present a minimization algorithm for finite state automata that finds and merges bisimulation-equivalent states, identified through partition aggregation. We show the algorithm to be correct and run in time O(n 2 d 2 |Σ|), where n is the number of states of the input automaton M, d is the maximal outdegree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm is slower than those based on partition refinement, but has the advantage that intermediate solutions are also language equivalent to M. As a result, the algorithm can be interrupted or put on hold as needed, and the derived automaton is still useful. Furthermore, the algorithm essentially searches for the maximal model of a characteristic formula for M, so many of the optimisation techniques used to gain efficiency in SAT solvers are likely to apply.
Originele taal-2Engels
TitelLanguage and Automata Theory and Applications
Subtitel11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's223-235
Aantal pagina's13
ISBN van elektronische versie978-3-319-53733-7
ISBN van geprinte versie978-3-319-53732-0
DOI's
StatusGepubliceerd - 2017

Publicatie series

NaamLecture Notes in Computer Science
Volume10168

    Vingerafdruk

Citeer dit

Björklund, J., & Cleophas, L. G. W. A. (2017). Minimization of finite state automata through partition aggregation. In Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings (blz. 223-235). (Lecture Notes in Computer Science; Vol. 10168). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-53733-7_16