Extended Horn sets in propositional logic
From MaRDI portal
Publication:4302833
DOI10.1145/102782.102789zbMath0942.68721OpenAlexW2040475127MaRDI QIDQ4302833
No author found.
Publication date: 29 September 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/102782.102789
Logic in artificial intelligence (68T27) Classical propositional logic (03B05) Logic programming (68N17)
Related Items
Computing definite logic programs by partial instantiation, A rounding algorithm for integer programs, Properties of SLUR Formulae, Recognition of \(q\)-Horn formulae in linear time, The arborescence-realization problem, The phase transition in random horn satisfiability and its algorithmic implications, A new algorithm for the propositional satisfiability problem, Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing, Domain permutation reduction for constraint satisfaction problems, Hierarchies of polynomially solvable satisfiability problems, On the Boolean connectivity problem for Horn relations, Logic applied to integer programming and integer programming applied to logic, Incremental methods for optimizing partial instantiation, Balanced matrices, Maximum renamable Horn sub-CNFs, Mixed logical-linear programming, Recognition of tractable satisfiability problems through balanced polynomial representations, A logic-based approach to polymer sequence analysis, Solving peptide sequencing as satisfiability, On some tractable classes in deduction and abduction, Computing minimal models by partial instantiation, On finding solutions for extended Horn formulas, About some UP-based polynomial fragments of SAT, Ideal clutters, On exact selection of minimally unsatisfiable subformulae, Solving the resolution-free SAT problem by submodel propagation in linear time, Recognizing renamable generalized propositional Horn formulas is NP- complete, Balanced \(0,\pm 1\) matrices. I: Decomposition, 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, New methods for computing inferences in first order logic, A perspective on certain polynomial-time solvable classes of satisfiability
Uses Software
