| Title:
|
Tree pattern matching from regular tree expressions (English) |
| Author:
|
Belabbaci, Ahlem |
| Author:
|
Cherroun, Hadda |
| Author:
|
Cleophas, Loek |
| Author:
|
Ziadi, Djelloul |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
54 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
221-242 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
tree automata |
| Keyword:
|
Thompson Tree automata |
| Keyword:
|
regular tree expressions |
| Keyword:
|
tree pattern matching |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 06890417 |
| idMR:
|
MR3807712 |
| DOI:
|
10.14736/kyb-2018-2-0221 |
| . |
| Date available:
|
2018-05-30T15:58:00Z |
| Last updated:
|
2020-01-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147190 |
| . |
| Reference:
|
[1] Assaleh, T. A., Ai, W.: Survey of Global Regular Expression Print (GREP) Tools..2004. |
| Reference:
|
[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. |
| Reference:
|
[3] Antimirov, V. M.: Partial derivatives of regular expressions and finite automaton constructions..Theor. Comput. Sci. 155 (1996), 291-319. MR 1379579, 10.1016/0304-3975(95)00182-4 |
| Reference:
|
[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. 10.1109/tpami.1981.4767101 |
| Reference:
|
[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. 10.1109/tpami.1982.4767191 |
| Reference:
|
[6] Brzozowski, J. A.: Derivatives of regular expressions..J. ACM 11 (1964), 481-494. MR 0174434, 10.1145/321239.321249 |
| Reference:
|
[7] Champarnaud, J.-M., Ziadi, D.: From C-continuations to new quadratic algorithms for automaton synthesis..IJAC 11 (2001), 707-736. MR 1880374, 10.1142/s0218196701000772 |
| Reference:
|
[8] Champarnaud, J.-M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions..Theor. Comput. Sci. 289 (2002), 137-163. MR 1932893, 10.1016/s0304-3975(01)00267-5 |
| Reference:
|
[9] Cleophas, L.: Tree Algorithms: Two Taxonomies and a Toolkit..PhD Thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 2008. |
| Reference:
|
[10] Comon, H., Dauchet, M., Gilleron, R., Loding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications.. |
| Reference:
|
[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. 10.1093/bioinformatics/bti325 |
| Reference:
|
[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. MR 3003394, 10.1016/j.jda.2012.10.003 |
| Reference:
|
[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. 10.1145/131080.131089 |
| Reference:
|
[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. 10.1007/10721959_21 |
| Reference:
|
[15] Giegerich, R.: A Declarative Approach to the Development of Dynamic Programming Algorithms, Applied to RNA Folding..Report, 1998. |
| Reference:
|
[16] Glushkov, V. M.: The abstract theory of automata..Russian Math. Surveys 16 (1961) 1-53. MR 0138529, 10.1070/rm1961v016n05abeh004112 |
| Reference:
|
[17] Goebelbecker, E.: Using grep: Moving from DOS? Discover the power of this Linux utility..Linux Journal, Belltown Media 18 (1995). |
| Reference:
|
[18] Goubault-Larrecq, J.: A Method for Automatic Cryptographic Protocol Verification..In: Parallel and Distributed Processing, Springer 2000, pp. 977-984. 10.1007/3-540-45591-4_134 |
| Reference:
|
[19] Gräf, A.: Left-to-right Tree Pattern Matching..In: Rewriting Techniques and Applications, Springer 1991, pp. 323-334. MR 1104491, 10.1007/3-540-53904-2_107 |
| Reference:
|
[20] Hoffmann, Ch. M., O'Donnell, M. J.: Pattern matching in trees..J. ACM 29 (1982), 68-95. MR 0662611, 10.1145/322290.322295 |
| Reference:
|
[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. 10.1007/978-1-4614-1695-1_27 |
| Reference:
|
[22] Kron, H. H.: Tree Templates and Subtree Transformational Grammars..PhD Thesis, University of California, Santa Cruz 1975. |
| Reference:
|
[23] Kuske, D., Meinecke, I.: Construction of tree automata from regular expressions..RAIRO - Theor. Inf. and Appl. 45 (2011), 347-370. MR 2836494, 10.1051/ita/2011107 |
| Reference:
|
[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. MR 3090335, 10.1007/978-3-642-37064-9_35 |
| Reference:
|
[25] Lu, H.-T., Wuu, Y.: A simple tree pattern-matching algorithm..In: Proc. Workshop on Algorithms and Theory of Computation, Citeseer 2000. |
| Reference:
|
[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. MR 1733926, 10.1007/978-3-540-49382-2_11 |
| Reference:
|
[27] McNaughton, R., Yamada, H.: Regular expressions and finite state graphs for automata..Electronic Computers, IRE Trans. EC-9 (1960), 39-47. 10.1109/tec.1960.5221603 |
| Reference:
|
[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. |
| Reference:
|
[29] Reingold, E. M., Urban, K. J., Gries, D.: {K-M-P} string matching revisited..Inf. Process. Lett. 64 (1997), 217-223. MR 1492846, 10.1016/s0020-0190(97)00173-7 |
| Reference:
|
[30] Thompson, K.: Regular expression search algorithm..Commun. {ACM} 11 (1968), 419-422. 10.1145/363347.363387 |
| Reference:
|
[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. MR 3344835, 10.1007/978-3-319-15579-1_47 |
| . |
