Minimization of finite state automata through partition aggregation

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
Place of PublicationDordrecht
PublisherSpringer
Pages223-235
Number of pages13
ISBN (Electronic)978-3-319-53733-7
ISBN (Print)978-3-319-53732-0
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science
Volume10168

Fingerprint

Finite automata
Agglomeration

Cite this

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 (pp. 223-235). (Lecture Notes in Computer Science; Vol. 10168). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-53733-7_16
Björklund, J. ; Cleophas, L.G.W.A. / Minimization of finite state automata through partition aggregation. Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Dordrecht : Springer, 2017. pp. 223-235 (Lecture Notes in Computer Science).
@inproceedings{e401f671b5b743858b4271595681e4a0,
title = "Minimization of finite state automata through partition aggregation",
abstract = "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.",
author = "J. Bj{\"o}rklund and L.G.W.A. Cleophas",
year = "2017",
doi = "10.1007/978-3-319-53733-7_16",
language = "English",
isbn = "978-3-319-53732-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "223--235",
booktitle = "Language and Automata Theory and Applications",
address = "Germany",

}

Björklund, J & Cleophas, LGWA 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. Lecture Notes in Computer Science, vol. 10168, Springer, Dordrecht, pp. 223-235. https://doi.org/10.1007/978-3-319-53733-7_16

Minimization of finite state automata through partition aggregation. / Björklund, J.; Cleophas, L.G.W.A.

Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Dordrecht : Springer, 2017. p. 223-235 (Lecture Notes in Computer Science; Vol. 10168).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Minimization of finite state automata through partition aggregation

AU - Björklund, J.

AU - Cleophas, L.G.W.A.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-53733-7_16

DO - 10.1007/978-3-319-53733-7_16

M3 - Conference contribution

SN - 978-3-319-53732-0

T3 - Lecture Notes in Computer Science

SP - 223

EP - 235

BT - Language and Automata Theory and Applications

PB - Springer

CY - Dordrecht

ER -

Björklund J, Cleophas LGWA. 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. Dordrecht: Springer. 2017. p. 223-235. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-53733-7_16