On the impact of stratification on the complexity of nonmonotonic reasoning

DOI10.1080/11663081.1994.10510830zbMath0820.03013OpenAlexW2988172561MaRDI QIDQ4317728

Jussi Rintanen, Ilkka Niemelä

Publication date: 21 December 1994

Published in: Journal of Applied Non-Classical Logics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/11663081.1994.10510830

zbMATH Keywords

stratificationcomplexitydefault logiclogic programstruth maintenance systemsauto-epistemic logiciterative algorithm for reasoning in stratified auto-epistemic theoriesnonmonotonic modal systemstractable subclasses of nonmonotonic reasoning

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) Logic programming (68N17)

Related Items

Reasoning with minimal models: efficient algorithms and applications ⋮ Backdoors to tractable answer set programming

Cites Work

• Unnamed Item
• Unnamed Item
• Negation by default and unstratifiable logic programs
• The expressive power of stratified logic programs
• Semantical considerations on nonmonotonic logic
• A theory of diagnosis from first principles
• On the relation between default and autoepistemic logic
• Nonmonotonic logic and temporal projection
• Polynomially solvable satisfiability problems
• A logic for default reasoning
• General logical databases and programs: Default logic semantics and stratification
• Hard problems for simple default logics
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A rational reconstruction of nonmonotonic truth maintenance systems
• Horn clause queries and generalizations
• Complexity Results for Nonmonotonic Logics
• Modal nonmonotonic logics
• Autoepistemic logic
• The well-founded semantics for general logic programs
• The complexity of satisfiability problems
• Depth-First Search and Linear Graph Algorithms