Why not negation by fixpoint?

DOI10.1016/0022-0000(91)90033-2zbMath0753.68028OpenAlexW2022938902MaRDI QIDQ1176286

Christos H. Papadimitriou, Phokion G. Kolaitis

Publication date: 25 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90033-2

zbMATH Keywords

fixpointsDATALOGinflationary semantics

Mathematics Subject Classification ID

Database theory (68P15) Semantics in the theory of computing (68Q55) Logic programming (68N17)

Related Items

The complexity of propositional closed world reasoning and circumscription, Multiple total stable models are definitely needed to solve unique solution problems, Formalizing a logic for logic programming, Inductive definitions over finite structures, The expressive powers of stable models for bound and unbound DATALOG queries, The expressive power of unique total stable model semantics, Circumscribing DATALOG: expressive power and complexity, Complexity and undecidability results for logic programming, About boundedness for some datalog and DATALOGneg programs, Answer set programming in intuitionistic logic, Datalog extensions for database queries and updates, An analysis of the Core-ML language: Expressive power and type reconstruction, atalog: A logic language for expressing search and optimization problems, Tie-breaking semantics and structural totality, A logic for programming with complex objects, The alternating fixpoint of logic programs with negation, Negation in rule-based database languages: A survey, Negation by default and unstratifiable logic programs, Fundamental properties of deterministic and nondeterministic extensions of Datalog, Expressive power and complexity of partial models for disjunctive deductive databases, Queries and computation on the web, Succinctness as a source of complexity in logical formalisms, On the complexity of data disjunctions., Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\)., Functional queries in datalog, Querying datalog programs with temporal logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressive power of stratified logic programs
• The complexity of facets (and some facets of complexity)
• Fixed-point extensions of first-order logic
• Elementary induction on abstract structures
• Some simplified NP-complete graph problems
• Structure and complexity of relational queries
• A lattice-theoretical fixpoint theorem and its applications
• On the unique satisfiability problem
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Contributions to the Theory of Logic Programming
• A note on succinct representations of graphs
• Reducibility among Combinatorial Problems