×

From tree automata to string automata minimization. (English) Zbl 1400.68103

The authors associate with any given deterministic finite bottom-up tree automaton (DFTA) a deterministic finite string automaton (DFA) that can be used for minimizing the tree automaton. By this reduction the existing efficient minimization algorithms designed for string automata become applicable to tree automata. Thus, using a standard minimization method for DFAs, a DFTA can be minimized in time \(\mathcal{O}(rm + m \log n)\), where \(r\) is the maximal rank in the ranked alphabet, \(m\) is the size of the DFTA and \(n\) is the number of its states. The reduction yields also efficient methods for minimizing acyclic DFTAs, as well as for incremental minimization and incremental construction of DFTAs.

MSC:

68Q45 Formal languages and automata
68W05 Nonnumerical algorithms

Software:

OpenFst; FSA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: Rewriting Techniques and Applications (R. Nieuwenhuis, ed.), vol. 2706 of Lecture Notes in Computer Science, Springer Berlin Heidelberg (2003) · Zbl 1038.68039
[2] Chidlovskii, B.: Using regular tree automata as XML schemas. In: Proceedings IEEE advances on digital libraries conference 2000, pp 89-98 (1999)
[3] Tommasi, M.: Structures arborescentes et apprentissage automatique, p 3. PhD thesis, Université Charles de Gaulle - Lille (2006)
[4] Brainerd, WS, The minimalization of tree automata, Inf. Control., 13, 484-491, (1968) · Zbl 0181.01602 · doi:10.1016/S0019-9958(68)90917-0
[5] Arbib, MA; Give’on, Y, Algebra automata I: parallel programming as a prolegomena to the categorical approach, Inf. Control., 12, 331-345, (1968) · Zbl 0164.32201 · doi:10.1016/S0019-9958(68)90374-4
[6] Moore, E.F.: Gedanken Experiments on Sequential Machines. In: Automata Studies, pp. 129-153, Princeton U. (1956)
[7] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979) · Zbl 0426.68001
[8] Valmari, A, Fast brief practical DFA minimization, Inf. Process. Lett., 112, 213-217, (2012) · Zbl 1242.68149 · doi:10.1016/j.ipl.2011.12.004
[9] Gécseg, F; Steinby, M, Minimal ascending tree automata, Acta Cybern., 4, 37-44, (1980) · Zbl 0396.68041
[10] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications, 2007. release October 12th (2007)
[11] Watson, B.W.: Taxonomies and Toolkits of Regular Language Algorithms. PhD thesis, Faculty of Mathematics and Computer Science, Eindhoven University of Technology (1995) · Zbl 0832.68064
[12] Watson, BW; Daciuk, J, An efficient incremental DFA minimization algorithm, Nat. Lang. Eng., 9, 49-64, (2003) · doi:10.1017/S1351324903003127
[13] Cleophas, L.G., Kourie, D.G., Strauss, T., Watson, B.W.: On minimizing deterministic tree automata. In: Stringology (J. Holub and J. Zdrek, eds.), pp. 173-182, Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2009) · Zbl 1209.68298
[14] Almeida, M., Moreira, N., Reis, R.: Incremental DFA minimisation. In: CIAA (M. Domaratzki and K. Salomaa, eds.), vol. 6482 of Lecture Notes in Computer Science, pp. 39-48, Springer (2010) · Zbl 1297.68103
[15] García, P; Vázquez de Parga, M; Velasco, JA; Lȯpez, D, A split-based incremental deterministic automata minimization algorithm, Theory Comput. Syst., 57, 319-336, (2015) · Zbl 1335.68119 · doi:10.1007/s00224-014-9588-y
[16] Carrasco, RC; Daciuk, J; Forcada, ML, Incremental construction of minimal tree automata, Algorithmica, 55, 95-110, (2009) · Zbl 1180.68168 · doi:10.1007/s00453-008-9172-4
[17] Carrasco, RC; Forcada, ML, Incremental construction and maintenance of minimal finite-state automata, Comput. Linguist., 28, 207-216, (2002) · Zbl 1232.68080 · doi:10.1162/089120102760173652
[18] Carrasco, R.C., Daciuk, J., Forcada, M.L.: An implementation of deterministic tree automata minimization. In: CIAA (J. Holub and J. Zdarek, eds.), vol. 4783 of Lecture Notes in Computer Science, pp. 122-129, Springer (2007) · Zbl 1139.68357
[19] Abdulla, PA; Bouajjani, A; Holík, L; Kaati, L; Kaati, TX, Composed bisimulation for tree automata, Int. J. Found. Comput. Sci., 20, 685-700, (2009) · Zbl 1176.68098 · doi:10.1142/S0129054109006814
[20] Högberg, J; Maletti, A; May, J, Backward and forward bisimulation minimization of tree automata, Theor. Comput. Sci., 410, 3539-3552, (2009) · Zbl 1194.68139 · doi:10.1016/j.tcs.2009.03.022
[21] Riley, M., Allauzen, C., Jansche, M.: OpenFst: An open-source, weighted finite-state transducer library and its applications to speech and language. In: Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, May 31 - June 5, 2009, Boulder, Colorado, USA, Tutorial Abstracts, pp 9-10 (2009)
[22] Kanthak, S., Ney, H.: FSA: An Efficient and Flexible C++ Toolkit for Finite State Automata Using On-Demand Computation. In: Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 510-517 (2004)
[23] Watson, BW, Implementing and using finite automata toolkits, Nat. Lang. Eng., 2, 295-302, (1996) · doi:10.1017/S135132499700154X
[24] Paige, R; Tarjan, RE, Three partition refinement algorithms, SIAM J. Comput., 16, 973-989, (1987) · Zbl 0654.68072 · doi:10.1137/0216062
[25] Bousquet-Mėlou, M; Lohrey, M; Maneth, S; Nȯth, E, XML compression via directed acyclic graphs, Theory Comput. Syst., 57, 1322-1371, (2015) · Zbl 1352.68079 · doi:10.1007/s00224-014-9544-x
[26] Watson, BW, A new algorithm for the construction of minimal acyclic dfas, Sci. Comput. Program., 48, 81-97, (2003) · Zbl 1059.68071 · doi:10.1016/S0167-6423(03)00012-1
[27] Revuz, D, Minimisation of acyclic deterministic automata in linear time, Theor. Comput. Sci., 92, 181-189, (1992) · Zbl 0759.68066 · doi:10.1016/0304-3975(92)90142-3
[28] Watson, B.W.: An incremental DFA minimization algorithm. In: Finite State Methods in Natural Language Processing (2001)
[29] Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite-state automata, CoRR, vol. cs.CL/0007009 (2000) · Zbl 1232.68081
[30] Hanneforth, T., Maletti, A., Quernheim, D.: Random generation of nondeterministic finite-state tree automata. In: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19/10/2013, pp 11-16 (2013) · Zbl 1390.68394
[31] Bubenzer, J.: Minimization of Acyclic DFAs. In: Proceedings of the Prague Stringology Conference 2011, Prague, Czech Republic, August 29-31 (2011) · Zbl 1329.68157
[32] Björklund, J; Cleophas, L, A taxonomy of minimisation algorithms for deterministic tree automata, J. Universal Comput. Sci., 22, 180-196, (2016)
[33] Hėam, P-C; Nicaud, C; Schmitz, S, Parametric random generation of deterministic tree automata, Theor. Comput. Sci., 411, 3469-3480, (2010) · Zbl 1209.68298 · doi:10.1016/j.tcs.2010.05.036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.