The complexity of circumscriptive inference in Post's lattice

DOI10.1007/S00224-010-9311-6zbMATH Open1282.68144OpenAlexW2019366780MaRDI QIDQ692903FDOQ692903

Authors: M. C. Fu 

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9311-6

Recommendations

• The Complexity of Circumscriptive Inference in Post’s Lattice
• A dichotomy in the complexity of propositional circumscription
• Logic for Programming, Artificial Intelligence, and Reasoning
• scientific article; zbMATH DE number 1962835
• scientific article; zbMATH DE number 1884382

zbMATH Keywords

complexity theorynonmonotonic reasoningcircumscriptionPost's lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Cites Work

• Title not available (Why is that?)
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Structure and importance of logspace-MOD class
• On the relationship between circumscription and negation as failure
• Circumscription - a form of non-monotonic reasoning
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Satisfiability problems for propositional calculi
• The complexity of propositional implication
• The complexity of model checking for Boolean formulas
• The Complexity of Reasoning for Fragments of Default Logic
• The Complexity of Circumscriptive Inference in Post’s Lattice
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2003
• Generalized Modal Satisfiability
• The complexity of minimal satisfiability problems
• The complexity of propositional closed world reasoning and circumscription
• Logic for Programming, Artificial Intelligence, and Reasoning
• Title not available (Why is that?)
• On compact representations of propositional circumscription
• A dichotomy in the complexity of propositional circumscription
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Generalized Satisfiability for Linear Temporal Logic

Cited In (8)

• Title not available (Why is that?)
• The complexity of propositional implication
• Title not available (Why is that?)
• Complexity of propositional nested circumscription and nested abnormality theories
• Title not available (Why is that?)
• A dichotomy in the complexity of propositional circumscription
• The complexity of propositional closed world reasoning and circumscription
• The Complexity of Circumscriptive Inference in Post’s Lattice

This page was built for publication: The complexity of circumscriptive inference in Post's lattice

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