Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0895.68019
Baader, Franz; Schulz, Klaus U.
Combination of constraint solvers for free and quasi-free structures. (English)
[J] Theor. Comput. Sci. 192, No.1, 107-161 (1998). ISSN 0304-3975

Summary: 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. We define so-called quasi-free structures (called ``strong simply-combinable structures'' in a previous publication) as a generalization of free structures. For quasi-free structures over disjoint signatures, we describe a canonical amalgamation construction that yields the free amalgamated product. The combination techniques known from unification theory can be used to combine constraint solvers for quasi-free structures over disjoint signatures into a solver for their free amalgamated product. In addition to term algebras modulo equational theories (i.e., free algebras), the class of quasi-free structures contains many solution structures that are of interest in constraint logic programming, such as the algebra of rational trees, feature structures, and domains consisting of hereditarily finite (well-founded or non-well-founded) nested sets and lists.

MSC 2000:: *68N17 Logic programming
08A70 Appl. of universal algebra in computer science

Keywords: constraint solving; unification; combination; universal algebra

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]