Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T15:22:50.617Z Has data issue: false hasContentIssue false
  • English
  • Français

CLP(H): Constraint logic programming for hedges*

Published online by Cambridge University Press:  16 April 2015

BESIK DUNDUA ,
MÁRIO FLORIDO ,
TEMUR KUTSIA  and
MIRCEA MARIN
BESIK DUNDUA
Affiliation:
VIAM, Tbilisi State University, Tbilisi, Georgia and LIACC, University of Porto, Porto, Portugal (e-mail: [email protected])
MÁRIO FLORIDO
Affiliation:
DCC-FC and LIACC, University of Porto, Porto, Portugal (e-mail: [email protected])
TEMUR KUTSIA
Affiliation:
RISC, Johannes Kepler University, Linz, Austria (e-mail: [email protected])
MIRCEA MARIN
Affiliation:
West University of Timişoara, Timişoara, Romania (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

CLP(H) is an instantiation of the general constraint logic programming scheme with the constraint domain of hedges. Hedges are finite sequences of unranked terms, built over variadic function symbols and three kinds of variables: for terms, for hedges, and for function symbols. Constraints involve equations between unranked terms and atoms for regular hedge language membership. We study algebraic semantics of CLP(H) programs, define a sound, terminating, and incomplete constraint solver, investigate two fragments of constraints for which the solver returns a complete set of solutions, and describe classes of programs that generate such constraints.

Keywords

constraint logic programmingconstraint solvinghedges
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 16 , Issue 2 , March 2016 , pp. 141 - 162
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This research has been partially supported by LIACC through Programa de Financiamento Plurianual of the Fundação para a Ciência e Tecnologia (FCT), by the FCT fellowship (ref. SFRH/BD/62058/2009), by the Austrian Science Fund (FWF) under the project SToUT (P 24087-N18), and the by Rustaveli Science Foundation under the grants DI/16/4-120/11 and FR/611/4-102/12.

References

Antimirov, V. M. 1996. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155, 2, 291–319.CrossRefGoogle Scholar
Balland, E., Brauner, P., Kopetz, R., Moreau, P. and Reilles, A. 2007. Tom: Piggybacking rewriting on java. In Proc. Term Rewriting and Applications, 18th International Conference, RTA 2007, Paris, France, June 26–28, 2007, Baader, F., Ed. Lecture Notes in Computer Science, vol. 4533. Springer, 36–47.Google Scholar
Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., and Talcott, C. L. Eds. 2007. All About Maude - A High-Performance Logical Framework, How to Specify, Program and Verify Systems in Rewriting Logic. Lecture Notes in Computer Science, vol. 4350. Springer.Google Scholar
Coelho, J. and Florido, M. 2004. CLP(Flex): Constraint logic programming applied to XML processing. In Proc. On the Move to Meaningful Internet Systems 2004: CoopIS, DOA, and ODBASE, OTM Confederated International Conferences, Agia Napa, Cyprus, October 25–29 Part II, Meersman, R. and Tari, Z., Eds. Lecture Notes in Computer Science, vol. 3291. Springer, 1098–1112.Google Scholar
Coelho, J. and Florido, M. 2006. VeriFLog: A constraint logic programming approach to verification of website content. In Proc. Advanced Web and Network Technologies, and Applications, APWeb 2006 International Workshops: XRA, IWSN, MEGA, and ICSE, Harbin, China, January 16–18, 2006, Shen, H. T., Li, J., Li, M., Ni, J. and Wang, W., Eds. Lecture Notes in Computer Science, vol. 3842. Springer, 148–156.Google Scholar
Coelho, J. and Florido, M. 2007. XCentric: Logic programming for XML processing. In Proc. of 9th ACM International Workshop on Web Information and Data Management (WIDM 2007), Lisbon, Portugal, November 9, Fundulaki, I. and Polyzotis, N., Eds. ACM, 1–8.Google Scholar
Colmerauer, A. 1990. An introduction to Prolog III. Communications of the ACM 33, 7, 69–90.Google Scholar
Comon, H. 1998. Completion of rewrite systems with membership constraints. Part II: constraint solving. Journal of Symbolic Computation 25, 4, 421–453.CrossRefGoogle Scholar
Dembinski, P. and Maluszynski, J. 1985. And-parallelism with intelligent backtracking for annotated logic programs. In Proceedings of the 1985 Symposium on Logic Programming, Boston, Massachusetts, USA, July 15–18, IEEE-CS, 29–38.Google Scholar
Dershowitz, N. 1982. Orderings for term-rewriting systems. Theoretical Computer Science 17, 279–301.Google Scholar
Dovier, A., Piazza, C., Pontelli, E. and Rossi, G. 2000. Sets and constraint logic programming. ACM Transactions on Programming Languages and Systems 22, 5, 861–931.CrossRefGoogle Scholar
Dovier, A., Piazza, C. and Rossi, G. 2008. A uniform approach to constraint-solving for lists, multisets, compact lists, and sets. ACM Transactions on Computational Logic 9, 3, 1–30.Google Scholar
Dundua, B., Florido, M., Kutsia, T. and Marin, M. 2014. Constraint logic programming for hedges: A semantic reconstruction. In Proc. of Functional and Logic Programming – 12th International Symposium, FLOPS 2014, Kanazawa, Japan, June 4–6, Codish, M. and Sumii, E., Eds. Lecture Notes in Computer Science, vol. 8475. Springer, 285–301.Google Scholar
Ganzinger, H. and Waldmann, U. 1992. Termination proofs of well-moded logic programs via conditional rewrite systems. In Proc. of Conditional Term Rewriting Systems, 3rd International Workshop, CTRS-92, Pont-à-Mousson, France, July 8–10, Rusinowitch, M. and Remy, J., Eds. Lecture Notes in Computer Science, vol. 656. Springer, 430–437.Google Scholar
Genesereth, M. R. and Fikes, R. E. 1992. Knowledge Interchange Format, Version 3.0 Reference Manual. Tech. Rep. Logic-92-1, Stanford University, Stanford, CA, USA.Google Scholar
Hosoya, H. and Pierce, B. C. 2003. Regular expression pattern matching for XML. Journal of Functional Programming 13, 6, 961–1004.CrossRefGoogle Scholar
Jaffar, J., Maher, M. J., Marriott, K. and Stuckey, P. J. 1998. The semantics of constraint logic programs. Journal of Logic Programming 37, 1–3, 1–46.Google Scholar
Kutsia, T. 2003. Equational prover of Theorema. In Proc. of Rewriting Techniques and Applications, 14th International Conference, RTA 2003, Valencia, Spain, June 9–11, Nieuwenhuis, R., Ed. Lecture Notes in Computer Science, vol. 2706. Springer, 367–379.Google Scholar
Kutsia, T. 2004. Solving equations involving sequence variables and sequence functions. In Proc of Artificial Intelligence and Symbolic Computation, 7th International Conference, AISC 2004, Linz, Austria, September 22–24, Buchberger, B. and Campbell, J. A., Eds. Lecture Notes in Computer Science, vol. 3249. Springer, 157–170.Google Scholar
Kutsia, T. 2007. Solving equations with sequence variables and sequence functions. Journal of Symbolic Computation 42, 3, 352–388.Google Scholar
Kutsia, T. and Marin, M. 2005a. Can context sequence matching be used for querying XML? In Proc. of the 19th International Workshop on Unification UNIF'05, Vigneron, L., Ed. Nara, Japan, 77–92.Google Scholar
Kutsia, T. and Marin, M. 2005b. Matching with regular constraints. In Proc. of Logic for Programming, Artificial Intelligence, and Reasoning, 12th International Conference, LPAR 2005, Montego Bay, Jamaica, December 2–6, Sutcliffe, G. and Voronkov, A., Eds. Lecture Notes in Computer Science, vol. 3835. Springer, 215–229.Google Scholar
Marin, M. and Kutsia, T. 2003. On the implementation of a rule-based programming system and some of its applications. In Proc. of the 4th International Workshop on the Implementation of Logics (WIL'03), Konev, B. and Schmidt, R., Eds. Almaty, Kazakhstan, 55–68.Google Scholar
Marin, M. and Kutsia, T. 2006. Foundations of the rule-based system ρLog. Journal of Applied Non-Classical Logics 16, 1–2, 151–168.Google Scholar
Miller, D. 1991. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation 1, 4, 497–536.Google Scholar
Rajasekar, A. 1994. Constraint logic programming on strings: Theory and applications. In Logic Programming, Proc. of the 1994 International Symposium, Ithaca, New York, USA, November 13–17, Bruynooghe, M., Ed. MIT Press, 681.Google Scholar
van den Brand, M., van Deursen, A., Heering, J., de Jong, H., de Jonge, M., Kuipers, T., Klint, P., Moonen, L., Olivier, P. A., Scheerder, J., Vinju, J. J., Visser, E. and Visser, J. 2001. The ASF+SDF meta-environment: A component-based language development environment. Electronic Notes in Theoretical Computer Science 44, 2, 3–8.Google Scholar
Walinsky, C. 1989. CLP(Σ*): Constraint logic programming with regular sets. In Logic Programming, Proc. of the 6th International Conference, Lisbon, Portugal, June 19–23, Levi, G. and Martelli, M., Eds. MIT Press, 181–196.Google Scholar
Wolfram, S. 2003. The Mathematica Book, 5th ed. Wolfram-Media.Google Scholar
Supplementary material: PDF

Dundua supplementary material

Appendix

Download Dundua supplementary material(PDF)
PDF 289.5 KB