On finding solutions for extended Horn formulas

DOI10.1016/0020-0190(95)00019-9zbMath0875.68451OpenAlexW1974010251MaRDI QIDQ673602

R. P. Swaminathan, Fred S. Annexstein, John S. Schlipf, John V. Franco

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00019-9

zbMATH Keywords

AlgorithmsSatisfiabilityBalanced matricesExtended Horn formulasUnit resolution

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (19)

Properties of SLUR Formulae ⋮ The phase transition in random horn satisfiability and its algorithmic implications ⋮ Generalising and Unifying SLUR and Unit-Refutation Completeness ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ A CNF Class Generalizing Exact Linear Formulas ⋮ Fuzzy logic programs as hypergraphs. Termination results ⋮ Mixed logical-linear programming ⋮ A logic-based approach to polymer sequence analysis ⋮ Solving peptide sequencing as satisfiability ⋮ Bounds on the size of PC and URC formulas ⋮ Satisfiability of Acyclic and almost Acyclic CNF Formulas (II) ⋮ On exact selection of minimally unsatisfiable subformulae ⋮ Propagation complete encodings of smooth DNNF theories ⋮ The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas ⋮ A short note on some tractable cases of the satisfiability problem. ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ A perspective on certain polynomial-time solvable classes of satisfiability ⋮ Generalising unit-refutation completeness and SLUR via nested input resolution

Cites Work

• The arborescence-realization problem
• Extended Horn sets in propositional logic
• Unnamed Item

This page was built for publication: On finding solutions for extended Horn formulas