Additional model if preprocessor is enabled

[rkaminsk]

The program below reports one model too much if the preprocessor is enabled:

asp 1 0 0
1 0 1 1 0 0
1 0 1 2 0 0
1 0 1 3 0 0
1 0 1 4 0 1 5
1 0 1 6 0 1 7
1 0 1 8 0 1 5
1 0 1 9 0 1 7
1 0 2 10 11 0 1 4
1 0 2 12 13 0 2 10 9
1 0 2 10 11 0 2 12 6
1 0 1 14 0 2 5 10
1 0 1 15 0 2 7 10
1 0 1 16 1 1 2 14 1 15 1
1 0 1 17 0 1 -16
1 0 1 18 0 2 5 10
1 0 1 19 0 2 7 10
1 0 1 20 1 1 2 18 1 19 1
1 0 1 21 1 2 2 18 1 19 1
1 0 1 22 0 2 20 -21
1 0 1 23 0 1 22
1 0 1 24 0 2 5 10
1 0 1 25 0 2 7 10
1 0 1 26 1 2 2 24 1 25 1
1 0 1 27 0 1 26
1 1 1 5 0 1 2
1 1 1 7 0 1 3
4 6 f(a,b) 1 5
4 6 f(a,c) 1 7
4 11 friend(a,b) 1 4
4 11 friend(a,c) 1 6
4 11 friend(b,a) 1 8
4 11 friend(c,a) 1 9
4 9 smokes(b) 0
4 9 smokes(a) 1 10
4 9 smokes(c) 1 12
4 13 not_smokes(a) 1 11
4 13 not_smokes(c) 1 13
4 5 cf(0) 1 17
4 5 cf(1) 1 23
4 5 cf(2) 1 27
0

Compare:

➜ clasp -q 0    
clasp version 3.3.8
Reading from stdin
Solving...
SATISFIABLE

Models       : 8
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

and

➜ clasp --eq=0 -q 0
clasp version 3.3.8
Reading from stdin
Solving...
SATISFIABLE

Models       : 7
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

[BenKaufmann]

@rkaminsk Thanks for the report.
It will take a while until I can tackle this. Not only am I completely swamped with work atm, I have also forgotten mostly everything about disjunctive logic programming and the preprocessor.

Maybe interesting: running bin/clasp bug.aspif --pre | bin/clasp -n0 -q also only returns 7 models. So, it's probably some issue in the translation step.

[rkaminsk]

I could try to have a look too. The program is so small that it should be possible to trace everything that happens.

[rkaminsk]

The program can be made smaller:

asp 1 0 0
1 0 1 4 0 1 2
1 0 2 6 7 0 2 4 3
1 0 2 4 5 0 2 6 3
1 0 1 1 0 2 3 4
1 1 1 2 0 0
1 1 1 3 0 0
4 1 x 1 1
4 1 a 1 2
4 1 c 1 3
4 2 pa 1 4
4 2 pc 1 6
4 2 na 1 5
4 2 nc 1 7
0

which is equivalent to

pa :- a.
pc|nc :- pa, c.
pa|na :- pc, c.
x :- c, pa.
{a}.
{c}.

Strangely removing the rule with x in the head and the problem goes away.

[rkaminsk]

Here is the smallest program I managed to come up with:

asp 1 0 0
1 0 1 4 0 1 2
1 0 2 5 6 0 2 3 4
1 0 1 4 0 1 5
1 0 1 1 0 2 3 4
1 1 1 2 0 0
1 1 1 3 0 0
4 1 a 1 1
4 1 b 1 2
4 1 c 1 3
4 1 d 1 4
4 1 t 1 5
4 1 f 1 6
0

or as text

d :- b.
t|f :- c, d.
d :- t.
a :- c, d.
{b}.
{c}.

The preprocessed program is the shifted program below:

clasp --pre | lpconvert --text
d :- b.
a :- c, d.
d :- t.
{b;c}.
t :- a, not f.
f :- a, not t.

So the preprocessor seems to work alright and the problems occurs afterward.

EDIT: Sorry for the many updates.

[BenKaufmann]

Thanks, @rkaminsk 👍
I'll have a look asap. And given these small programs, it shouldn‘t be too hard to find the place where I messed up.

[BenKaufmann]

Looks like the shifted rules are not correctly represented in the program dependency graph used in the unfounded set checker.
The problem only occurs when in a rule like

t|f :- c, d.

the body is replaced with a single atom during shifting. I.e. instead of creating the rule t :- c, d, not f, we create t :- a, not f..
If one drops this simplification (by removing the check for a root atom in LogicProgram::getEqAtomLit()), the unfounded models are no longer returned.

Note: This is mostly a note for me so that I remember what to investigate once I find a couple of hours 😄

[BenKaufmann]

Disabled the problematic simplification for now.

[rkaminsk]

Thanks so much!