Kybernetika 48 no. 3, 402-428, 2012

Arbology: Trees and pushdown automata

Bořivoj Melichar, Jan Janoušek and Tomas Flouri

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.

Keywords:

pushdown automata, trees, tree pattern matching, indexing trees, arbology

Classification:

05C05, 68Q68

paper.pdf

References:

  1. A. V. Aho and J. D. Ullman: The Theory of Parsing, Translation, and Compiling. Prentice-Hall Englewood Cliffs, N.J. 1972.   CrossRef
  2. R. Alur and P. Madhusudan: Visibly pushdown languages. In: STOC (L. Babai, ed.), ACM (2004), pp. 202-211.   CrossRef
  3. : Arbology www pages. Available on: \url{http://www.arbology.org/} (2012).   CrossRef
  4. A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen and J. I. Seiferas: The smallest automaton recognizing the subwords of a text. Theoret. Comput. Sci. 40 (1985), 31-55.   CrossRef
  5. L. Cleophas: Tree Algorithms. Two Taxonomies and a Toolkit. Ph.D. Thesis, Technische Universiteit Eindhoven 2008.   CrossRef
  6. H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: Tree automata techniques and applications. Available on: \url{http://www.grappa.univ-lille3.fr/tata} (2007).   CrossRef
  7. M. Crochemore: Transducers and repetitions. Theoret. Comput. Sci. 45 (1986), 1, 63-86.   CrossRef
  8. M. Crochemore and C. Hancart: 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.   CrossRef
  9. M. Crochemore and W. Rytter: Jewels of Stringology. World Scientific, New Jersey 1994.   CrossRef
  10. J. Engelfriet: Tree Automata and Tree Grammars. University of Aarhus 1975.   CrossRef
  11. T. Flouri, C. Iliopoulos, J. Janoušek, B. Melichar and S. Pissis: Tree template matching in ranked, ordered trees by pushdown automata. To appear at CIAA 2011.   CrossRef
  12. T. Flouri, J. Janoušek and B. Melichar: Subtree matching by pushdown automata. Comput. Sci. Inform. System 7 (2010), 2, 331-357.   CrossRef
  13. F. Gecseg and M. Steinby: 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.   CrossRef
  14. R. S. Glanville and S. L. Graham: A new method for compiler code generation. In: POPL 1978, pp. 231-240.   CrossRef
  15. C. M. Hoffmann and M. J. O'Donnell: Pattern matching in trees. J. Assoc. Comput. Mach. 29 (1982), 1, 68-95.   CrossRef
  16. J. E. Hopcroft, R. Motwani and J. D. Ullman: Introduction to Automata Theory, Languages, and Computation. Second edition. Addison-Wesley, Boston 2001.   CrossRef
  17. J. Janou{š}ek: 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: \url{http://www.stringology.org/event/2009}.   CrossRef
  18. J. Janou{š}ek: Arbology: Algorithms on Trees and Pushdown Automata. Habilitation Thesis, TU FIT, Brno 2010.   CrossRef
  19. J. Janou{š}ek: Introduction to arbology. An invited talk at AAMP WIII conference, Prague 2011.   CrossRef
  20. J. Janoušek and B. Melichar: On regular tree languages and deterministic pushdown automata. Acta Inform. 46 (2009), 7, 533-547.   CrossRef
  21. M. Madhavan, P. Shankar, S. Rai and U. Ramakrishna: Extending graham-glanville techniques for optimal code generation. ACM Trans. Program. Lang. Syst. 22 (2000), 6, 973-1001.   CrossRef
  22. B. Melichar: 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.   CrossRef
  23. B. Melichar, J. Holub and J. Polcar: Text searching algorithms. Available on: \url{http://stringology.org/athens/} (2005).   CrossRef
  24. D. Nowotka and J. Srba: Height-deterministic pushdown automata. In: MFCS 2007 (L. Kucera and A. Kucera, eds.), Lecture Notes in Comput. Sci. 4708 (2007), pp. 125-134.   CrossRef
  25. P. Shankar, A. Gantait, A. R. Yuvaraj and M. Madhavan: A new algorithm for linear regular tree pattern matching. Theor. Comput. Sci. 242 (2000), 1-2, 125-142.   CrossRef
  26. B. Smyth: Computing Patterns in Strings. Addison-Wesley-Pearson Education Limited, Essex 2003.   CrossRef