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
    EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
    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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume10168 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Fingerprint Dive into the research topics of 'Minimization of finite state automata through partition aggregation'. Together they form a unique fingerprint.

    Cite this