Computationally hard problems for logic programs under answer set semantics

DOI10.1145/3676964MaRDI QIDQ6636616zbMATH OpenFDO

Authors Yuping Shen, Xishun Zhao

Publication date 12 November 2024

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3676964

zbMATH Keywords

answer set semanticsexponential lower boundlogic programspropositional formulassuccinctness

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A generalization of the Lin-Zhao theorem
• A taxonomy of problems with fast parallel algorithms
• An observation on time-storage trade off
• Answer set programming
• ASSAT: computing answer sets of a logic program by SAT solvers
• Boolean function complexity. Advances and frontiers.
• Computational Complexity
• Computational Complexity
• Constant Depth Reducibility
• Elements of Information Theory
• Extending and implementing the stable model semantics
• Handbook of satisfiability. In 2 parts
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• scientific article; zbMATH DE number 953683 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Languages that Capture Complexity Classes
• Logic Programming
• Logic Programming and Nonmonotonic Reasoning
• Logic Programming and Nonmonotonic Reasoning
• Logic programs with stable model semantics as a constraint programming paradigm
• Natural proofs
• Nested expressions in logic programs
• Nonmonotonic causal theories
• Nonuniform ACC circuit lower bounds
• On elementary loops of logic programs
• On the succinctness of some modal logics
• Parity, circuits, and the polynomial-time hierarchy
• The probabilistic method
• Tight logic programs
• Two-valued logic programs
• Weight constraints as nested expressions
• What is answer set programming to propositional satisfiability
• Why are there so many loop formulas?

This page was built for publication: Computationally hard problems for logic programs under answer set semantics

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