On the Combination of Symbolic Constraints, Solution Domains, and Constraint Solvers

Franz BaaderFranz Baader, K. SchulzK. Schulz

Datei:CIS-94-82.ps.gz

Download

Franz Baader, K. Schulz
On the Combination of Symbolic Constraints, Solution Domains, and Constraint Solvers
Technical Report, Universität München, volume 94-82, 1994. {CIS}-Report

Details
Bibtex

KurzfassungAbstract
When combining languages for symbolic constraints, one is typically faced with the problem of how to treat ``mixed constraints. The two main problems are (1) how to define a combined solution structure over which these constraints are to be solved, and (2) how to combine the constraint solving methods for pure constraints into one for mixed constraints. The paper introduces the notion of a ``free amalgamated product as a possible solution to the first problem. Subsequently, we define so-called simply-combinable structures (SC-structures). For SC-structures over disjoint signatures, a canonical amalgamation construction exists, which for the subclass of strong SC-structures yields the free amalgamated product. The combination technique of [Baader&Schulz92,Baader&Schulz95] can be used to combine constraint solvers for (strong) SC-structures over disjoint signatures into a solver for their (free) amalgamated product. In addition to term algebras modulo equational theories, the class of SC-structures contains many solution structures that have been used in constraint logic programming, such as the algebra of rational trees, feature structures, domains consisting of hereditarily finite (wellfounded or non-wellfounded) nested sets and lists.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ CIS-94-82,
  author = {F. {Baader} and K. {Schulz}},
  institution = {Universit\"at M\"unchen},
  number = {94-82},
  title = {On the Combination of Symbolic Constraints, Solution Domains, and Constraint Solvers},
  type = {{CIS}-Report},
  year = {1994},
}