Constraint Solving for Sequences
Downloads: Two constraint solvers for sequences.
Description of the program:
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:
S first 1, S last 2, S size 2.Answer:
ins_last(S,S1,1), S first 1, S1 tail .Answer:
S rev [1,2,2].Answer:
S front [1,1,1], S size 5.Answer:
The CHR homepage.