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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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