prologsicstus-prologclpfd

How to use clpfd:automaton to restrict counter value in SICStus Prolog?


I want to implement a very simple automaton that restrict the number of consecutive 1s in a list of ones and zeros (e.g. [0,1,1,0,1,1,1]).

My automaton looks like this:

% 'Day' is a list of clpfd variables
% 'Allowed' is an integer
%
% consecutiveOnes(+Day, +Allowed)
consecutiveOnes(Day, Allowed) :-

    automaton(Day, _, Day,
        [source(n)],
        [
         arc(n, 0, n, [0]  ),
         arc(n, 1, n, [C+1])
        ],
        [C],
        [0],
        [_N]
    ).



% example 1:
%   consecutiveOnes([0,0,0,1,1,1], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.

% example 2:
%   consecutiveOnes([0,1,1,1,0,0], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.


% example 3:
%   consecutiveOnes([0,1,1,0,0,0], 2)  -> there are only two consecutive 1s and we allow 2 -> OK

How can I add the constraint for counter C specifying C <= Allowed to the Prolog code above?


Solution

  • It may be best to formulate this with additional states. For example, for at most two consecutive 1s:

    :- use_module(library(clpfd)).
    
    at_most_two_consecutive_ones(Day) :-
        automaton(Day,
            [source(n),sink(n),sink(n1),sink(n2)],
            [arc(n, 0, n),
             arc(n, 1, n1),
             arc(n1, 1, n2),
             arc(n1, 0, n),
             arc(n2, 1, false),
             arc(n2, 0, n)
            ]).
    

    Example queries:

    ?- at_most_two_consecutive_ones([0,0,0,1,1,1]).
    false.
    
    ?- at_most_two_consecutive_ones([0,1,1,0,1,1]).
    true.
    
    ?- at_most_two_consecutive_ones([0,1,1,0,1,0]).
    true.
    

    For a more general solution, you have to build an automaton on demand when given the maximal length of a run.