Geodesic
Tree pattern matching from regular tree expressions
Kybernetika, Tome 54 (2018) no. 2, pp. 221-242
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2018-2-0221
Classification : 68Q45
Keywords: tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching 
@article{10_14736_kyb_2018_2_0221,
     author = {Belabbaci, Ahlem and Cherroun, Hadda and Cleophas, Loek and Ziadi, Djelloul},
     title = {Tree pattern matching from regular tree expressions},
     journal = {Kybernetika},
     pages = {221--242},
     year = {2018},
     volume = {54},
     number = {2},
     doi = {10.14736/kyb-2018-2-0221},
     mrnumber = {3807712},
     zbl = {06890417},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/}
}
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
SP  - 221
EP  - 242
VL  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/
DO  - 10.14736/kyb-2018-2-0221
LA  - en
ID  - 10_14736_kyb_2018_2_0221
ER  - 
%0 Journal Article
%A Belabbaci, Ahlem
%A Cherroun, Hadda
%A Cleophas, Loek
%A Ziadi, Djelloul
%T Tree pattern matching from regular tree expressions
%J Kybernetika
%D 2018
%P 221-242
%V 54
%N 2
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0221/
%R 10.14736/kyb-2018-2-0221
%G en
%F 10_14736_kyb_2018_2_0221
Belabbaci, Ahlem; Cherroun, Hadda; Cleophas, Loek; Ziadi, Djelloul. Tree pattern matching from regular tree expressions. Kybernetika, Tome 54 (2018) no. 2, pp. 221-242. doi: 10.14736/kyb-2018-2-0221

[1] Assaleh, T. A., Ai, W.: Survey of Global Regular Expression Print (GREP) Tools. 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.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155 (1996), 291-319. | DOI | MR

[4] Barry, L.: Derivatives of tree sets with applications to grammatical inference. IEEE Trans. Pattern Analysis and Machine Intelligence, IEEE Computer Soc. 3 (1981), 285-293. | DOI

[5] Barry, L.: 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

[6] Brzozowski, J. A.: Derivatives of regular expressions. J. ACM 11 (1964), 481-494. | DOI | MR

[7] Champarnaud, J.-M., Ziadi, D.: From C-continuations to new quadratic algorithms for automaton synthesis. IJAC 11 (2001), 707-736. | DOI | MR

[8] Champarnaud, J.-M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289 (2002), 137-163. | DOI | MR

[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.: 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

[12] Flouri, T., Iliopoulos, C. S., Janoušek, J., Melichar, B., Pissis, S. P.: Tree template matching in ranked ordered trees by pushdown automata. J. Discrete Algorithms 17 (2012), 15-23. | DOI | MR

[13] Fraser, Ch. W., Henry, R. R., Proebsting, T. A.: BURG: Fast optimal instruction selection and tree parsing. SIGPLAN Not, ACM 27 (1992), 68-76. | DOI

[14] Genet, T., Klay, F.: Rewriting for cryptographic protocol verification. In: Proc. 17th International Conference on Automated Deduction, CADE-17, Springer-Verlag, London 2000, pp. 271-290. | DOI

[15] Giegerich, R.: A Declarative Approach to the Development of Dynamic Programming Algorithms, Applied to RNA Folding. Report, 1998.

[16] Glushkov, V. M.: The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53. | DOI | MR

[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.: A Method for Automatic Cryptographic Protocol Verification. In: Parallel and Distributed Processing, Springer 2000, pp. 977-984. | DOI

[19] Gräf, A.: Left-to-right Tree Pattern Matching. In: Rewriting Techniques and Applications, Springer 1991, pp. 323-334. | DOI | MR

[20] Hoffmann, Ch. M., O'Donnell, M. J.: Pattern matching in trees. J. ACM 29 (1982), 68-95. | DOI | MR

[21] Itokawa, Y., Wada, M., Ishii, T., Uchida, T.: 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

[22] Kron, H. H.: Tree Templates and Subtree Transformational Grammars. PhD Thesis, University of California, Santa Cruz 1975.

[23] Kuske, D., Meinecke, I.: Construction of tree automata from regular expressions. RAIRO - Theor. Inf. and Appl. 45 (2011), 347-370. | DOI | MR

[24] Laugerotte, É., Sebti, N. O., Ziadi, D.: 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 | MR

[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.: 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 | MR

[27] McNaughton, R., Yamada, H.: Regular expressions and finite state graphs for automata. Electronic Computers, IRE Trans. EC-9 (1960), 39-47. | DOI

[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.: {K-M-P} string matching revisited. Inf. Process. Lett. 64 (1997), 217-223. | DOI | MR

[30] Thompson, K.: Regular expression search algorithm. Commun. {ACM} 11 (1968), 419-422. | DOI

[31] Trávníček, J., Janoušek, J., Melichar, B., Cleophas, L. G.: Backward linearised tree pattern matching. In: Language and Automata Theory and Applications - 9th International Conference, LATA, Nice 2015, pp. 599-610. | DOI | MR

Cité par Sources :