Autark assignments of Horn CNFs

DOI10.1007/s13160-017-0284-6zbMath1390.68599OpenAlexW2780854972MaRDI QIDQ1742887

Kazuhisa Makino, Kei Kimura

Publication date: 12 April 2018

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-017-0284-6

zbMATH Keywords

combinatorial algorithmHorn CNFBoolean satisfiability problemautark assignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Boolean programming (90C09) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• Some results and experiments in programming techniques for propositional logic
• Polynomial-time inference of all valid implications for Horn and related formulae
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Investigations on autark assignments
• A short note on some tractable cases of the satisfiability problem.
• Parallel cooperative propositional theorem proving
• Introduction to Mathematics of Satisfiability
• Unit Refutations and Horn Sets
• On the Complexity of Timetable and Multicommodity Flow Problems
• Renaming a Set of Clauses as a Horn Set