Journal article

Publication year: 2010

Pages: 3404-3413

Journal: Theoretical Computer Science

Volume number: 411

Issue number: 38-39

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2010.05.029

Publisher: Elsevier

Abstract: 
We improve a recent result [A. Badr, Hyper-minimization in O(n(2)), Internat. J. Found. Comput. Sci. 20 (4) (2009) 735-746] for hyper-minimized finite automata. Namely, we present an O(n log n) algorithm that computes for a given deterministic finite automaton (dfa) an almost-equivalent dfa that is as small as possible such an automaton is called hyper-minimal. Here two finite automata are almost-equivalent if and only if the symmetric difference of their languages is finite. In other words, two almost-equivalent automata disagree on acceptance on finitely many inputs. In this way, we solve an open problem stated in [A. Badr, V. Geffert, I. Shipman, Hyper-minimizing minimized deterministic finite state automata, RAIRO Theor. Inf. Appl. 43 (1) (2009) 69-94] and by Badr. Moreover, we show that minimization linearly reduces to hyper-minimization, which shows that the time-bound 0(n log n) is optimal for hyper-minimization. Independently, similar results were obtained in [P. Gawrychowski, A. Jez, Hyper-minimisation made efficient, in: Proc. 34th Int. Symp. Mathematical Foundations of Computer Science, in: LNCS, vol. 5734, Springer, 2009, pp. 356-368]. (C) 2010 Elsevier B.V. All rights reserved.

Harvard Citation style: Holzer, M. and Maletti, A. (2010) An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton, Theoretical Computer Science, 411(38-39), pp. 3404-3413. https://doi.org/10.1016/j.tcs.2010.05.029

APA Citation style: Holzer, M., & Maletti, A. (2010). An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoretical Computer Science. 411(38-39), 3404-3413. https://doi.org/10.1016/j.tcs.2010.05.029