The expressive power of stratified logic programs

DOI10.1016/0890-5401(91)90059-BzbMath0727.68016OpenAlexW2063545044MaRDI QIDQ803773

Phokion G. Kolaitis

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90059-b

zbMATH Keywords

game treesdatabase queriesfixedpoint logicstratified logic programs

Mathematics Subject Classification ID

Database theory (68P15) Logic programming (68N17) Inductive definability (03D70)

Related Items (27)

Stratified least fixpoint logic ⋮ Non-determinism in logic-based languages ⋮ The expressive powers of stable models for bound and unbound DATALOG queries ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ Polynomial-time computable stable models ⋮ The expressiveness of locally stratified programs ⋮ Complexity and undecidability results for logic programming ⋮ Abduction from logic programs: Semantics and complexity ⋮ On the impact of stratification on the complexity of nonmonotonic reasoning ⋮ Datalog extensions for database queries and updates ⋮ Why not negation by fixpoint? ⋮ On the expressive power of database queries with intermediate types ⋮ A declarative extension of horn clauses, and its significance for datalog and its applications ⋮ The expressive power of the bounded-iteration construct ⋮ Bottom-up evaluation and query optimization of well-founded models ⋮ Capturing complexity classes by fragments of second-order logic ⋮ The functional dimension of inductive definitions ⋮ Complexity and expressive power of second‐order extended Horn logic ⋮ Semantics and expressive power of nondeterministic constructs in deductive databases ⋮ On Q-Resolution and CDCL QBF Solving ⋮ Negation in rule-based database languages: A survey ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ Semantics and expressiveness issues in active databases ⋮ The expressive power of stratified logic programs with value invention ⋮ Unnamed Item ⋮ Functional queries in datalog ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• Fixed-point extensions of first-order logic
• Elementary induction on abstract structures
• Structure and complexity of relational queries
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• Contributions to the Theory of Logic Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The expressive power of stratified logic programs