Matching of Bounded Set Terms in the Logic Language LDL++

This paper is concerned with the problem of matching bounded set terms, i.e., terms of the form { e_l , . . . , e_n}, where e_i is a constant or a variable. Such simplified types of set terms are much used in deductive database systems such as LDL++. There are two main results: (a) the detailed complexity analysis of the problem by providing a formula for determining the number of matchers and (b) the invention of an optimal matching algorithm. This algorithm is also extended to handle bound set terms whose elements are not restricted to be constants or variables.