Abstract
We describe a sound, terminating, and complete matching algorithm for terms built over flexible arity function symbols and context, function, sequence, and individual variables. Context and sequence variables allow matching to move in term trees to arbitrary depth and breadth, respectively. The values of variables can be constrained by regular expressions which are not necessarily linear. We describe heuristics for optimization, and discuss applications.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alpuente, M., Ballis, D., Falaschi, M.: A rewriting-based framework for web sites verification. Electr. Notes on Theoretical Comp. Science 124(1), 41–61 (2005)
Benzaken, V., Castagna, G., Frisch, A.: CDuce: an XML-centric general-purpose language. In: Proc. of ICFP 2003, pp. 51–63. ACM Press, New York (2003)
Boley, H.: A Tight, Practical Integration of Relations and Functions. LNCS, vol. 1712. Springer, Heidelberg (1999)
Bonifati, A., Ceri, S.: Comparative analysis of five XML query languages. ACM SIGMOD Record 29(1), 68–79 (2000)
Brüggemann-Klein, A.: Regular expressions into finite automata. Theoretical Computer Science 120(2), 197–213 (1993)
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets. Technical Report HKUST-TCSC-2001-05, Hong Kong University of Science and Technology (2001)
Bry, F., Koch, C., Furche, T., Schaffert, S., Badea, L., Berger, S.: Querying the web reconsidered: Design principles for versatile web query languages. Int. J. Semantic Web Inf. Syst. 1(2), 1–21 (2005)
Bry, F., Schaffert, S.: Towards a declarative query and transformation language for XML and semistructured data: Simulation unification. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, p. 255. Springer, Heidelberg (2002)
Buchberger, B., Crǎciun, A.: Algorithm synthesis by Lazy Thinking: Examples and implementation in Theorema. Electr. Notes Theor. Comput. Sci. 93, 24–59 (2004)
Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol. 3091, pp. 105–118. Springer, Heidelberg (2004)
Chasseur, E., Deville, Y.: Logic program schemas, constraints and semi-unification. In: Fuchs, N.E. (ed.) LOPSTR 1997. LNCS, vol. 1463, pp. 69–89. Springer, Heidelberg (1998)
Clark, J., DeRose, S. (eds.): XML Path Language (XPath) Version 1.0. W3C (1999), Available from, http://www.w3.org/TR/xpath/
Comon, H.: Completion of rewrite systems with membership constraints. Part I: Deduction rules. J. Symbolic Computation 25(4), 397–419 (1998)
Comon, H.: Completion of rewrite systems with membership constraints. Part II: Constraint solving. J. Symbolic Computation 25(4), 421–453 (1998)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), Available from, http://www.grappa.univ-lille3.fr/tata
Frick, M., Grohe, M.: Ch. Koch. Query evaluation on compressed trees. In: Proc. of LICS 2003, pp. 188–198. IEEE Computer Society, Los Alamitos (2003)
Frisch, A., Cardelli, L.: Greedy regular expression matching. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 618–629. Springer, Heidelberg (2004)
Furche, T., Bry, F., Schaffert, S., Orsini, R., Horroks, I., Kraus, M., Bolzer, O.: Survey over existing query and transformation languages (2004), Available from, http://rewerse.net/deliverables/i4-d1.pdf
Gapeyev, V., Pierce, B.C.: Regular object types. In: Cardelli, L. (ed.) ECOOP 2003. LNCS, vol. 2743, pp. 151–175. Springer, Heidelberg (2003)
Ginsberg, M.: The MVL theorem proving system. SIGART Bull 2(3), 57–60 (1991)
Gottlob, G., Koch, C.: Monadic Datalog and the expressive power of languages for web information retrieval. J. ACM 51(1), 74–113 (2004)
Gottlob, G., Koch, C., Schulz, K.: Conjunctive queries over trees. In: Deutsch, A. (ed.) Proc. of PODS 2004, pp. 189–200. ACM Press, New York (2004)
Hamana, M.: Term rewriting with sequences. In: Proc. of the First Int. Theorema Workshop. Technical report 97–20, RISC, Johannes Kepler University, Linz (1997)
Hosoya, H.: Regular expression pattern matching—a simpler design. Manuscript (2003)
Hosoya, H., Pierce, B.: Regular expression pattern matching for XML. J. Functional Programming 13(6), 961–1004 (2003)
Kutsia, T.: Solving and Proving in Equational Theories with Sequence Variables and Flexible Arity Symbols. PhD thesis, Johannes Kepler University, Linz (2002)
Kutsia, T.: Unification with sequence variables and flexible arity symbols and its extension with pattern-terms. In: Calmet, J., Benhamou, B., Caprotti, O., Hénocque, L., Sorge, V. (eds.) AISC 2002 and Calculemus 2002. LNCS (LNAI), vol. 2385, pp. 290–304. Springer, Heidelberg (2002)
Kutsia, T.: Solving equations involving sequence variables and sequence functions. In: Buchberger, B., Campbell, J. (eds.) AISC 2004. LNCS (LNAI), vol. 3249, pp. 157–170. Springer, Heidelberg (2004)
Kutsia, T.: Context sequence matching for XML. In: Alpuente, M., Escobar, S., Falaschi, M. (eds.) Proc. of WWV 2005, pp. 103–119 (2005) (Full version to appear in ENTCS).
Kutsia, T., Marin, M.: Matching with regular constraints. Technical Report 05-05, RISC, Johannes Kepler University, Linz (2005)
Levy, J., Villaret, M.: Linear second-order unification and context unification with tree-regular constraints. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol. 1833, pp. 156–171. Springer, Heidelberg (2000)
Maier, D.: Database desiderata for an XML query language (1998), Available from, http://www.w3.org/TandS/QL/QL98/pp/maier.html
Marin, M.: Introducing ρLog (2005), Available from, http://www.score.is.tsukuba.ac.jp/~mmarin/RhoLog/
Marin, M., Ţepeneu, D.: Programming with sequence variables: The Sequentica package. In: Proc. of the 5th Int. Mathematica Symposium, pp. 17–24 (2003)
Marin, M., Ida, T.: Progress of ρLog , a rule-based programming system. In: 7th Intl. Mathematica Symposium (IMS 2005), Perth, Australia (2005) (to appear)
Neumann, A., Seidl, H.: Locating matches of tree patterns in forests. In: Arvind, V., Sarukkai, S. (eds.) FST TCS 1998. LNCS, vol. 1530, pp. 134–145. Springer, Heidelberg (1998)
Neven, F., Schwentick, T.: Query automata on finite trees. Theoretical Computer Science 275, 633–674 (2002)
Niehren, J., Planque, L., Talbot, J.-M., Tison, S.: N-ary queries by tree automata. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 217–231. Springer, Heidelberg (2005)
Schmidt-Schauß, M.: A decision algorithm for stratified context unification. J. Logic and Computation 12(6), 929–953 (2002)
Schmidt-Schauß, M., Schulz, K.U.: Solvability of context equations with two context variables is decidable. J. Symbolic Computation 33(1), 77–122 (2002)
Schmidt-Schauß, M., Stuber, J.: On the complexity of linear and stratified context matching problems. Theory Comput. Systems 37, 717–740 (2004)
Sekar, R.C., Ramakrishnan, I.V., Voronkov, A.: Term indexing. In: Robinson, J.A., Voronkov, A. (eds.) Handbook of Automated Reasoning, pp. 1853–1964. Elsevier and MIT Press (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kutsia, T., Marin, M. (2005). Matching with Regular Constraints. In: Sutcliffe, G., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2005. Lecture Notes in Computer Science(), vol 3835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11591191_16
Download citation
DOI: https://doi.org/10.1007/11591191_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30553-8
Online ISBN: 978-3-540-31650-3
eBook Packages: Computer ScienceComputer Science (R0)