Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Minimization of Finite State Automata Through Partition Aggregation
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. Department of Information Science, Stellenbosch University, Stellenbosch, South Africa.
2017 (engelsk)Inngår i: Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings / [ed] Drewes, F Martin-Vide, C Truthe, B, Springer International Publishing AG , 2017, s. 223-235Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

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) vertical bar Sigma vertical bar), 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 vertical bar Sigma vertical bar 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.

sted, utgiver, år, opplag, sider
Springer International Publishing AG , 2017. s. 223-235
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10168
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-144128DOI: 10.1007/978-3-319-53733-7_16ISI: 000418579700016Scopus ID: 2-s2.0-85013436481ISBN: 978-3-319-53732-0 (tryckt)ISBN: 978-3-319-53733-7 (digital)OAI: oai:DiVA.org:umu-144128DiVA, id: diva2:1176316
Konferanse
11th International Conference on Language and Automata Theory and Applications (LATA), MAR 06-09, 2017, Umeå, SWEDEN
Tilgjengelig fra: 2018-01-22 Laget: 2018-01-22 Sist oppdatert: 2023-03-24bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Björklund, Johanna

Søk i DiVA

Av forfatter/redaktør
Björklund, Johanna
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 910 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf