The expressive power of stratified logic programs

DOI10.1016/0890-5401(91)90059-BMaRDI QIDQ803773zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

game treesdatabase queriesfixedpoint logicstratified logic programs

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4199654 (Why is no real title available?)
• scientific article; zbMATH DE number 4199656 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 4035805 (Why is no real title available?)
• scientific article; zbMATH DE number 4185010 (Why is no real title available?)
• Contributions to the Theory of Logic Programming
• Elementary induction on abstract structures
• Fixed-point extensions of first-order logic
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• Structure and complexity of relational queries

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
• Non-determinism in logic-based languages
• Semantics and expressive power of nondeterministic constructs in deductive databases
• 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
• scientific article; zbMATH DE number 515730 (Why is no real title available?)
• Capturing complexity classes by fragments of second-order logic
• On Q-resolution and CDCL QBF solving
• Stratified least fixpoint logic
• scientific article; zbMATH DE number 1696722 (Why is no real title available?)
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Polynomial-time computable stable models
• Negation in rule-based database languages: A survey
• The functional dimension of inductive definitions
• scientific article; zbMATH DE number 4147555 (Why is no real title available?)
• 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
• Bottom-up evaluation and query optimization of well-founded models
• Complexity and expressive power of second-order extended Horn logic
• On the impact of stratification on the complexity of nonmonotonic reasoning

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)