Aggregation-based minimization of finite state automata
type: Item
instance of: scholarly article
title: Aggregation-based minimization of finite state automata
zbMATH Open document ID: 1490.68125
author: Johanna Björklund
author: Loek Cleophas
published in: Acta Informatica
publication date: 2021-06-23T00:00:00Z
review text: The contribution investigates bisimulation minimization for nondeterministic finite-state automata (NFA) using a partition aggregation algorithm instead of the classical partition refinement algorithms. Minimization of NFA is a well-known difficult problem that is even hard to approximate (unless \(\mathrm{P} = \mathrm{PSpace}\)). Consequently, alternative efficient algorithms that reduce the size of NFA have been investigated. Bisimulation minimization algorithms utilize bisimulations, which are equivalence relations that respect the transitions (i.e., if one of two equivalent states permits an \(a\)-transition to another state \(q\), then the equivalent state has an \(a\)-transition to a state that is equivalent to \(q\)). Additionally, the equivalence needs to respect the distinction into final and nonfinal states. The standard algorithms to compute the coarsest bisimulation of a given NFA use partition refinement in the sense that they initially split the set of states into final and nonfinal states and then split equivalence classes if the transitions are not respected. The current contribution computes the same bisimulation using a partition aggregation approach, so it starts with each state in its own equivalence class and then merges equivalence classes if that is possible. The contribution claims that the benefit of the aggregation approach, despite of being asymptotocally slower than the refinement algorithms, is that the intermediate equivalences computed on the way to the coarsest bismulation can be used to reduce the input NFA as well and will always preserve the recognized language. This is due to the fact that states that are placed in the same equivalence class in the aggregation approach are guaranteed to be bisimilar, whereas this is not the case for the refinement approach since the initial partition for the refinement approach is potentially too aggressive. The logical characterization of the equivalence classes that can be merged might lead itse…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7362509
zbMATH Keywords: nondeterministic finite-state automata
zbMATH Keywords: minimization
zbMATH Keywords: bisimulation
zbMATH Keywords: aggregation
zbMATH Keywords: bisimulation minimization
MaRDI profile type: Publication
full work available at URL: s00236-019-00363-5
OpenAlex ID: W2999586522
cites work: A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
cites work: Q4091421
cites work: Incremental DFA minimisation
cites work: Q5389971
cites work: Minimization of Finite State Automata Through Partition Aggregation
cites work: Backward and forward bisimulation minimization of tree automata
cites work: Bisimulation Minimisation of Weighted Automata on Unranked Trees
cites work: Bisimulation relations for weighted automata
cites work: Q5418253
cites work: Average complexity of Moore's and Hopcroft's algorithms
cites work: Minimizing nfa's and regular expressions
cites work: Set Merging Algorithms
cites work: Q5551191
cites work: Linear Automaton Transformations
cites work: Three Partition Refinement Algorithms
cites work: Efficiency of a Good But Not Linear Set Union Algorithm
cites work: Q4848749
Wikidata QID: Q126404744
DOI: 10.1007/S00236-019-00363-5
description: scientific article; zbMATH DE number 7362509