Deciding kCFA is Complete for EXPTIME
| Title | Deciding kCFA is Complete for EXPTIME |
| Publication Type | Conference Papers |
| Year of Publication | 2008 |
| Authors | Van Horn D, Mairson HG |
| Conference Name | ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming |
| Date Published | 2008/// |
| Publisher | ACM |
| ISBN Number | 978-1-59593-919-7 |
| Keywords | complexity, flow analysis |
| Abstract | 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. |
| URL | http://doi.acm.org/10.1145/1411204.1411243 |