💡 clingexplaid

This library collects tools for explaining why an ASP program is unsatisfiable. We build on top of the clingo API to offer preprocessing, subset computation, and constraint analysis helpers for building explanation systems. This repository is part of the Potassco suite.

📦 Installation

Clingo-Explaid can easily be installed with pip:

pip install clingexplaid

Requirements : python >= 3.11 & clingo >= 5.7.1

Building from Source

Please refer to DEVELOPEMENT

🚀 Getting Started

The following Examples show use-cases for clingexplaid's API.

Pre-Processing

Transforming facts to Assumptions

from clingexplaid.preprocessors import AssumptionPreprocessor
from clingexplaid.preprocessors import (
    FilterSignature,
    FilterPattern,
)

PROGRAM = """
a(book;magazine;video).
b(test).
c(1..10).
d(1..3).
"""

ap = AssumptionPreprocessor(filters=[FilterSignature("a", 1), FilterPattern("d(2)")])
result = ap.process(PROGRAM)
# You can either use the return value of `ap.process`
print(result)
# Or use `ap.control` with your transformed program already added
print(ap.control)

Transforming facts to Assumptions with custom Control

import clingo
from clingexplaid.preprocessors import AssumptionPreprocessor, FilterSignature, FilterPattern

FILE = "local/encoding.lp"

ctl = clingo.Control("0")
ap = AssumptionPreprocessor(control=ctl, filters=[FilterSignature("a", 1), FilterPattern("d(2)")])
ap.process_files([FILE])

# The transformed files are added to ctl so it can be directly used
ctl.ground([("base", [])])
ctl.solve()

Computing relevant subsets (MUS, MSS, MCS)

Finding a single MUS

from clingexplaid.preprocessors import AssumptionPreprocessor, FilterSignature
from clingexplaid.unsat import SubsetComputer

PROGRAM = """
a(1..3).
{b(4..6)}.

a(X) :- b(X).

:- a(X), X>=3.
"""

ap = AssumptionPreprocessor(filters={FilterSignature("a", 1)})
ap.process(PROGRAM)
ap.control.ground([("base", [])])
sc = SubsetComputer(ap.control, ap.assumptions)


def shrink_on_core(core) -> None:
    mus = sc.mus(core)
    print(mus)


ap.control.solve(assumptions=list(ap.assumptions), on_core=shrink_on_core)

The SubsetComputer.mus() method can simple be swapped with SubsetComputer.mss() or SubsetComputer.mcs() to compute the respective other subset types

Finding multiple MUSs

from clingexplaid.preprocessors import AssumptionPreprocessor
from clingexplaid.unsat import SubsetComputer

PROGRAM = """
a(1..3).
b(1..3).

:- a(X), b(X).
"""

ap = AssumptionPreprocessor()
ap.process(PROGRAM)
ap.control.ground([("base", [])])
sc = SubsetComputer(ap.control, ap.assumptions)

for i, mus in enumerate(sc.multiple()):
    print(f"{i}:", mus)

Finding multiple MUSs with a custom Lattice

Clingo-Explaid's SubsetComputer uses an internal Lattice to decide the order in which subset candidates are explored. By default it uses the AssumptionLattice, which is defined in this MUS core utilities repository musclingo. You can also use your own lattice, by defining a custom LatticeFactory that provides it to the SubsetComputer. The following is an example showing this by re-implementing the AssumptionLattice.

from clingexplaid.preprocessors import AssumptionPreprocessor
from clingexplaid.unsat import SubsetComputer
from clingexplaid.unsat.lattice import LatticeFactory

PROGRAM = """
a(1..3).
b(1..3).

:- a(X), b(X).
"""


class MyLatticeFactory(LatticeFactory):
    def __init__(self, bias: bool):
        super().__init__()
        self._bias = bias

    def new(self, literals: set[int]):
        return AssumptionLattice(literals, bias=self._bias)


ap = AssumptionPreprocessor()
ap.process(PROGRAM)
ap.control.ground([("base", [])])
sc = SubsetComputer(ap.control, ap.assumptions, lattice_factory=MyLatticeFactory(True))

for i, mus in enumerate(sc.multiple()):
    print(f"{i}:", mus)

Finding multiple relevant subsets (MUS, MSS, and MCS)

from clingexplaid.preprocessors import AssumptionPreprocessor
from clingexplaid.unsat import SubsetComputer
from clingexplaid.unsat.sets import [
    MinimalUnsatisfiableSubset,
    MaximalSatisfiableSubset,
    MinimalCorrectionSet
]

PROGRAM = """
a(1..3).
b(1..3).

:- a(X), b(X).
"""

ap = AssumptionPreprocessor()
ap.process(PROGRAM)
ap.control.ground([("base", [])])
sc = SubsetComputer(ap.control, ap.assumptions)

types = [MinimalUnsatisfiableSubset, MaximalSatisfiableSubset, MinimalCorrectionSet]
for i, subset in enumerate(sc.multiple(types)):
    print(f"{i}:", subset)

Unsatisfiable Constraints

from clingexplaid.unsat_constraints import UnsatConstraintComputer

PROGRAM = """
a(1..3).
{b(4..6)}.

a(X) :- b(X).

:- a(X), X>=3.
"""

ucc = UnsatConstraintComputer()
ucc.parse_string(PROGRAM)
unsat_constraints = ucc.get_unsat_constraints()

for uc_id, unsat_constraint in unsat_constraints.items():
    print(f"Unsat Constraint {uc_id}:", unsat_constraint)