TY - CONF
T1 - Deciding kCFA is Complete for EXPTIME
T2 - ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming
Y1 - 2008
A1 - David Van Horn
A1 - Mairson, Harry G.
KW - complexity
KW - flow analysis
AB - We give an exact characterization of the computational complexity of the kCFA hierarchy. For any k > 0, we prove that the control flow decision problem is complete for deterministic exponential time. This theorem validates empirical observations that such control flow analysis is intractable. It also provides more general insight into the complexity of abstract interpretation.
JA - ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming
T3 - ICFP '08
PB - ACM
SN - 978-1-59593-919-7
UR - http://doi.acm.org/10.1145/1411204.1411243
ER -