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

The static analysis of cache accesses consists in correctly predicting whichaccesses are hits or misses. While there exist good exact and approximateanalyses for caches implementing the least recently used (LRU) replacementpolicy, such analyses were harder to find for other replacement policies. Atheoretical explanation was found: for an appropriate setting of analysis overcontrol-flow graphs, cache analysis is PSPACE-complete for all commonreplacement policies (FIFO, PLRU, NMRU) except for LRU, for which it is onlyNP-complete. In this paper, we show that if procedure calls are added to thecontrol flow, then the gap widens: analysis remains NP-complete for LRU, butbecomes EXPTIME-complete for the three other policies. For this, we improve onearlier results on the complexity of reachability problems on Boolean programswith procedure calls. In addition, for the LRU policy we derive a backtrackingalgorithm as well as an approach for using it as a last resort after otheranalyses have failed to conclude.

The complexity gap in the static analysis of cache accesses grows if procedure calls are added