Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching
tree automata; Thompson Tree automata; regular tree expressions; tree pattern matching
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.
References:
[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 10.1016/0304-3975(95)00182-4 | MR 1379579
[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 10.1109/tpami.1981.4767101
[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 10.1109/tpami.1982.4767191
[6] Brzozowski, J. A.: Derivatives of regular expressions. J. ACM 11 (1964), 481-494. DOI 10.1145/321239.321249 | MR 0174434
[7] Champarnaud, J.-M., Ziadi, D.: From C-continuations to new quadratic algorithms for automaton synthesis. IJAC 11 (2001), 707-736. DOI 10.1142/s0218196701000772 | MR 1880374
[8] Champarnaud, J.-M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289 (2002), 137-163. DOI 10.1016/s0304-3975(01)00267-5 | MR 1932893
[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 10.1093/bioinformatics/bti325
[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 10.1016/j.jda.2012.10.003 | MR 3003394
[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 10.1145/131080.131089
[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 10.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.: The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53. DOI 10.1070/rm1961v016n05abeh004112 | MR 0138529
[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 10.1007/3-540-45591-4_134
[19] Gräf, A.: Left-to-right Tree Pattern Matching. In: Rewriting Techniques and Applications, Springer 1991, pp. 323-334. DOI 10.1007/3-540-53904-2_107 | MR 1104491
[20] Hoffmann, Ch. M., O'Donnell, M. J.: Pattern matching in trees. J. ACM 29 (1982), 68-95. DOI 10.1145/322290.322295 | MR 0662611
[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 10.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.: Construction of tree automata from regular expressions. RAIRO - Theor. Inf. and Appl. 45 (2011), 347-370. DOI 10.1051/ita/2011107 | MR 2836494
[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 10.1007/978-3-642-37064-9_35 | MR 3090335
[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 10.1007/978-3-540-49382-2_11 | MR 1733926
[27] McNaughton, R., Yamada, H.: Regular expressions and finite state graphs for automata. Electronic Computers, IRE Trans. EC-9 (1960), 39-47. DOI 10.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.: {K-M-P} string matching revisited. Inf. Process. Lett. 64 (1997), 217-223. DOI 10.1016/s0020-0190(97)00173-7 | MR 1492846
[30] Thompson, K.: Regular expression search algorithm. Commun. {ACM} 11 (1968), 419-422. DOI 10.1145/363347.363387
[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 10.1007/978-3-319-15579-1_47 | MR 3344835
Search
Partner of
