Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1328
URN: urn:nbn:de:0030-drops-13286
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1328/
Valmari, Antti ; Lehtinen, Petri
Efficient Minimization of DFAs with Partial Transition
| pdf-format: |
|
Abstract
Let PT-DFA mean a deterministic finite automaton whose transitionrelation is a partial function. We present an algorithm for
minimizing a PT-DFA in $O(m lg n)$ 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(alpha n lg n)$ time,
$O(alpha n)$ memory algorithm.
BibTeX - Entry
@InProceedings{valmari_et_al:LIPIcs:2008:1328,
author = {Antti Valmari and Petri Lehtinen},
title = {{Efficient Minimization of DFAs with Partial Transition}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {645--656},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-06-4},
ISSN = {1868-8969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1328},
URN = {urn:nbn:de:0030-drops-13286},
doi = {10.4230/LIPIcs.STACS.2008.1328},
annote = {Keywords: Deterministic finite automaton, sparse adjacency matrix, partition refinement}
}
| Keywords: | Deterministic finite automaton, sparse adjacency matrix, partition refinement | |
| Seminar: | 25th International Symposium on Theoretical Aspects of Computer Science | |
| Issue date: | 2008 | |
| Date of publication: | 06.02.2008 |
