On Minimising Automata with Errors

详细信息    查看全文

• 作者：Pawe? Gawrychowski (1) gawry@cs.uni.wroc.pl
  Artur Je? (1) aje@cs.uni.wroc.pl
  Andreas Maletti (2) andreas.maletti@ims.uni-stuttgart.de
• 关键词：finite automaton – minimisation – lossy compression
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6907
• 期：1
• 页码：327-338
• 全文大小：236.6 KB
• 参考文献：1. Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3) (2007)
  2. Badr, A., Geffert, V., Shipman, I.: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theoret. Inform. Appl. 43(1), 69–94 (2009)
  3. 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)
  4. 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)
  5. Gries, D.: Describing an algorithm by Hopcroft. Acta Inf. 2(2), 97–109 (1973)
  6. Holzer, M., Maletti, A.: An n logn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci. 411(38–39), 3404–3413 (2010)
  7. Hopcroft, J.E.: An algorithm for minimizing states in a finite automaton. In: Kohavi, Z. (ed.) Theory of Machines and Computations, pp. 189–196. Academic Press, London (1971)
  8. 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)
  9. Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)
• 作者单位：1. Institute of Computer Science, University of Wroc?aw, ul. Joliot-Curie?15, 50-383 Wroc?aw, Poland2. Institute for Natural Language Processing, Universit?t Stuttgart, Azenbergstra?e?12, 70174 Stuttgart, Germany
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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 O( | M | log2 n)\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 O( | M | logn)\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.