Circumscribing DATALOG: expressive power and complexity

DOI10.1016/S0304-3975(97)00108-4MaRDI QIDQ1127538zbMATH OpenOpenAlexFDO

Authors Marco Cadoli, Luigi Palopoli

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)00108-4

zbMATH Keywords

data complexityDATALOG semantics

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the expressive power of Datalog: tools and a case study.
• Datalog extensions for database queries and updates
• scientific article; zbMATH DE number 1405452
• The expressive power of higher-order Datalog

Cites work

• An algorithm to compute circumscription
• Circumscription - a form of non-monotonic reasoning
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Complexity and undecidability results for logic programming
• Complexity classes and theories of finite models
• Computable queries for relational data bases
• Decidability and definability with circumscription
• Embedding circumscriptive theories in general disjunctive programs
• Fixed-point extensions of first-order logic
• Horn clause queries and generalizations
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4199656 (Why is no real title available?)
• scientific article; zbMATH DE number 4147465 (Why is no real title available?)
• scientific article; zbMATH DE number 176244 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1114053 (Why is no real title available?)
• scientific article; zbMATH DE number 1142327 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 4185010 (Why is no real title available?)
• Multiple total stable models are definitely needed to solve unique solution problems
• Negation as failure: careful closure procedure
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Querying disjunctive databases through nonmonotonic logics
• Relational queries computable in polynomial time
• Structure and complexity of relational queries
• The complexity of model checking for circumscriptive formulae
• The complexity of propositional closed world reasoning and circumscription
• The expressive powers of the logic programming semantics
• The Semantics of Predicate Logic as a Programming Language
• Why not negation by fixpoint?

Cited in

(15)

• Permutation dependency in datalog programs
• Expressive power and complexity of partial models for disjunctive deductive databases
• The expressive powers of stable models for bound and unbound DATALOG queries
• The expressiveness of DAC
• Enhancing context knowledge repositories with justifiable exceptions
• Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
• Compiling problem specifications into SAT
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• The Complexity and Expressive Power of Limit Datalog
• The expressive power of higher-order Datalog
• scientific article; zbMATH DE number 2218053 (Why is no real title available?)
• The Data Complexity of MDatalog in Basic Modal Logics
• Extending stratified datalog to capture complexity classes ranging from \(\mathcal P\) to \(Cal Q\mathcal H\)
• The expressive power of revised Datalog on problems with closure properties
• On the expressive power of Datalog: tools and a case study.

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Circumscribing DATALOG: expressive power and complexity

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