Efficient minimization of DFAs with partial transition

DOI10.4230/LIPICS.STACS.2008.1328MaRDI QIDQ4910757zbMATH OpenOpenAlexFDO

Authors Antti Valmari, Petri Lehtinen

Publication date 19 March 2013

Full work available at URL https://arxiv.org/abs/0802.2826, http://subs.emis.de/LIPIcs/frontdoor_2f7e.html

zbMATH Keywords

deterministic finite automatonpartition refinementsparse adjacency matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Analysis of algorithms (68W40)

Abstract: Let PT-DFA mean a deterministic finite automaton whose transition relation is a partial function. We present an algorithm for minimizing a PT-DFA in $O(mlgn)$ time and $O(m+n+alpha)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $alpha$ is the size of the alphabet. Time consumption does not depend on $alpha$, because the $alpha$ term arises from an array that is accessed at random and never initialized. It is not needed, if transitions are in a suitable order in the input. The algorithm uses two instances of an array-based data structure for maintaining a refinable partition. Its operations are all amortized constant time. One instance represents the classical blocks and the other a partition of transitions. Our measurements demonstrate the speed advantage of our algorithm on PT-DFAs over an $O(alphanlgn)$ time, $O(alphan)$ memory algorithm.

Recommendations

• Fast brief practical DFA minimization
• scientific article; zbMATH DE number 6300100
• Incremental DFA minimisation
• Incremental DFA minimisation
• OPTIMAL HYPER-MINIMIZATION

Cited in

(15)

• Average case analysis of Moore's state minimization algorithm
• Hyper-minimisation Made Efficient
• scientific article; zbMATH DE number 3883638 (Why is no real title available?)
• Weak Minimization of DFA — An Algorithm and Applications
• Bisimilarity Minimization in O(m logn) Time
• Fast brief practical DFA minimization
• Finding All Minimum-Size DFA Consistent with Given Examples: SAT-Based Approach
• Morphisms and Minimisation of Weighted Automata
• Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence
• An O(m n) algorithm for branching bisimilarity on labelled transition systems
• An O(m n) algorithm for computing stuttering equivalence and branching bisimulation
• DFA with a Bounded Activity Level
• Efficient algorithms for the inference of minimum size DFAs
• On complementation of nondeterministic finite automata without full determinization
• Average complexity of Moore's and Hopcroft's algorithms

This page was built for publication: Efficient minimization of DFAs with partial transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910757)