The complexity of model checking for circumscriptive formulae
From MaRDI portal
Publication:1205713
DOI10.1016/0020-0190(92)90049-2zbMath0766.68122OpenAlexW2088631785MaRDI QIDQ1205713
Publication date: 1 April 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90049-2
Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Logic in artificial intelligence (68T27)
Related Items
Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs, The complexity of propositional closed world reasoning and circumscription, Generating all maximal models of a Boolean expression, The complexity of minimal satisfiability problems, Reasoning under minimal upper bounds in propositional logic, Reasoning with minimal models: efficient algorithms and applications, Circumscribing DATALOG: expressive power and complexity, On the computational cost of disjunctive logic programming: Propositional case, On the Boolean connectivity problem for Horn relations, On compact representations of propositional circumscription, Reducing belief revision to circumscription (and vice versa), An incremental algorithm for generating all minimal models, On the tractability of minimal model computation for some CNF theories, Trichotomies in the complexity of minimal inference, On the counting complexity of propositional circumscription, Resolution based algorithms for the transversal hypergraph generation problem, Subtractive reductions and complete problems for counting complexity classes, Graph-based construction of minimal models, Default reasoning from conditional knowledge bases: Complexity and tractable cases, Preprocessing of intractable problems
Cites Work
