Tree pattern matching from regular tree expressions

Ahlem Belabbaci; Hadda Cherroun; Loek Cleophas; Djelloul Ziadi

Kybernetika (2018)

  • Volume: 54, Issue: 2, page 221-242
  • ISSN: 0023-5954

Abstract

top
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 𝒪 ( | t | | E | ) time complexity, where | t | is the number of nodes of t and | E | 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.

How to cite

top

Belabbaci, Ahlem, et al. "Tree pattern matching from regular tree expressions." Kybernetika 54.2 (2018): 221-242. <http://eudml.org/doc/294555>.

@article{Belabbaci2018,
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.},
author = {Belabbaci, Ahlem, Cherroun, Hadda, Cleophas, Loek, Ziadi, Djelloul},
journal = {Kybernetika},
keywords = {tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching},
language = {eng},
number = {2},
pages = {221-242},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Tree pattern matching from regular tree expressions},
url = {http://eudml.org/doc/294555},
volume = {54},
year = {2018},
}

TY - JOUR
AU - Belabbaci, Ahlem
AU - Cherroun, Hadda
AU - Cleophas, Loek
AU - Ziadi, Djelloul
TI - Tree pattern matching from regular tree expressions
JO - Kybernetika
PY - 2018
PB - Institute of Information Theory and Automation AS CR
VL - 54
IS - 2
SP - 221
EP - 242
AB - 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.
LA - eng
KW - tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching
UR - http://eudml.org/doc/294555
ER -

References

top
  1. Assaleh, T. A., Ai, W., , 2004. DOI
  2. Aho, A. V., Ganapathi, M., 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. 
  3. Antimirov, V. M., 10.1016/0304-3975(95)00182-4, Theor. Comput. Sci. 155 (1996), 291-319. MR1379579DOI10.1016/0304-3975(95)00182-4
  4. Barry, L., 10.1109/tpami.1981.4767101, IEEE Trans. Pattern Analysis and Machine Intelligence, IEEE Computer Soc. 3 (1981), 285-293. DOI10.1109/tpami.1981.4767101
  5. Barry, L., 10.1109/tpami.1982.4767191, IEEE Trans. Pattern Analysis and Machine Intelligence, IEEE Computer Soc. 4 (1982), 25-34. DOI10.1109/tpami.1982.4767191
  6. Brzozowski, J. A., 10.1145/321239.321249, J. ACM 11 (1964), 481-494. MR0174434DOI10.1145/321239.321249
  7. Champarnaud, J.-M., Ziadi, D., 10.1142/s0218196701000772, IJAC 11 (2001), 707-736. MR1880374DOI10.1142/s0218196701000772
  8. Champarnaud, J.-M., Ziadi, D., 10.1016/s0304-3975(01)00267-5, Theor. Comput. Sci. 289 (2002), 137-163. MR1932893DOI10.1016/s0304-3975(01)00267-5
  9. Cleophas, L., Tree Algorithms: Two Taxonomies and a Toolkit., PhD Thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 2008. 
  10. Comon, H., Dauchet, M., Gilleron, R., Loding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M., Tree Automata Techniques and Applications. 
  11. Dufayard, J.-F., Duret, L., Penel, S., Gouy, M., Rechenmann, F., Perrière, G., 10.1093/bioinformatics/bti325, Bioinformatics, Oxford Univ Press, 21 (2005), 2596-2603. DOI10.1093/bioinformatics/bti325
  12. Flouri, T., Iliopoulos, C. S., Janoušek, J., Melichar, B., Pissis, S. P., 10.1016/j.jda.2012.10.003, J. Discrete Algorithms 17 (2012), 15-23. MR3003394DOI10.1016/j.jda.2012.10.003
  13. Fraser, Ch. W., Henry, R. R., Proebsting, T. A., 10.1145/131080.131089, SIGPLAN Not, ACM 27 (1992), 68-76. DOI10.1145/131080.131089
  14. Genet, T., Klay, F., 10.1007/10721959_21, In: Proc. 17th International Conference on Automated Deduction, CADE-17, Springer-Verlag, London 2000, pp. 271-290. DOI10.1007/10721959_21
  15. Giegerich, R., A Declarative Approach to the Development of Dynamic Programming Algorithms, Applied to RNA Folding., Report, 1998. 
  16. Glushkov, V. M., 10.1070/rm1961v016n05abeh004112, Russian Math. Surveys 16 (1961) 1-53. MR0138529DOI10.1070/rm1961v016n05abeh004112
  17. Goebelbecker, E., Using grep: Moving from DOS? Discover the power of this Linux utility., Linux Journal, Belltown Media 18 (1995). 
  18. Goubault-Larrecq, J., 10.1007/3-540-45591-4_134, In: Parallel and Distributed Processing, Springer 2000, pp. 977-984. DOI10.1007/3-540-45591-4_134
  19. Gräf, A., 10.1007/3-540-53904-2_107, In: Rewriting Techniques and Applications, Springer 1991, pp. 323-334. MR1104491DOI10.1007/3-540-53904-2_107
  20. Hoffmann, Ch. M., O'Donnell, M. J., 10.1145/322290.322295, J. ACM 29 (1982), 68-95. MR0662611DOI10.1145/322290.322295
  21. Itokawa, Y., Wada, M., Ishii, T., Uchida, T., 10.1007/978-1-4614-1695-1_27, In: Intelligent Control and Innovative Computing, Lecture Notes in Electrical Engineering, Springer US 2012, pp. 349-361. DOI10.1007/978-1-4614-1695-1_27
  22. Kron, H. H., Tree Templates and Subtree Transformational Grammars., PhD Thesis, University of California, Santa Cruz 1975. 
  23. Kuske, D., Meinecke, I., 10.1051/ita/2011107, RAIRO - Theor. Inf. and Appl. 45 (2011), 347-370. MR2836494DOI10.1051/ita/2011107
  24. Laugerotte, É., Sebti, N. O., Ziadi, D., 10.1007/978-3-642-37064-9_35, In: Language and Automata Theory and Applications - 7th International Conference, {LATA}, Bilbao 2013, pp. 395-406. MR3090335DOI10.1007/978-3-642-37064-9_35
  25. Lu, H.-T., Wuu, Y., A simple tree pattern-matching algorithm., In: Proc. Workshop on Algorithms and Theory of Computation, Citeseer 2000. 
  26. Madhavan, M., Shankar, P., 10.1007/978-3-540-49382-2_11, In: Foundations of Software Technology and Theoretical Computer Science, 18th Conference, Chennai 1998, pp. 122-133. MR1733926DOI10.1007/978-3-540-49382-2_11
  27. McNaughton, R., Yamada, H., 10.1109/tec.1960.5221603, Electronic Computers, IRE Trans. EC-9 (1960), 39-47. DOI10.1109/tec.1960.5221603
  28. Polách, R., Janoušek, J., Melichar, B., 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. 
  29. Reingold, E. M., Urban, K. J., Gries, D., 10.1016/s0020-0190(97)00173-7, Inf. Process. Lett. 64 (1997), 217-223. MR1492846DOI10.1016/s0020-0190(97)00173-7
  30. Thompson, K., 10.1145/363347.363387, Commun. {ACM} 11 (1968), 419-422. DOI10.1145/363347.363387
  31. Trávníček, J., Janoušek, J., Melichar, B., Cleophas, L. G., 10.1007/978-3-319-15579-1_47, In: Language and Automata Theory and Applications - 9th International Conference, LATA, Nice 2015, pp. 599-610. MR3344835DOI10.1007/978-3-319-15579-1_47

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.