Constraint Satisfaction Ontology

FLOW ALGEBRA
CONSTRAINT SATISFACTION ONTOLOGY
Kireth Semantic Library | Discrete AI Mathematics
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/constraint-satisfaction-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Mathematical synthesis; source webpage not independently verified.

1. PURPOSE AND SCOPE
Represent finite and infinite constraint satisfaction problems (CSPs),
variables, domains, constraints, assignments, propagation, search,
consistency, satisfiability, optimisation extensions and proofs.

2. TYPED SIGNATURE
sort Variable, Value, Domain, Constraint, Assignment, Problem, Solver,
     SearchState, PropagationEvent, Proof, Objective, Solution.
Domain(v:Variable) -> Set(Value)
Scope(c:Constraint) -> Sequence(Variable)
Relation(c:Constraint) -> Set(Tuple(Value))
Assigned(a:Assignment,v:Variable) -> Option(Value)
Constraints(p:Problem) -> Set(Constraint)
Variables(p:Problem) -> Set(Variable)
Satisfies(a:Assignment,c:Constraint) -> Bool
Consistent(a:Assignment,p:Problem) -> Bool
Complete(a:Assignment,p:Problem) -> Bool
SolutionOf(a:Assignment,p:Problem) -> Bool

3. CORE MODEL
CSP P = (X,D,C), where X={x1,...,xn}, Di is the domain of xi,
and each c in C is a pair (scope(c), relation(c)).
An assignment a is a partial function X ⇀ union(Di).
WellTyped(a,P) iff forall x in dom(a), a(x) in Dx.
Satisfies(a,c) iff scope(c) subseteq dom(a) and the tuple of
assigned values ordered by scope(c) belongs to relation(c).
Consistent(a,P) iff WellTyped(a,P) and no fully assigned
constraint is violated.
SolutionOf(a,P) iff Complete(a,P) and forall c in C, Satisfies(a,c).
SAT(P) iff exists a: SolutionOf(a,P).
UNSAT(P) iff not SAT(P).

4. ENTITY RELATIONSHIPS
Problem HAS_VARIABLE Variable
Variable HAS_DOMAIN Domain
Problem HAS_CONSTRAINT Constraint
Constraint RESTRICTS Variable
Assignment BINDS Variable TO Value
Solver EXPLORES SearchState
PropagationEvent REDUCES Domain
Solution SATISFIES Constraint
Proof JUSTIFIES Solution | UNSAT
Objective EXTENDS Problem INTO ConstraintOptimisationProblem

5. CONSTRAINT FAMILIES
Unary: x in A.
Binary: x != y; x < y; R(x,y).
Global: AllDifferent(X); AtMostK(X,v,k); Cumulative(tasks,capacity).
Arithmetic: sum(ai*xi) <= b.
Logical: implication, conjunction, disjunction, reification.
Extensional: allowed tuples in an explicit relation.
Intensional: predicate evaluated on a tuple.
Hard constraints are mandatory; soft constraints belong to a
weighted/optimisation extension and must not be silently treated as hard.

6. INFERENCE AND PROPAGATION
Domain filtering must preserve every genuine solution.
Node consistency: remove unary-incompatible values.
Arc consistency for binary constraint c(x,y):
  forall a in Dx, exists b in Dy with (a,b) in relation(c).
If no supporting b exists, delete a from Dx.
Generalised arc consistency for c with scope S:
  forall x in S, forall a in Dx, exists allowed tuple t in relation(c)
  compatible with all current domains and with t[x]=a.
Forward checking: after assigning x, remove incompatible values
from directly constrained unassigned variables.
Propagation fixed point: repeat sound reductions until no change.
Domain wipeout: any empty domain in a well-formed finite CSP
implies the current search branch is unsatisfiable.

7. SEARCH FLOW
flow SolveCSP(P):
  require WellFormed(P)
  domains := InitialDomains(P)
  propagate(domains, Constraints(P))
  if any domain empty: return UNSAT
  return Search({},domains)

