Expressive power and complexity of partial models for disjunctive deductive databases

DOI10.1016/S0304-3975(97)00129-1zbMath0913.68053OpenAlexW1974247722MaRDI QIDQ1274974

Nicola Leone, Thomas Eiter, Domenico Saccà

Publication date: 12 January 1999

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

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

zbMATH Keywords

complexityexpressive powerdisjunctive logic programmingdeductive databasespartial model semantics

Mathematics Subject Classification ID

Database theory (68P15)

Related Items

Complexity results for answer set programming with bounded predicate arities and implications, Interlinking logic programs and argumentation frameworks, Partial equilibrium logic, Succinctness as a source of complexity in logical formalisms, On the computational complexity of assumption-based argumentation for default reasoning., Logic programming and knowledge representation---The A-Prolog perspective

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
• Negation in rule-based database languages: A survey
• The expressive power of stratified logic programs
• Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
• On the expressive power of Datalog: tools and a case study.
• Circumscribing DATALOG: expressive power and complexity
• General logical databases and programs: Default logic semantics and stratification
• Why not negation by fixpoint?
• Stable and extension class theory for logic programs and default logics
• The polynomial-time hierarchy
• A restricted second order logic for finite structures
• A three-valued semantics for deductive databases and logic programs
• The expressive powers of stable models for bound and unbound DATALOG queries
• On the partial semantics for disjunctive deductive databases
• Structure and complexity of relational queries
• The expressive powers of the logic programming semantics
• Complexity and undecidability results for logic programming
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• Second order logic and the weak exponential hierarchies
• Short note preferred extensions are partial stable models
• A survey of complexity results for non-monotonic logics
• Autoepistemic logic
• The well-founded semantics for general logic programs
• Logic programming and negation: A survey
• On the equivalence of semantics for normal logic programs
• Deterministic and non-deterministic stable models