The expressive power of stratified logic programs

DOI10.1016/0890-5401(91)90059-BzbMATH Open0727.68016OpenAlexW2063545044MaRDI QIDQ803773FDOQ803773

Authors: 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

Recommendations

• The expressiveness of locally stratified programs
• Stratified least fixpoint logic
• The expressive powers of the logic programming semantics
• scientific article
• The expressive power of stratified logic programs with value invention

zbMATH Keywords

game treesdatabase queriesfixedpoint logicstratified logic programs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Fixed-point extensions of first-order logic
• Elementary induction on abstract structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relational queries computable in polynomial time
• Contributions to the Theory of Logic Programming
• Horn clause queries and generalizations
• Structure and complexity of relational queries
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (34)

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

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

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