DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1328

Efficient Minimization of DFAs with Partial Transition

Authors: Antti Valmari and Petri Lehtinen

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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(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.

Cite as

Antti Valmari and Petri Lehtinen. Efficient Minimization of DFAs with Partial Transition. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 645-656, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{valmari_et_al:LIPIcs.STACS.2008.1328,
  author =	{Valmari, Antti and Lehtinen, Petri},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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}
}

Search Results

Documents authored by Valmari, Antti

Efficient Minimization of DFAs with Partial Transition

Abstract

Cite as

Thanks for your feedback!

Could not send message