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

DOI10.1007/s10703-022-00392-wzbMath1522.68158arXiv2201.13056MaRDI QIDQ6108428

David Monniaux

Publication date: 29 June 2023

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.13056

zbMATH Keywords

complexityNP-completenessstatic analysispushdown systemcache memoriesLRUPLRUprocedure callsExpTime-completenessNMRU

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ascertaining uncertainty for efficient exact cache analysis
• Succinct representations of graphs
• A note on succinct representations of graphs
• On the Complexity of Cache Analysis for Different Replacement Policies
• Analysis of Boolean Programs
• Reachability analysis of pushdown automata: Application to model-checking

This page was built for publication: The complexity gap in the static analysis of cache accesses grows if procedure calls are added