Circumscribing DATALOG: expressive power and complexity

DOI10.1016/S0304-3975(97)00108-4zbMath0896.68059OpenAlexW2090079575MaRDI QIDQ1127538

Luigi Palopoli, Marco Cadoli

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)

Related Items (3)

Compiling problem specifications into SAT ⋮ Enhancing context knowledge repositories with justifiable exceptions ⋮ Expressive power and complexity of partial models for disjunctive deductive databases

Uses Software

• Datalog

Cites Work

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

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