Redundancy in logic. I: CNF propositional formulae

DOI10.1016/j.artint.2004.11.002zbMath1132.68736OpenAlexW2058793155MaRDI QIDQ2457681

Paolo Liberatore

Publication date: 23 October 2007

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

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

zbMATH Keywords

computational complexitypropositional logicredundancyformula minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Knowledge representation (68T30) Classical propositional logic (03B05)

Related Items (20)

On computing minimal independent support and its applications to sampling and counting ⋮ Quantified maximum satisfiability ⋮ On preprocessing techniques and their impact on propositional model counting ⋮ Counting minimal unsatisfiable subsets ⋮ SAT-Based Formula Simplification ⋮ Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Redundancy in logic. III: Non-monotonic reasoning ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ On redundant topological constraints ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ Logical reduction of metarules ⋮ Computing smallest MUSes of quantified Boolean formulas ⋮ Algorithms for computing minimal equivalent subformulas ⋮ On Improving MUS Extraction Algorithms ⋮ Logical and algorithmic properties of stable conditional independence ⋮ BEACON: An Efficient SAT-Based Tool for Debugging $${\mathcal {EL}}{^+}$$ Ontologies ⋮ Efficient Reasoning for Inconsistent Horn Formulae ⋮ On the complexity of inconsistency measurement ⋮ Semantic relevance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Removing redundancy from a clause
• Theory contraction through base contraction
• The complexity of facets resolved
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• On compact representations of propositional circumscription
• Approximating minimal unsatisfiable subformulae by means of adaptive core search
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• The size of a revised knowledge base
• Redundancy in logic. II: 2CNF and Horn propositional formulae
• On the unique satisfiability problem
• Minimal Representation of Directed Hypergraphs
• Minimum Covers in Relational Database Model
• NP trees and Carnap's modal logic
• Compilability and compact representations of revision of Horn knowledge bases
• Strongly equivalent logic programs
• Counterfactuals

This page was built for publication: Redundancy in logic. I: CNF propositional formulae