flow Search(a,domains):
  if all variables assigned:
    if SolutionOf(a,P): return SOLUTION(a)
    else: return FAILURE
  x := choose_unassigned_variable(MRV, degree_tie_break)
  for v in ordered_values(domains[x], least_constraining_first):
    a2 := a union {x -> v}
    if Consistent(a2,P):
      d2 := copy(domains); d2[x] := {v}
      propagate(d2, Constraints(P))
      if all domains nonempty:
        r := Search(a2,d2)
        if r is SOLUTION: return r
  return FAILURE

8. HEURISTICS
MRV: choose variable with smallest remaining domain.
Degree heuristic: tie-break using number of constraints on
unassigned neighbours.
Least-constraining value: prefer values eliminating fewer
remaining neighbour choices.
Heuristics affect efficiency, not correctness, provided search
remains exhaustive when deciding SAT versus UNSAT.

9. CORRECTNESS OBLIGATIONS
Soundness: every reported solution satisfies all constraints.
Propagation preservation: no feasible solution is removed.
Completeness: finite-domain exhaustive backtracking explores every
unpruned admissible assignment, assuming sound pruning.
Termination: finite variables and finite domains, with each branch
assigning at least one new variable and no infinite propagation loop.
UNSAT certificate: an exhaustive search trace or accepted proof system;
failure of a heuristic or time limit alone is not an UNSAT proof.

10. COMPLEXITY
For n variables and maximum finite domain size d, naive search
examines up to d^n complete assignments; constraint checks add cost.
General finite-domain CSP is NP-complete when constraint relations
are represented in a standard polynomially checkable form.
Special structure (e.g. bounded treewidth) may enable more efficient
algorithms; complexity depends on representation and restrictions.
Propagation may reduce search substantially without changing the
worst-case exponential character of general CSP solving.

11. WORKED EXAMPLE: THREE-COLOURING
X = {A,B,C}; DA=DB=DC={red,green,blue}.
C = {A != B, B != C, A != C}.
a = {A:red, B:green, C:blue}.
All domains respected; every inequality true; SolutionOf(a,P)=true.
Counterexample {A:red,B:red,C:blue} violates A != B.

12. WORKED EXAMPLE: UNSAT
X={x,y}; Dx=Dy={0,1}.
C={x=y, x!=y}.
No assignment satisfies both constraints; SAT(P)=false.

13. SEMANTIC EQUIVALENCE
CSP ~ ConstraintNetwork when both denote identical variables,
domains and admissible solution assignments (up to renaming).
Constraint propagation != search; consistency != satisfiability.
Local consistency does not generally imply global consistency.
CSP != SAT syntactically, although finite CSPs can be encoded as SAT.
CSP != COP: a constraint optimisation problem adds an objective.

14. VALIDATION RULES
V01 Every variable has a declared nonempty initial domain, unless
    an explicitly unsatisfiable input is intentionally represented.
V02 Every constraint scope references declared variables.
V03 Every relation tuple matches its scope arity and domain types.
V04 Every reported solution is complete and independently checked.
V05 Every domain reduction records a valid supporting justification.
V06 Search termination and UNSAT claims are appropriately certified.
V07 Distinguish hard constraints, soft constraints and objectives.
V08 Avoid equating arc consistency with global satisfiability.

15. CONFIDENCE
Mathematical definitions and elementary examples: HIGH.
Implementation-specific performance claims: CONTEXT_DEPENDENT.
Page-specific alignment: UNVERIFIED until source text is checked.

16. FLOW_HASH
Canonicalise typed entities, ordered scope declarations, constraint
relations, inference rules and validation assertions as UTF-8.
FLOW_HASH := SHA256(canonical_serialisation).
No hash value is asserted until the canonical bytes are generated.

17. UPDATE_MODEL
On domain/constraint edit: increment ontology revision; revalidate
scope and type references; invalidate affected propagation caches;
recompute solution claims and FLOW_HASH; preserve provenance.

18. AI_CONSUMPTION
Input: typed CSP or natural-language constraints with provenance.
Process: extract variables/domains/relations; type-check; normalise;
propagate; search; verify; attach proof or uncertainty metadata.
Output: SAT with checked assignment; UNSAT with defensible evidence;
or UNKNOWN for resource-limited/undecided runs.
Never present UNKNOWN as UNSAT or an unverified candidate as a solution.

END FLOW ALGEBRA