Redundancy in logic. II: 2CNF and Horn propositional formulae

DOI10.1016/j.artint.2007.06.003zbMath1182.68282MaRDI QIDQ2389621

Paolo Liberatore

Publication date: 17 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2007.06.003

zbMATH Keywords

computational complexity; propositional logic; redundancy

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T27: Logic in artificial intelligence

03B05: Classical propositional logic

Related Items

Algorithms for computing minimal equivalent subformulas, Minimal sets on propositional formulae. Problems and reductions, Redundancy in logic. III: Non-monotonic reasoning, Redundancy in logic. I: CNF propositional formulae, Efficient Reasoning for Inconsistent Horn Formulae

Cites Work

• Unnamed Item
• Generating all maximal models of a Boolean expression
• Removing redundancy from a clause
• Graph minors. XX: Wagner's conjecture
• Improving exact algorithms for MAX-2-SAT
• The complexity of facets resolved
• The directed subgraph homeomorphism problem
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Approximating minimal unsatisfiable subformulae by means of adaptive core search
• Extension and equivalence problems for clause minimal formulae
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Redundancy in logic. III: Non-monotonic reasoning
• Redundancy in logic. I: CNF propositional formulae
• The even-path problem for graphs and digraphs
• Minimal Representation of Directed Hypergraphs
• Minimum Covers in Relational Database Model
• On the Complexity of Timetable and Multicommodity Flow Problems
• The Minimization Problem for Boolean Formulas
• Approximating the Minimum Equivalent Digraph
• Computationally Related Problems
• On Cores and Prime Implicants of Truth Functions
• Minimum Witnesses for Unsatisfiable 2CNFs