Is intractability of nonmonotonic reasoning a real drawback?

DOI10.1016/S0004-3702(96)00009-4zbMath0907.68182OpenAlexW2017956822WikidataQ58006985 ScholiaQ58006985MaRDI QIDQ1391905

Francesco M. Donini, Marco Cadoli, Marco Schaerf

Publication date: 23 July 1998

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(96)00009-4

zbMATH Keywords

computational complexityknowledge representationnonmonotonic reasoningcompact representations

Mathematics Subject Classification ID

Knowledge representation (68T30)

Related Items

On compact representations of propositional circumscription, Is intractability of nonmonotonic reasoning a real drawback?, Fixed-parameter tractability of disjunction-free default reasoning, Alternative foundations for Reiter's default logic, Preprocessing of intractable problems, Reasoning with infinite stable models, Compiling propositional weighted bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidability and definability with circumscription
• Some consequences of non-uniform conditions on uniform classes
• Foundations of a functional approach to knowledge representation
• Closed-world databases and circumscription
• Negation as failure: careful closure procedure
• On the relationship between circumscription and negation as failure
• A logic for default reasoning
• The decision problem for database dependencies
• Hard problems for simple default logics
• The complexity of propositional closed world reasoning and circumscription
• Computing circumscriptive databases
• Incomplete deductive databases
• Is intractability of nonmonotonic reasoning a real drawback?
• Semantical and computational aspects of Horn approximations
• Deduction in non-Horn databases
• Weak generalized closed world assumption
• The size of a revised knowledge base
• Off-line reasoning for on-line efficiency: knowledge bases
• Reasoning with models
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Complexity Results for Nonmonotonic Logics
• On the Complexity of Timetable and Multicommodity Flow Problems
• A survey of complexity results for non-monotonic logics
• The well-founded semantics for general logic programs
• On compact representations of propositional circumscription