Efficient Minimization of DFAs with Partial Transition Functions
| dc.creator | Valmari, Antti | |
| dc.creator | Lehtinen, Petri | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:21:59Z | |
| dc.date.available | 2026-07-07T09:21:59Z | |
| dc.description | 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(m \lg n)$ time and $O(m+n+α)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $α$ is the size of the alphabet. Time consumption does not depend on $α$, because the $α$ 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(αn \lg n)$ time, $O(αn)$ memory algorithm. | |
| dc.identifier | https://arxiv.org/abs/0802.2826 | |
| dc.identifier | http://arxiv.org/abs/0802.2826 | |
| dc.identifier | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155219 | |
| dc.subject | Information Theory | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Efficient Minimization of DFAs with Partial Transition Functions | |
| dc.type | text |