Constraint Solving for Sequences

• The first version (solver1.pl).

• The second version (solver2.pl).

The object of this page is to present and to compare two methods of constraint solving for sequences.

The first method is inspired from the generalised concatenation (conc) by Thom Fruehwirth and is based on the constraints conc and size. It provides a good constraint propagation and depends less on the order of sequences than the second one. Is garantees a faster constraint solving in the worst case (although the second method can be faster for a very small constraint set).

The second method is based on the constraints begseq / endseq and size. It is less efficient and depends very much on the order of constraints.

Operations on Sequences and Solver Syntax:

We consider the following sequence operations:

N	Operation meaning	Mathematical notation	Example	Solver syntax
1.	The first element	first( S ) = X	first [ 1,2,2,2,3 ] = 1	S first X
2.	The last element	last( S ) = X	last [ 1,2,2,2,3 ] = 3	S last X
3.	Remove the last element	front( S ) = S1	front [ 1,2,2,2,3 ] = [ 1,2,2,2 ]	S front S1
4.	Remove the first element	tail( S ) = S1	tail [ 1,2,2,2,3 ] = [ 2,2,2,3 ]	S tail S1
5.	Prefix	X → S1 = S	1 → [ 2,2,2,3 ] = [ 1,2,2,2,3 ]	ins_first( S, S1, X )
6.	Append	S1 ← X = S	[ 1,2,2,2 ] ← 3 = [ 1,2,2,2,3 ]	ins_last( S, S1, X )
7.	Size	size( S ) = L	size [ 1,2,2,2,3 ] = 5	S size L
8.	Subsequence of the first L elements	S ↑ L = S1	[ 1,2,2,2,3 ] ↑ 2 = [ 1,2 ]	begseq( S, L, S1 )
9.	Subsequence without the first L elements	S ↓ L = S1	[ 1,2,2,2,3 ] ↓ 2 = [ 2,2,3 ]	endseq( S , L , S1 )
10.	Concatenation	S1 ^ S2 = S	[ 1,2 ] ^ [ 2,2,3 ] = [ 1,2,2,2,3 ]	concat( S , S1 , S2 )
11.	Reverse	rev( S1 ) = S2	rev [ 1,2,3 ] = [ 3,2,1 ]	S1 rev S2

Running the Solvers:

The solvers were implemented and tested in SICStus Prolog 3.8.6. They can be consulted and used with SICStus Prolog.

Another possible way to test them is through the WebCHR Online Demo link on this page. You can just type the program text (or copy, for exemple, the file solver1.pl) to the "Program" window in the right-top part of the browser and type your query in the "Query" window. Then press the "Submit" button and get the answer!

Some Examples of Queries:

1. Query:

   S first 1, S last 2, S size 2.

   Answer:

   S=[1,2]

2. Query:

   ins_last(S,S1,1), S first 1, S1 tail [2].

   Answer:

   S=[1,2,1]
   S1=[1,2]

3. Query:

   S rev [1,2,2].

   Answer:

   S=[2,2,1]

4. Query:

   S front [1,1,1], S size 5.

   Answer:

   no

Some Links:

The CHR homepage.