Geodesic
Arbology: Trees and pushdown automata
Kybernetika, Tome 48 (2012) no. 3, pp. 402-428 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C05, 68Q68
Keywords: trees; pushdown automata; tree pattern matching; indexing trees; arbology 
@article{KYB_2012_48_3_a4,
     author = {Melichar, Bo\v{r}ivoj and Janou\v{s}ek, Jan and Flouri, Tomas},
     title = {Arbology: {Trees} and pushdown automata},
     journal = {Kybernetika},
     pages = {402--428},
     year = {2012},
     volume = {48},
     number = {3},
     mrnumber = {2975797},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a4/}
}
TY  - JOUR
AU  - Melichar, Bořivoj
AU  - Janoušek, Jan
AU  - Flouri, Tomas
TI  - Arbology: Trees and pushdown automata
JO  - Kybernetika
PY  - 2012
SP  - 402
EP  - 428
VL  - 48
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a4/
LA  - en
ID  - KYB_2012_48_3_a4
ER  - 
%0 Journal Article
%A Melichar, Bořivoj
%A Janoušek, Jan
%A Flouri, Tomas
%T Arbology: Trees and pushdown automata
%J Kybernetika
%D 2012
%P 402-428
%V 48
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a4/
%G en
%F KYB_2012_48_3_a4
Melichar, Bořivoj; Janoušek, Jan; Flouri, Tomas. Arbology: Trees and pushdown automata. Kybernetika, Tome 48 (2012) no. 3, pp. 402-428. http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a4/

[1] Aho, A. V., Ullman, J. D.: The Theory of Parsing, Translation, and Compiling. Prentice-Hall Englewood Cliffs, N.J. 1972. | MR

[2] Alur, R., Madhusudan, P.: Visibly pushdown languages. In: STOC (L. Babai, ed.), ACM (2004), pp. 202–211. | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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

[9] Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific, New Jersey 1994. | MR | Zbl

[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

[12] Flouri, T., Janoušek, J., Melichar, B.: Subtree matching by pushdown automata. Comput. Sci. Inform. System 7 (2010), 2, 331–357. | DOI

[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

[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 | MR | Zbl

[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 | MR | Zbl

[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

[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

[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 | Zbl

[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 | MR | Zbl

[26] Smyth, B.: Computing Patterns in Strings. Addison-Wesley-Pearson Education Limited, Essex 2003.