Abstract
The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M | of a DFA M is the size of the domain of the transition function) such that L(M) ΔL(N) ⊆ Σ< k, which means that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time \(\mathcal{O}(\mid M \mid{\rm log}^{2} n)\) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \(\mathcal{O}(\mid M \mid\log n)\) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N with |L(M) ΔL(N) ≤ m. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that |L(M) ΔL(N) ≤ m.
This work was partially done when A. Maletti was visiting Wrocław University thanks to the support of the “Visiting Professors” programme of the Municipality of Wrocław.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3) (2007)
Badr, A., Geffert, V., Shipman, I.: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theoret. Inform. Appl. 43(1), 69–94 (2009)
Castiglione, G., Restivo, A., Sciortino, M.: Hopcroft’s algorithm and cyclic automata. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 172–183. Springer, Heidelberg (2008)
Gawrychowski, P., Jeż, A.: Hyper-minimisation made efficient. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 356–368. Springer, Heidelberg (2009)
Gries, D.: Describing an algorithm by Hopcroft. Acta Inf. 2(2), 97–109 (1973)
Holzer, M., Maletti, A.: An n logn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci. 411(38–39), 3404–3413 (2010)
Hopcroft, J.E.: An \(n\,\textrm{log}\, n\) algorithm for minimizing states in a finite automaton. In: Kohavi, Z. (ed.) Theory of Machines and Computations, pp. 189–196. Academic Press, London (1971)
Maletti, A.: Better hyper-minimization— not as fast, but fewer errors. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 201–210. Springer, Heidelberg (2011)
Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Gawrychowski, P., Jeż, A., Maletti, A. (2011). On Minimising Automata with Errors. In: Murlak, F., Sankowski, P. (eds) Mathematical Foundations of Computer Science 2011. MFCS 2011. Lecture Notes in Computer Science, vol 6907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22993-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-22993-0_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22992-3
Online ISBN: 978-3-642-22993-0
eBook Packages: Computer ScienceComputer Science (R0)