Deciding \(k\)CFA is complete for EXPTIME

We give an exact characterization of the computational complexity of the \(k\)CFA 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 intracta...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-11
Main Authors: David Van Horn, Mairson, Harry G
Format: Article
Language:English
Subjects:
Complexity
Decision theory
Empirical analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give an exact characterization of the computational complexity of the \(k\)CFA 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.
ISSN:2331-8422