Redundancy in logic. II: 2CNF and Horn propositional formulae
From MaRDI portal
Publication:2389621
DOI10.1016/j.artint.2007.06.003zbMath1182.68282OpenAlexW2046879559MaRDI QIDQ2389621
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
Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Classical propositional logic (03B05)
Related Items
Redundancy in logic. III: Non-monotonic reasoning ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Logical reduction of metarules ⋮ Algorithms for computing minimal equivalent subformulas ⋮ 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