Bug solving disjunctive program

[rkaminsk]

I managed to produce this rather small program where clasp gobbles answer sets:

a; na.
x; y; z; b; c :- a.
a :- b.
a :- c.

It should provide 6 answer sets (as can be verified for example with cmodels). Interestingly, changing a; na. into a choice rule produces the right results.

A corresponding aspif program is

asp 1 0 0
1 0 2 1 2 0 0
1 0 5 3 4 5 6 7 0 1 1
1 0 1 1 0 1 6
1 0 1 1 0 1 7
4 1 a 1 1
4 2 na 1 2
4 1 x 1 3
4 1 y 1 4
4 1 z 1 5
4 1 b 1 6
4 1 c 1 7
0

It should have the following answer sets:

➜ gringo --output=smodels bug.lp | cmodels 0                  
cmodels version 3.86 Reading...done
Passed this pointProgram is not tight.
Program is Disjunctive.
Program is not HCF.
Calling SAT solver Minisat 2.0 beta ...
Answer: 1 
 Answer set: a y 
Answer: 2 
 Answer set: na 
Answer: 3 
 Answer set: a x 
Answer: 4 
 Answer set: a z 
Answer: 5 
 Answer set: a c 
Answer: 6 
 Answer set: a b 
Number of loops 0

Fixing this problem, would hopefully also resolve the issue reported here: potassco/clingo#425.

[BenKaufmann]

@rkaminsk Thanks for boiling the issue down to this small and manageable example. Nevertheless, please don't hold your breath for a fix. At this point I have forgotten everything about the theory and implementation of disjunctive logic programs so addressing this issue will probably take quite some time.

Until then, could you please check whether passing option --no-gamma would work for the original problem?
It does for your example program provided here:

➜ clasp /tmp/dlp-bug.aspif -n0 --no-gamma
clasp version 3.3.9
Reading from /tmp/dlp-bug.aspif
Solving...
Answer: 1
a b
Answer: 2
a c
Answer: 3
na
Answer: 4
a x
Answer: 5
a y
Answer: 6
a z
SATISFIABLE

Interestingly enough, passing the program through clasp --pre also helps 🤔

[rkaminsk]

@rkaminsk Thanks for boiling the issue down to this small and manageable example. Nevertheless, please don't hold your breath for a fix. At this point I have forgotten everything about the theory and implementation of disjunctive logic programs so addressing this issue will probably take quite some time.

Until then, could you please check whether passing option --no-gamma would work for the original problem? It does for your example program provided here:

I get the correct number of answer sets with this option.

Interestingly enough, passing the program through clasp --pre also helps thinking

Yes, I already noticed that this helped with the original problem. The usual candidate --eq=0 does not make a difference.

Small changes to the above program also lead to correct results. For example, removing one of x, y, or z from the choice rule. That's why I was thinking that maybe it is just some mess up somewhere...

Update: There is also an example in potassco/clingo#425 that produces too many answer sets (including incorrect ones). It also runs correctly using option --no-gamma. If you want to, I can also try to produce a small example that reproduces this behavior.

[rkaminsk]

With this program, I can trigger another assertion:

a :- b.
b :- a.

f :- g.
g :- f.

b; h; e; i :- c.
b; a; c; d :- e.
b; a; g; f; c; e.
b; c; d.

:- d, e.

or in aspif

asp 1 0 0
1 0 6 1 2 3 4 5 6 0 0
1 0 3 1 5 7 0 0
1 0 4 1 2 5 7 0 1 6
1 0 4 1 8 6 9 0 1 5
1 0 0 0 2 6 7
1 0 1 4 0 1 3
1 0 1 3 0 1 4
1 0 1 2 0 1 1
1 0 1 1 0 1 2
4 1 b 1 1
4 1 a 1 2
4 1 g 1 3
4 1 f 1 4
4 1 c 1 5
4 1 h 1 8
4 1 e 1 6
4 1 i 1 9
4 1 d 1 7
0

This assertion is independent of the --no-gamma option.

clasp bug.aspif 
clasp version 3.3.9
Reading from bug.aspif
clasp: ./clasp/src/dependency_graph.cpp:389: Clasp::Literal Clasp::Asp::PrgDepGraph::NonHcfComponent::ComponentMap::Mapping::hp() const: Assertion `disj()' failed.
zsh: IOT instruction  clasp bug.aspif

The same problem slightly shuffled produces one additional wrong answer set:

asp 1 0 0
1 0 3 1 2 3 0 0
1 0 6 1 4 5 6 2 7 0 0
1 0 4 1 8 7 9 0 1 2
1 0 4 1 4 2 3 0 1 7
1 0 0 0 2 7 3
1 0 1 6 0 1 5
1 0 1 5 0 1 6
1 0 1 4 0 1 1
1 0 1 1 0 1 4
4 1 b 1 1
4 1 a 1 4
4 1 g 1 5
4 1 f 1 6
4 1 c 1 2
4 1 h 1 8
4 1 e 1 7
4 1 i 1 9
4 1 d 1 3
0

We can again use cmodels to verify the correct number of answer sets (or clasp --no-gamma):

➜ gringo bug2.lp --output=smodels | cmodels 0
cmodels version 3.86 Reading...done
Passed this pointProgram is not tight.
Program is Disjunctive.
Program is not HCF.
Calling SAT solver Minisat 2.0 beta ...
Answer: 1 
 Answer set: c i 
Answer: 2 
 Answer set: c e 
Answer: 3 
 Answer set: d g f 
Answer: 4 
 Answer set: b a 
Answer: 5 
 Answer set: c h 
Number of loops 2

[rkaminsk]

I could produce something with a bit more structure but had to tiptoe around the assertion. Shuffling the program around produces the assertion mentioned above.

For the program below, we get 4 instead of 3 answer sets:

a :- b.
b :- a.

c :- d.
d :- c.

f :- g.
g :- f.

c; nc.
a; b; f; g; c; d.

The corresponding aspif is:

asp 1 0 0
1 0 6 1 2 3 4 5 6 0 0
1 0 2 5 7 0 0
1 0 1 3 0 1 4
1 0 1 4 0 1 3
1 0 1 5 0 1 6
1 0 1 6 0 1 5
1 0 1 1 0 1 2
1 0 1 2 0 1 1
4 1 b 1 2
4 1 a 1 1
4 1 d 1 6
4 1 c 1 5
4 1 g 1 4
4 1 f 1 3
4 2 nc 1 7
0

[BenKaufmann]

@rkaminsk FYI and just as a small progress update:

With this program, I can trigger another assertion:

This one is legit and triggered because of a real bug in the final pre-processing of disjunctions in LogicProgram::finalizeDisjunctions(). This function removes input disjunctions one by one and then adds relevant new (non-hcf) disjunctions and shifted rules for each removed disjunction. Alas, due to pure stupidity on my end, it does not correctly distinguish between ids of old and new disjunctions and as a result removing an old dependency sometimes actually removes a new depdency from an atom. Once ids are correctly handled, the assertion no longer triggers. The incorrect answer set without --no-gamma still remains, though.

[BenKaufmann]

@rkaminsk I fixed two issues and clasp now seems to compute the correct answer sets for the examples you posted here. I have not checked further programs so I'll leave the issue open for now.

[rkaminsk]

Marvelous, I'll have a look later.

[rkaminsk]

Looks good. Clasp reports the correct answer sets now. I think we can close this.

[rkaminsk]

Thanks so much.

[BenKaufmann]

Looks good. Clasp reports the correct answer sets now. I think we can close this.

Ok, thanks.