Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T11:32:39.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Anti-unification in Constraint Logic Programming

Published online by Cambridge University Press:  20 September 2019

GONZAGUE YERNAUX Open the ORCID record for GONZAGUE YERNAUX [Opens in a new window]  and
WIM VANHOOF
GONZAGUE YERNAUX
Affiliation:
University of Namur, BelgiumNamur Digital Institute (e-mail: [email protected])
WIM VANHOOF
Affiliation:
University of Namur, BelgiumNamur Digital Institute (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Anti-unification refers to the process of generalizing two (or more) goals into a single, more general, goal that captures some of the structure that is common to all initial goals. In general one is typically interested in computing what is often called a most specific generalization, that is a generalization that captures a maximal amount of shared structure. In this work we address the problem of anti-unification in CLP, where goals can be seen as unordered sets of atoms and/or constraints. We show that while the concept of a most specific generalization can easily be defined in this context, computing it becomes an NP-complete problem. We subsequently introduce a generalization algorithm that computes a well-defined abstraction whose computation can be bound to a polynomial execution time. Initial experiments show that even a naive implementation of our algorithm produces acceptable generalizations in an efficient way.

Keywords

Anti-unification(most specific) generalizationCLPprogram analysis
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 19 , Special Issue 5-6: 35th International Conference on Logic Programming , September 2019 , pp. 773 - 789
Copyright
© Cambridge University Press 2019 

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.)

References

Benkerimi, K. and W. Lloyd, J. 1990. A partial evaluation procedure for logic programs. 343–358.Google Scholar
Bouajjani, A., Habermehl, P., Rogalewicz, A., and Vojnar, T. 2006. Abstract regular tree model checking. Electronic Notes in Theoretical Computer Science 149, 1, 37–48. Proceedings of the 7th International Workshop on Verification of Infinite-State Systems (INFINITY 2005).CrossRefGoogle Scholar
Burghardt, J. 2014. E-generalization using grammars. CoRR abs/1403.8118.Google Scholar
De Schreye, D., Glück, R., Jørgensen, J., Leuschel, M., Martens, B., and Sørensen, M. H. 1999. Conjunctive partial deduction: foundations, control, algorithms, and experiments. The Journal of Logic Programming 41, 2, 231–277.Google Scholar
Fioravanti, F., Pettorossi, A., Proietti, M., and Senni, V. 2013. Controlling polyvariance for specialization-based verification. Fundam. Inform. 124, 4, 483–502.Google Scholar
Gallagher, J. P. 1993. Tutorial on specialisation of logic programs. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation. PEPM ’93. ACM, New York, NY, USA, 88–98.Google Scholar
Gange, G., Navas, J. A., Schachte, P., Søndergaard, H., and Stuckey, P. J. 2015. Horn clauses as an intermediate representation for program analysis and transformation. TPLP 15, 4-5, 526–542.Google Scholar
Gutiérrez-Naranjo, M. A., Alonso-Jiménez, J. A., and Borrego-Díaz, J. 2003. Generalizing programs via subsumption. In Computer Aided Systems Theory - EUROCAST 2003, Moreno-Díaz, R. and Pichler, F., Eds. Springer Berlin Heidelberg, Berlin, Heidelberg, 115–126.Google Scholar
Jaffar, J., Maher, M., Marriott, K., and Stuckey, P. 1998. The semantics of constraint logic programs. The Journal of Logic Programming 37, 1, 1–46.Google Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: a survey. The Journal of Logic Programming 19-20, 503–581. Special Issue: Ten Years of Logic Programming.Google Scholar
Khardon, R. and Arias, M. 2006. The subsumption lattice and query learning. Journal of Computer and System Sciences 72, 1, 72–94.Google Scholar
Leuschel, M., Martens, B., and Schreye, D. D. 1998. Controlling generalization amd polyvariance in partial deduction of normal logic programs. ACM Trans. Program. Lang. Syst. 20, 1, 208–258.Google Scholar
Mesnard, F., Payet, É., and Vanhoof, W. 2016. Towards a framework for algorithm recognition in binary code. In Proceedings of the 18th International Symposium on Principles and Practice of Declarative Programming, Edinburgh, United Kingdom, September 5-7, 2016, Cheney, J. and Vidal, G., Eds. ACM, 202–213.Google Scholar
Pettorossi, A. and Proietti, M. 1998. Program specialization via algorithmic unfold/fold transformations. ACM Comput. Surv. 30, 3es, 6.Google Scholar
Plotkin, G. D. 1970. A note on inductive generalization. Machine Intelligence 5, 153–163.Google Scholar
Sørensen, M. H. and Glück, R. 1999. Introduction to supercompilation. In Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School. Springer-Verlag, Berlin, Heidelberg, 246–270.Google Scholar
Sørensen, M. H. and Glück, R. 1995. An algorithm of generalization in positive supercompilation. In Proceedings of ILPS’95, the International Logic Programming Symposium. MIT Press, 465–479.Google Scholar
Syso, M. M. 1982. The subgraph isomorphism problem for outerplanar graphs. Theoretical Computer Science 17, 1, 91–97.Google Scholar