A Specialization System for Domain Variables and Equivalent Transformation for Non-Equality Constraints

概要

論文の詳細を見る
We have developed a new theory of representation and computation for domain variables, where a domain variable is a pair of a variable and a domain (a finite set of constants). Domain variables often contribute to efficient computing in constraint satisfaction problems due to the reduction and propagation of domain constraints. While conventional theories for domain variables are based on the logic paradigm, this new theory is based on the equivalent transformation (ET) paradigm, where computation is regarded as equivalent transformation of declarative descriptions. One of the most important differences from the logic paradigm is the existence of a strict and general foundation applicable to many data structures. In the ET paradigm, a class of declarative descriptions, called constraint declarative programs on specialization systems, is used for all possible applications. A specialization system is a mathematical structure that characterizes each application domain. A generic definition of declarative semantics for all constfaint declarative programs has been established. In this paper, a class of specialization systems is proposed to formalize spaces of domain variables. Bsic propositions are proven justifying equivalent transformation rules for nonequality constraints on the spaces of domain variables.
一般社団法人情報処理学会の論文
1999-05-15