A uniform approach to constraint-solving for lists, multisets, compact lists, and sets (TR)

Agostino Dovier, Carla Piazza, and Gianfranco Rossi


Lists, multisets, and sets are well-known data structures whose usefulness is widely recognized in various areas of Computer Science. These data structures have been analyzed from an axiomatic point of view with a parametric approach in [DPR98-fuin] and the relevant unification algorithms have been also parametrically developed. In this paper we extend these results considering more general constraints including not only equality but also membership constraints as well as their negative counterparts. This amounts to define the privileged structures for the considered axiomatic theories and to solve the relevant constraint satisfaction problems in each of the theories. Like in [DPR98-fuin], moreover, we adopt a highly parametric approach which allows all the results obtained separately for each single theory to be easily combined so as to obtain a general framework where it is possible to deal with more than one data structure at a time.

Keywords: Constraints, Computable Set and Multiset Theory.


A. Dovier, A. Policriti, and G. Rossi.
A uniform axiomatic view of lists, multisets, and sets, and the relevant unification algorithms.
Fundamenta Informaticae, 36(2/3):201-234, 1998.

Available: 600 DPI PostScript, BibTeX entry.

[Page last updated on January 29, 2002, 11:16:45.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links