Constraint Satisfaction Problems in Clausal Form I: Autarkies and Deficiency
DOI10.3233/FI-2011-428zbMath1242.68289arXiv1103.3693MaRDI QIDQ2895792
Publication date: 4 July 2012
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.3693
satisfiability problem; satisfiability; polynomial time; constraint satisfaction problem; deficiency; signed formulas; autarkies; generalized clause-sets; lean clause-sets; matching autarkies; non-Boolean variables; Boolean translations; direct encoding; disjoint DNF; generalised clause-sets; Hermitian defect; hitting clause-sets; irredundant clause-sets; minimally unsatisfiable clause-sets. deficiency; nested translation
68Q25: Analysis of algorithms and problem complexity
05C90: Applications of graph theory
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
03B05: Classical propositional logic
Uses Software