Redundancy in logic. I: CNF propositional formulae

DOI10.1016/J.ARTINT.2004.11.002MaRDI QIDQ2457681zbMATH OpenOpenAlexFDO

Authors 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 complexityredundancypropositional logicformula minimization

Mathematics Subject Classification ID

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

Recommendations

• Redundancy in logic. II: 2CNF and Horn propositional formulae
• Redundancy in logic. III: Non-monotonic reasoning
• Removing redundancy from a clause
• Extension and equivalence problems for clause minimal formulae
• A simple heuristic for knowledge base compression

Cites work

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

Cited in

(27)

• Semantic relevance
• SAT-Based Formula Simplification
• On computing minimal independent support and its applications to sampling and counting
• Counting minimal unsatisfiable subsets
• The ghosts of forgotten things: a study on size after forgetting
• Quantified maximum satisfiability
• On preprocessing techniques and their impact on propositional model counting
• Algorithms for computing minimal equivalent subformulas
• BEACON: an efficient SAT-based tool for debugging \(\mathcal {EL}^+\) ontologies
• Logical and algorithmic properties of stable conditional independence
• Redundant disequalities in the Latin square problem
• Minimal sets on propositional formulae. Problems and reductions
• Towards formal XAI: formally approximate minimal explanations of neural networks
• On the complexity of inconsistency measurement
• On redundant topological constraints
• AI*IA 2005: Advances in Artificial Intelligence
• Understanding the complexity of axiom pinpointing in lightweight description logics
• Explanations of unsatisfiability beyond minimal subsets
• Efficient reasoning for inconsistent Horn formulae
• On improving MUS extraction algorithms
• Logical reduction of metarules
• Computing smallest MUSes of quantified Boolean formulas
• Redundancy in logic. II: 2CNF and Horn propositional formulae
• Redundancy in logic. III: Non-monotonic reasoning
• A simple irredundance test for tautological sequents
• Computing MUS-based inconsistency measures
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457681)