Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Aggregation-based minimization of finite state automata
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0001-8503-0118
2020 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525Article in journal (Refereed) Epub ahead of print
Abstract [en]

We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O(n2r2|Σ|), where n is the number of states of the input automaton M, r is the maximal out-degree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft’s partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M, optimisation techniques from the field of model checking become applicable.

Place, publisher, year, edition, pages
Springer Nature, 2020.
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-170707DOI: 10.1007/s00236-019-00363-5Scopus ID: 2-s2.0-85077537325OAI: oai:DiVA.org:umu-170707DiVA, id: diva2:1429991
Available from: 2020-05-13 Created: 2020-05-13 Last updated: 2020-05-13

Open Access in DiVA

fulltext(1027 kB)8 downloads
File information
File name FULLTEXT01.pdfFile size 1027 kBChecksum SHA-512
c79c4f045de334c39ace3d683261a231d0b6546a004b3268e096f6c3c74f347f96f936d282b0d8de577a3fb625aea152c88e7a8a9b9136e2208abb61a9829efd
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Björklund, Johanna
By organisation
Department of Computing Science
In the same journal
Acta Informatica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 25 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf