Multiple total stable models are definitely needed to solve unique solution problems

DOI10.1016/0020-0190(96)00067-1zbMath1023.68514OpenAlexW1968364806WikidataQ126422421 ScholiaQ126422421MaRDI QIDQ1349967

Domenico Saccà

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00067-1

zbMATH Keywords

relational databaseexpressive powerlogic programmingstable modelcomplexity classDATALOG\(^{\neg}\)unique and critical SAT

Mathematics Subject Classification ID

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

Related Items (4)

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 expressive power of deterministic semantics for DATALOG\(^ \neg\).

Uses Software

• Datalog

Cites Work

• The complexity of facets (and some facets of complexity)
• Why not negation by fixpoint?
• Structure and complexity of relational queries
• On the unique satisfiability problem
• Languages that Capture Complexity Classes
• Autoepistemic logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multiple total stable models are definitely needed to solve unique solution problems