Methods of searching lattice structure and their applications to constraint satisfaction problems

✍ Scribed by Hidehiro Shimizu; Ikuo Tahara

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 812 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690250502

✦ Synopsis

Abstract

The lattice structure often is employed in the representation of the knowledge and the search space as a method to represent the combinatorial relations of concepts, attributes, conditions and facts. In the information processing based on the lattice structure, often it is required to specify the element or region in the lattice structure.

This paper shows that the operations among the families of sets can be reduced to the operations among the sets, which are elements of the families. This is done by defining the new representation and the operation rules for the region in the lattice structure. Several methods for region search in the lattice structure are proposed based on the result.

As a special case, the solution of the constraint satisfaction problem represented by the lattice structure is discussed. The proposed methods are not restricted by the number of elements in the whole set. They are advantageous in that the success of the search is guaranteed since the methods are independent of the order of the search.