Kybernetika 54 no. 2, 221-242, 2018

Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas and Djelloul ZiadiDOI: 10.14736/kyb-2018-2-0221

Abstract:

In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern $E$, which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree $t$. The pattern matching algorithm requires an $\mathcal{O}(\vert t\vert\vert E\vert)$ time complexity, where $\vert t\vert$ is the number of nodes of $t$ and $\vert E\vert$ is the size of the regular tree expression $E$. The novelty of this contribution besides the low time complexity is that the set of patterns can be infinite, since we use regular tree expressions to represent patterns.

Keywords:

tree pattern matching, tree automata, Thompson Tree automata, regular tree expressions

Classification:

68Q45

References:

  1. T. A. Assaleh and W. Ai: Survey of Global Regular Expression Print (GREP) Tools. 2004.   http://www.cosc.brocku.ca/{\texttildelow}taa/papers/abou-assaleh_csci6306a.pdf
  2. A. V. Aho and M. Ganapathi: Efficient tree pattern matching (extended abstract): An aid to code generation. In: Proc. 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1985, pp. 334-340.   CrossRef
  3. V. M. Antimirov: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155 (1996), 291-319.   DOI:10.1016/0304-3975(95)00182-4
  4. L. Barry: Derivatives of tree sets with applications to grammatical inference. IEEE Trans. Pattern Analysis and Machine Intelligence, IEEE Computer Soc. 3 (1981), 285-293.   DOI:10.1109/tpami.1981.4767101
  5. L. Barry: The use of tree derivatives and a sample support parameter for inferring tree systems. IEEE Trans. Pattern Analysis and Machine Intelligence, IEEE Computer Soc. 4 (1982), 25-34.   DOI:10.1109/tpami.1982.4767191
  6. J. A. Brzozowski: Derivatives of regular expressions. J. ACM 11 (1964), 481-494.   DOI:10.1145/321239.321249
  7. J.-M. Champarnaud and D. Ziadi: From C-continuations to new quadratic algorithms for automaton synthesis. IJAC 11 (2001), 707-736.   DOI:10.1142/s0218196701000772
  8. J.-M. Champarnaud and D. Ziadi: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289 (2002), 137-163.   DOI:10.1016/s0304-3975(01)00267-5
  9. L. Cleophas: Tree Algorithms: Two Taxonomies and a Toolkit. PhD Thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 2008.   CrossRef
  10. H. Comon, M. Dauchet, R. Gilleron, C. Loding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: Tree Automata Techniques and Applications.    CrossRef
  11. J.-F. Dufayard, L. Duret, S. Penel, M. Gouy, F. Rechenmann and G. Perrière: Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases. Bioinformatics, Oxford Univ Press, 21 (2005), 2596-2603.   DOI:10.1093/bioinformatics/bti325
  12. T. Flouri, C. S. Iliopoulos, J. Janoušek, B. Melichar and S. P. Pissis: Tree template matching in ranked ordered trees by pushdown automata. J. Discrete Algorithms 17 (2012), 15-23.   DOI:10.1016/j.jda.2012.10.003
  13. Ch. W. Fraser, R. R. Henry and T. A. Proebsting: BURG: Fast optimal instruction selection and tree parsing. SIGPLAN Not, ACM 27 (1992), 68-76.   DOI:10.1145/131080.131089
  14. T. Genet and F. Klay: Rewriting for cryptographic protocol verification. In: Proc. 17th International Conference on Automated Deduction, CADE-17, Springer-Verlag, London 2000, pp. 271-290.   DOI:10.1007/10721959_21
  15. R. Giegerich: A Declarative Approach to the Development of Dynamic Programming Algorithms, Applied to RNA Folding. Report, 1998.   CrossRef
  16. V. M. Glushkov: The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53.   DOI:10.1070/rm1961v016n05abeh004112
  17. E. Goebelbecker: Using grep: Moving from DOS? Discover the power of this Linux utility. Linux Journal, Belltown Media 18 (1995).   CrossRef
  18. J. Goubault-Larrecq: A Method for Automatic Cryptographic Protocol Verification. In: Parallel and Distributed Processing, Springer 2000, pp. 977-984.   DOI:10.1007/3-540-45591-4_134
  19. A. Gräf: Left-to-right Tree Pattern Matching. In: Rewriting Techniques and Applications, Springer 1991, pp. 323-334.   DOI:10.1007/3-540-53904-2_107
  20. Ch. M. Hoffmann and M. J. O'Donnell: Pattern matching in trees. J. ACM 29 (1982), 68-95.   DOI:10.1145/322290.322295
  21. Y. Itokawa, M. Wada, T. Ishii and T. Uchida: Pattern Matching Algorithm Using a Succinct Data Structure for Tree-Structured Patterns. In: Intelligent Control and Innovative Computing, Lecture Notes in Electrical Engineering, Springer US 2012, pp. 349-361.   DOI:10.1007/978-1-4614-1695-1_27
  22. H. H. Kron: Tree Templates and Subtree Transformational Grammars. PhD Thesis, University of California, Santa Cruz 1975.   CrossRef
  23. D. Kuske and I. Meinecke: Construction of tree automata from regular expressions. RAIRO - Theor. Inf. and Appl. 45 (2011), 347-370.   DOI:10.1051/ita/2011107
  24. É. Laugerotte, N. O. Sebti and D. Ziadi: From regular tree expression to position tree automaton. In: Language and Automata Theory and Applications - 7th International Conference, {LATA}, Bilbao 2013, pp. 395-406.   DOI:10.1007/978-3-642-37064-9_35
  25. H.-T. Lu and Y. Wuu: A simple tree pattern-matching algorithm. In: Proc. Workshop on Algorithms and Theory of Computation, Citeseer 2000.   CrossRef
  26. M. Madhavan and P. Shankar: Optimal regular tree pattern matching using pushdown automata. In: Foundations of Software Technology and Theoretical Computer Science, 18th Conference, Chennai 1998, pp. 122-133.   DOI:10.1007/978-3-540-49382-2_11
  27. R. McNaughton and H. Yamada: Regular expressions and finite state graphs for automata. Electronic Computers, IRE Trans. EC-9 (1960), 39-47.   DOI:10.1109/tec.1960.5221603
  28. R. Polách, J. Janoušek and B. Melichar: Regular tree expressions and deterministic pushdown automata. In: Mathematical and Engineering Methods in Computer Science - 7th International Doctoral Workshop, MEMICS, Lednice 2011, pp. 70-77.   CrossRef
  29. E. M. Reingold, K. J. Urban and D. Gries: {K-M-P} string matching revisited. Inf. Process. Lett. 64 (1997), 217-223.   DOI:10.1016/s0020-0190(97)00173-7
  30. K. Thompson: Regular expression search algorithm. Commun. {ACM} 11 (1968), 419-422.   DOI:10.1145/363347.363387
  31. J. Trávníček, J. Janoušek, B. Melichar and L. G. Cleophas: Backward linearised tree pattern matching. In: Language and Automata Theory and Applications - 9th International Conference, LATA, Nice 2015, pp. 599-610.   DOI:10.1007/978-3-319-15579-1_47