Arbology: Trees and pushdown automata

Bořivoj Melichar; Jan Janoušek; Tomas Flouri

Kybernetika (2012)

  • Volume: 48, Issue: 3, page 402-428
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Melichar, Bořivoj, Janoušek, Jan, and Flouri, Tomas. "Arbology: Trees and pushdown automata." Kybernetika 48.3 (2012): 402-428. <http://eudml.org/doc/246452>.

@article{Melichar2012,
abstract = {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.},
author = {Melichar, Bořivoj, Janoušek, Jan, Flouri, Tomas},
journal = {Kybernetika},
keywords = {trees; pushdown automata; tree pattern matching; indexing trees; arbology; pushdown automata; trees; tree pattern matching; indexing trees; arbology; stringology},
language = {eng},
number = {3},
pages = {402-428},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Arbology: Trees and pushdown automata},
url = {http://eudml.org/doc/246452},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Melichar, Bořivoj
AU - Janoušek, Jan
AU - Flouri, Tomas
TI - Arbology: Trees and pushdown automata
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 3
SP - 402
EP - 428
AB - 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.
LA - eng
KW - trees; pushdown automata; tree pattern matching; indexing trees; arbology; pushdown automata; trees; tree pattern matching; indexing trees; arbology; stringology
UR - http://eudml.org/doc/246452
ER -

References

top
  1. Aho, A. V., Ullman, J. D., The Theory of Parsing, Translation, and Compiling, Prentice-Hall Englewood Cliffs, N.J. 1972. MR0408321
  2. Alur, R., Madhusudan, P., Visibly pushdown languages, In: STOC (L. Babai, ed.), ACM (2004), pp. 202–211. Zbl1085.68079MR2121602
  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., 10.1016/0304-3975(85)90157-4, Theoret. Comput. Sci. 40 (1985), 31–55. Zbl0574.68070MR0828515DOI10.1016/0304-3975(85)90157-4
  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., 10.1016/0304-3975(86)90041-1, Theoret. Comput. Sci. 45 (1986), 1, 63–86. Zbl0615.68053MR0865967DOI10.1016/0304-3975(86)90041-1
  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. MR1470014
  9. Crochemore, M., Rytter, W., Jewels of Stringology, World Scientific, New Jersey 1994. Zbl1078.68151MR2012571
  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. MR2862920
  12. Flouri, T., Janoušek, J., Melichar, B., 10.2298/CSIS1002331F, Comput. Sci. Inform. System 7 (2010), 2, 331–357. DOI10.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. MR1470018
  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., 10.1145/322290.322295, J. Assoc. Comput. Mach. 29 (1982), 1, 68–95. Zbl0477.68067MR0662611DOI10.1145/322290.322295
  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., 10.1007/s00236-009-0104-9, Acta Inform. 46 (2009), 7, 533–547. Zbl1186.68260MR2551918DOI10.1007/s00236-009-0104-9
  21. Madhavan, M., Shankar, P., Rai, S., Ramakrishna, U., 10.1145/371880.371881, ACM Trans. Program. Lang. Syst. 22 (2000), 6, 973–1001. DOI10.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. MR2753896
  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. Zbl1147.68562MR2539420
  25. Shankar, P., Gantait, A., Yuvaraj, A. R., Madhavan, M., 10.1016/S0304-3975(98)00205-9, Theor. Comput. Sci. 242 (2000), 1–2, 125–142. Zbl0944.68096MR1769140DOI10.1016/S0304-3975(98)00205-9
  26. Smyth, B., Computing Patterns in Strings, Addison-Wesley-Pearson Education Limited, Essex 2003. 

NotesEmbed ?

top

You must be logged in to post comments.