We integrated the constraint solving algorithm into the constraint logic programming schema, obtaining a constraint logic programming language CLP(SC) over the domain of sequences
and contexts. We studied the semantics of this language and identified two special cases of CLP(SC) programs, well-moded and KIF programs, that lead to constraints with the corresponding names, for which the solver computes a complete set of solutions. Although the constraints we consider in this thesis are positive, in well-moded and KIF fragments we can easily enrich them with negation. Well-modedness then guarantees that the eventual test for disequality and non-membership in constraints will be performed on ground sequences and contexts, which can be effectively decided. In the KIF case, disequality and non-membership concerns a single sequence or context variable.
With the help of free and unordered unranked function symbols and sequence variables, we can easily express such well-known data structures as lists and multisets. This gives us
the possibility to encode problems over those domains in CLP(SC). Context and function variables give additional expressive power to for making the encoding more compact and
flexible. This expressive power, combined with the powerful constraint solving mechanism, makes CLP(SC) an useful tool.

Project members:

• Jemal Antidze (Principal Investigator)

• Besik Dundua (Coordinator)