The Complexity of Model Checking for Circumscriptive Formulae

No abstract is available for this paper.

• Publication year

  1992

• Venue

  Information Processing Letters

• Publication date

  1992-11-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0020-0190(92)90049-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Propositional circumscription and extended closed-world reasoning are ΠP2-complete

  1993cited by this paper
• Some computational aspects of circumscription

  1988cited by this paper
• When is Closed World Reasoning Tractable?

  1988cited by this paper
• Applications of Circumscription to Formalizing Common Sense Knowledge

  1987cited by this paper
• On artificial intelligence

  1985cited by this paper
• Computing Circumscription

  1985cited by this paper
• The complexity of satisfiability problems

  1978cited by this paper

• Minimal Model Counting via Knowledge Compilation

  2024cites this paper
• On Lower Bounding Minimal Model Count

  2024cites this paper
• Dynamic Causality

  2023cites this paper
• On Contrastive Explanations for Tree-Based Classifiers

  2023cites this paper
• Graph-based construction of minimal models

  2022cites this paper
• Resolution based algorithms for the transversal hypergraph generation problem

  2020cites this paper
• On Enumerating All the Minimal Models for Particular CNF Formula Classes

  2019cites this paper
• Modular Construction of Minimal Models

  2017cites this paper
• Decomposing Minimal Models

  2016cites this paper
• Query answering in resource-based answer set semantics*

  2016cites this paper
• Knowledge Forgetting in Circumscription: A Preliminary Report

  2015cites this paper
• Knowledge Preemption and Defeasible Rules

  2014cites this paper
• On the tractability of minimal model computation for some CNF theories

  2013cites this paper
• An Algorithm for Enumerating Maximal Models of Horn Theories with an Application to Modal Logics

  2013cites this paper
• Negation as a Resource: a Novel View on Answer Set Semantics

  2013cites this paper
• Marco Cadoli's work on nonmonotonic reasoning

  2013cites this paper
• Trichotomies in the Complexity of Minimal Inference

  2012cites this paper
• Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations

  2011cites this paper
• Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations

  2011cites this paper
• Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs

  2010cites this paper
• Complexity of non-monotonic logics

  2010cites this paper
• Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs

  2009cites this paper
• Trichotomies in the Complexity of Minimal Inference

  2009cites this paper
• On the counting complexity of propositional circumscription

  2008influential citation
• Algorithmic and Computational Complexity Issues of MONET

  2008cites this paper
• Answer Set Programming for the Semantic Web

  2007cites this paper
• Formalising the Common Sense of a Mobile Robot

  2007cites this paper
• Complexity Dichotomies for CSP-related Problems

  2007cites this paper
• Circumscriptive Theorem Prover based on Integration of Guess and Check Programs

  2007cites this paper
• Reasoning under minimal upper bounds in propositional logic

  2006influential citation
• The complexity of model checking for propositional default logics

  2005cites this paper
• An incremental algorithm for generating all minimal models

  2005cites this paper
• Compilation of Intractable Problems and Its Application to Artificial Intelligence

  2004cites this paper
• Compiling Prioritized Circumscription into Answer Set Programming

  2004cites this paper
• Towards higher impact argumentation

  2004cites this paper
• An algebraic approach to the complexity of propositional circumscription

  2004influential citation
• Inverse Circumscription

  2003cites this paper
• The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete

  2003cites this paper
• Disjunctive Logic Programming: A Survey and Assessment

  2002cites this paper
• Preprocessing of Intractable Problems

  2002cites this paper
• Measuring inconsistency in knowledge via quasi-classical models

  2002cites this paper
• Recent Complexity Results on Generation Problems

  2002cites this paper
• The complexity of minimal satisfiability problems

  2001cites this paper
• Dividing and conquering logic

  2001cites this paper
• On the Complexity of Model Checking and Inference in Minimal Models

  2001cites this paper
• Generating all maximal models of a Boolean expression

  2000cites this paper
• A Demand-Driven Algorithm for Generating Minimal Models

  2000cites this paper
• Space Efficiency of Propositional Knowledge Representation Formalisms

  2000cites this paper
• Succinct Representations of Model Based Belief Revision

  2000cites this paper
• Default reasoning from conditional knowledge bases: Complexity and tractable cases

  2000cites this paper
• Complexity Results for Default Reasoning from Conditional Knowledge Bases

  2000cites this paper
• On the Complexity of Theory Curbing

  2000cites this paper
• Subtractive reductions and complete problems for counting complexity classes

  2000cites this paper
• ADemand-drive nAlgorith mfo rGeneratin gMinima lModels

  2000cites this paper
• A New Algorithm for the Transversal Hypergraph

  1999cites this paper
• Efficient implementation of lazy suffix trees

  1999cites this paper
• Logic and Databases: a 20 Year Retrospective -Updated in Honor of Ray Reiter

  1999cites this paper
• Heterogeneous Active Agents, II: Algorithms and Complexity

  1999cites this paper
• Model Checking for Nonmonotonic Logics: Algorithms and Complexity

  1999cites this paper
• Evaluation of an Algorithm for the Transversal Hypergraph Problem

  1999cites this paper
• Simulation, Theory, and Cut Elimination

  1999cites this paper
• Computing Intersections of Horn Theories for Reasoning with Models

  1998cites this paper
• Heterogeneous Active Agents

  1998cites this paper
• Circumscribing DATALOG: Expressive Power and Complexity

  1998cites this paper
• Reasoning with Minimal Models: Efficient Algorithms and Applications

  1997cites this paper
• Reducing Belief Revision to Circumscription (and Vice Versa)

  1997cites this paper
• Comparing Space Efficiency of Propositional Knowledge Representation Formalisms

  1996cites this paper
• Logic and Databases: A 20 Year Retrospective

  1996cites this paper
• On the computational cost of disjunctive logic programming: Propositional case

  1995cites this paper
• On Compact Representations of Propositional Circumscription

  1995cites this paper
• The Complexity of Propositional Closed World Reasoning and Circumscription

  1994cites this paper
• On the Model Checking Complexity of Circumscription Extended Abstract

  1994cites this paper
• A Survey of Complexity Results for Nonmonotonic Logics

  1993cites this paper
• The Bulletin of the EATCS

  year unknowncites this paper
• Journal of Graph Algorithms and Applications an Efficient Algorithm for the Transversal Hypergraph Generation

  year unknowncites this paper