Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
trees; pushdown automata; tree pattern matching; indexing trees; arbology
trees; pushdown automata; tree pattern matching; indexing trees; arbology
Summary:
We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata reading such linear notations of trees as its basic model of computation. Basic principles known from stringology are used for the construction of particular arbology algorithms, in which the underlying tree structure is processed with the use of the pushdown store. Arbology results are shown for the basic problems subtree matching and tree indexing for ranked and unranked ordered trees.
References:
[1] Aho, A. V., Ullman, J. D.: The Theory of Parsing, Translation, and Compiling. Prentice-Hall Englewood Cliffs, N.J. 1972. MR 0408321
[2] Alur, R., Madhusudan, P.: Visibly pushdown languages. In: STOC (L. Babai, ed.), ACM (2004), pp. 202–211. MR 2121602 | Zbl 1085.68079
[3]
Arbology www pages. Available on: http://www.arbology.org/ (2012).
[4] Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M. T., Seiferas, J. I.: The smallest automaton recognizing the subwords of a text. Theoret. Comput. Sci. 40 (1985), 31–55. DOI 10.1016/0304-3975(85)90157-4 | MR 0828515 | Zbl 0574.68070
[5] Cleophas, L.: Tree Algorithms. Two Taxonomies and a Toolkit. Ph.D. Thesis, Technische Universiteit Eindhoven 2008.
[6] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata (2007).
[7] Crochemore, M.: Transducers and repetitions. Theoret. Comput. Sci. 45 (1986), 1, 63–86. DOI 10.1016/0304-3975(86)90041-1 | MR 0865967 | Zbl 0615.68053
[8] Crochemore, M., Hancart, C.: Automata for matching patterns. In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Vol. 2 Linear Modeling: Background and Application, Chap. 9, pp. 399–462. Springer-Verlag, Berlin 1997. MR 1470014
[9] Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific, New Jersey 1994. MR 2012571 | Zbl 1078.68151
[10] Engelfriet, J.: Tree Automata and Tree Grammars. University of Aarhus 1975.
[11] Flouri, T., Iliopoulos, C., Janoušek, J., Melichar, B., Pissis, S.: Tree template matching in ranked, ordered trees by pushdown automata. To appear at CIAA 2011. MR 2862920
[12] Flouri, T., Janoušek, J., Melichar, B.: Subtree matching by pushdown automata. Comput. Sci. Inform. System 7 (2010), 2, 331–357. DOI 10.2298/CSIS1002331F
[13] Gecseg, F., Steinby, M.: Tree languages. In: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), Vol. 3 Beyond Words. Handbook of Formal Languages, pp. 1–68. Springer-Verlag, Berlin 1997. MR 1470018
[14] Glanville, R. S., Graham, S. L.: A new method for compiler code generation. In: POPL 1978, pp. 231–240.
[15] Hoffmann, C. M., O'Donnell, M. J.: Pattern matching in trees. J. Assoc. Comput. Mach. 29 (1982), 1, 68–95. DOI 10.1145/322290.322295 | MR 0662611 | Zbl 0477.68067
[16] Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Second edition. Addison-Wesley, Boston 2001.
[17] Janoušek, J.: String suffix automata and subtree pushdown automata. In: Proc. Prague Stringology Conference 2009 (J. Holub and J. Žďárek, eds.), Czech Technical University in Prague 2009, pp. 160–172. Available on: http://www.stringology.org/event/2009
[18] Janoušek, J.: Arbology: Algorithms on Trees and Pushdown Automata. Habilitation Thesis, TU FIT, Brno 2010.
[19] Janoušek, J.: Introduction to arbology. An invited talk at AAMP WIII conference, Prague 2011.
[20] Janoušek, J., Melichar, B.: On regular tree languages and deterministic pushdown automata. Acta Inform. 46 (2009), 7, 533–547. DOI 10.1007/s00236-009-0104-9 | MR 2551918 | Zbl 1186.68260
[21] Madhavan, M., Shankar, P., Rai, S., Ramakrishna, U.: Extending graham-glanville techniques for optimal code generation. ACM Trans. Program. Lang. Syst. 22 (2000), 6, 973–1001. DOI 10.1145/371880.371881
[22] Melichar, B.: Arbology: Trees and pushdown automata. In: LATA 2010 (A. H. Dediu, H. Fernau, and C. Martín-Vide, eds.), Lecture Notes in Comput. Sci. 6031 (2010), pp. 32–49. Invited paper. MR 2753896
[23] Melichar, B., Holub, J., Polcar, J.: Text searching algorithms. Available on: http://stringology.org/athens/ (2005).
[24] Nowotka, D., Srba, J.: Height-deterministic pushdown automata. In: MFCS 2007 (L. Kucera and A. Kucera, eds.), Lecture Notes in Comput. Sci. 4708 (2007), pp. 125–134. MR 2539420 | Zbl 1147.68562
[25] Shankar, P., Gantait, A., Yuvaraj, A. R., Madhavan, M.: A new algorithm for linear regular tree pattern matching. Theor. Comput. Sci. 242 (2000), 1–2, 125–142. DOI 10.1016/S0304-3975(98)00205-9 | MR 1769140 | Zbl 0944.68096
[26] Smyth, B.: Computing Patterns in Strings. Addison-Wesley-Pearson Education Limited, Essex 2003.
Search
Partner of
