Anti-unification in constraint logic programming
From MaRDI portal
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. Under consideration for acceptance in TPLP.
Recommendations
Cites work
- Abstract regular tree model checking
- Conjunctive partial deduction: foundations, control, algorithms, and experiments
- Controlling polyvariance for specialization-based verification
- E-generalization using grammars
- Horn clauses as an intermediate representation for program analysis and transformation
- scientific article; zbMATH DE number 1696824 (Why is no real title available?)
- scientific article; zbMATH DE number 3349329 (Why is no real title available?)
- The semantics of constraint logic programs1Note that reviewing of this paper was handled by the Editor-in-Chief.1
- The subgraph isomorphism problem for outerplanar graphs
- The subsumption lattice and query learning
Cited in
(12)- A library of anti-unification algorithms
- Anti-unification algorithms and their applications in program analysis
- Idempotent anti-unification
- Selective Unification in (Constraint) Logic Programming*
- A new algorithm for computing least generalization of a set of atoms
- Generalization-Driven Semantic Clone Detection in CLP
- Anti-unification for unranked terms and hedges
- Anti-unification of unordered goals
- Global guidance for local generalization in model checking
- A note on the parallel complexity of anti-unification
- Equational anti-unification over absorption theories
- Anti-patterns for rule-based languages
This page was built for publication: Anti-unification in constraint logic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108501)
