×

zbMATH — the first resource for mathematics

Incremental construction of minimal tree automata. (English) Zbl 1180.68168
Summary: We describe an algorithm that allows the incremental addition or removal of unranked ordered trees to a minimal frontier-to-root Deterministic finite-state Tree Automaton (DTA). The algorithm takes a tree \(t\) and a minimal DTA \(A\) as input; it outputs a minimal DTA \(A^{\prime}\) which accepts the language \(L(A)\) accepted by \(A\) incremented (or decremented) with the tree \(t\). The algorithm can be used to efficiently maintain dictionaries which store large collections of trees or tree fragments.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation and Compiling. Vol. I: Parsing. Prentice-Hall, London (1972) · Zbl 0264.68032
[2] Aoe, J., Morimoto, K., Hase, M.: An algorithm for compressing common suffixes used in tree structures. Syst. Comput. Jpn. 24(12), 31–42 (1993) (translated from Trans. IEICE J75-D-II(4), 770–779, 1992) · doi:10.1002/scj.4690240703
[3] Bod, R.: A computational model of language performance: Data oriented parsing. In: Proceedings of the 14th Conference on Computational Linguistics, pp. 855–859. Association for Computational Linguistics, Morristown (1992)
[4] Brainerd, W.S.: The minimalization of tree automata. Inf. Control 13(5), 484–491 (1968) · Zbl 0181.01602 · doi:10.1016/S0019-9958(68)90917-0
[5] Carrasco, R.C., Daciuk, J., Forcada, M.L.: An implementation of deterministic tree automata minimization. In: Holub., J., Zdárek, J. (eds.) CIAA2007, 12th International Conference on Implementation and Application of Automata Proceedings. Lecture Notes in Computer Science, vol. 4783, pp. 122–129. Springer, New York (2007) · Zbl 1139.68357
[6] Carrasco, R.C., Forcada, M.L.: Incremental construction and maintenance of minimal finite-state automata. Comput. Linguistics 28(2), 207–216 (2002) · Zbl 1232.68080 · doi:10.1162/089120102760173652
[7] Ciura, M., Deorowicz, S.: How to squeeze a lexicon. Softw. Pract. Experience 31(11), 1077–1090 (2001) · Zbl 0987.68782 · doi:10.1002/spe.402
[8] Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata (1997), release 1 October 2002
[9] Daciuk, J.: Comments on incremental construction and maintenance of minimal finite-state automata by R.C. Carrasco and M.L. Forcada. Comput. Linguistics 30(2), 227–235 (2004) · Zbl 1234.68207 · doi:10.1162/089120104323093302
[10] Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite-state automata. Comput. Linguistics 26(1), 3–16 (2000) · Zbl 1232.68081 · doi:10.1162/089120100561601
[11] Daciuk, J., van Noord, G.: Finite automata for compact representation of language models in NLP. In: Implementation and Application of Automata, 6th International Conference, CIAA 2001. Lecture Notes in Computer Science, vol. 2494, pp. 65–73. Springer, New York (2002) · Zbl 1015.68553
[12] de la Briandais, R.: File searching using variable length keys. In: Proceedings of the Western Joint Computer Conference, pp. 295–298 (1959)
[13] Fredkin, E.: Tree memory. Commun. ACM 3(9), 490–499 (1960) · doi:10.1145/367390.367400
[14] Garrido-Alenda, A., Forcada, M.L., Carrasco, R.C.: Incremental construction and maintenance of morphological analysers based on augmented letter transducers. In: Proceedings of TMI 2002, Theoretical and Methodological Issues in Machine Translation, Keihanna/Kyoto, Japan, March 2002, pp. 53–62 (2002)
[15] Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984) · Zbl 0537.68056
[16] Hopcroft, J., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979) · Zbl 0426.68001
[17] Lucchesi, C.L., Kowaltowski, T.: Applications of finite automata representing large vocabularies. Softw. Pract. Experience 23(1), 15–30 (1993) · doi:10.1002/spe.4380230103
[18] Revuz, D.: Dynamic acyclic minimal automaton. In: Yu, S., Paun, A. (eds.) CIAA 2000, Fifth International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science, vol. 2088, pp. 226–232. Springer, New York (2000)
[19] Sgarbas, K., Fakotakis, N., Kokkinakis, G.: Two algorithms for incremental construction of directed acyclic word graphs. Int. J. Artif. Intell. Tools 4(3), 369–381 (1995) · doi:10.1142/S0218213095000188
[20] Watson, B.W., Daciuk, J.: An efficient incremental DFA minimization algorithm. Nat. Lang. Eng. 9(1), 49–64 (2003) · doi:10.1017/S1351324903003127
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.