Efficient Minimization of DFAs with Partial Transition FunctionsReportar como inadecuado

Efficient Minimization of DFAs with Partial Transition Functions - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Institute of Software Systems

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 $Om \lg n$ time and $Om+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.

Mots-clés : deterministic finite automaton sparse adjacency matrix partition refinement

Autor: Antti Valmari - Petri Lehtinen -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados