English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Answer Set Programming (ASP) is a problem modeling and solving framework forseveral problems in KR with growing industrial applications. Also for studiesof computational complexity and deeper insights into the hardness and itssources, ASP has been attracting researchers for many years. These studiesresulted in fruitful characterizations in terms of complexity classes,fine-grained insights in form of dichotomy-style results, as well as detailedparameterized complexity landscapes. Recently, this lead to a novel resultestablishing that for the measure treewidth, which captures structural densityof a program, the evaluation of the well-known class of normal programs isexpected to be slightly harder than deciding satisfiability (SAT). However, itis unclear how to utilize this structural power of ASP. This paper deals with anovel reduction from SAT to normal ASP that goes beyond well-known encodings:We explicitly utilize the structural power of ASP, whereby we sublinearlydecrease the treewidth, which probably cannot be significantly improved. Then,compared to existing results, this characterizes hardness in a fine-grained wayby establishing the required functional dependency of the dependency graph'scycle length (SCC size) on the treewidth.

Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?