Tractable reasoning via approximation

DOI10.1016/0004-3702(94)00009-PzbMath1014.03512OpenAlexW2016515719MaRDI QIDQ1855213

Marco Schaerf, Marco Cadoli

Publication date: 4 February 2003

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

Full work available at URL: https://doi.org/10.1016/0004-3702(94)00009-p

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Other nonclassical logic (03B60) Logic in artificial intelligence (68T27) Mechanization of proofs and logical operations (03B35) Many-valued logic (03B50)

Related Items (26)

Tractable approximate deduction for OWL ⋮ The enduring scandal of deduction. Is propositional logic really uninformative? ⋮ The universe of propositional approximations ⋮ Cut and pay ⋮ A modal view on resource-bounded propositional logics ⋮ On simplification of schema mappings ⋮ Capturing model-based ontology evolution at the instance level: the case of DL-Lite ⋮ Foundations for a Fourth Normal Form over SQL-Like Databases ⋮ Controlling entity integrity with key sets ⋮ An informational view of classical logic ⋮ Semantics and complexity of abduction from default theories ⋮ Measuring Inconsistency for Description Logics Based on Paraconsistent Semantics ⋮ An Algorithm for Computing Inconsistency Measurement by Paraconsistent Semantics ⋮ Sound approximate reasoning about saturated conditional probabilistic independence under controlled uncertainty ⋮ Partial meet pseudo-contractions ⋮ Approximations of modal logics: \(\mathbf K\) and beyond ⋮ On AGM for non-classical logics ⋮ The Universe of Approximations ⋮ Does This Set of Clauses Overlap with at Least One MUS? ⋮ Computational Aspects of Quasi-Classical Entailment ⋮ Approximation Logics for Subclasses of Probabilistic Conditional Independence and Hierarchical Dependence on Incomplete Data ⋮ Local Diagnosis ⋮ Frontiers for propositional reasoning about fragments of probabilistic conditional independence and hierarchical database decompositions ⋮ Approximate coherence-based reasoning ⋮ A probabilistic semantics for belief logic ⋮ Is default logic a reinvention of inductive-statistical reasoning?

Cites Work

• Querying logical databases
• Attributive concept descriptions with complements
• The complexity of existential quantification in concept languages.
• Belief, awareness, and limited reasoning
• Network-based heuristics for constraint-satisfaction problems
• A satisfiability tester for non-clausal propositional calculus
• Polynomially solvable satisfiability problems
• A four-valued semantics for terminological logics
• Hard problems for simple default logics
• A theory of abstraction
• A hierarchy of tractable satisfiability problems
• The complexity of propositional closed world reasoning and circumscription
• Solving propositional satisfiability problems
• Semantical and computational aspects of Horn approximations
• Intuitive semantics for first-degree entailments and `coupled trees'
• ``Reducing classic to practice: Knowledge representation theory meets reality
• Terminological reasoning is inherently intractable
• A decidable first-order logic for knowledge representation
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Login: a logic programming language with built-in inheritance
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of satisfiability problems
• A Machine-Oriented Logic Based on the Resolution Principle
• A Computing Procedure for Quantification Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tractable reasoning via approximation