### Abstract

Original language | English |
---|---|

Title of host publication | Language and Automata Theory and Applications |

Subtitle of host publication | 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 223-235 |

Number of pages | 13 |

ISBN (Electronic) | 978-3-319-53733-7 |

ISBN (Print) | 978-3-319-53732-0 |

DOIs | |

Publication status | Published - 2017 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 10168 |

### Fingerprint

### Cite this

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -