3 citations · 3 across the 4 of their papers we have counts for
Showing cs.PLShow all
3 papers · 1 filter
cs.PL2013
Flow analysis, linearity, and PTIME
David Van Horn, Harry G. Mairson
Flow analysis is a ubiquitous and much-studied component of compiler technology---and its variations abound. Amongst the most well known is Shivers' 0CFA; however, the best known a…
cs.PL2013★ 3 cited
Deciding CFA is complete for EXPTIME
David Van Horn, Harry G. Mairson
We give an exact characterization of the computational complexity of the CFA hierarchy. For any , we prove that the control flow decision problem is complete for determin…
cs.PL2013
The Complexity of Flow Analysis in Higher-Order Languages
David Van Horn
This dissertation proves lower bounds on the inherent difficulty of deciding flow analysis problems in higher-order programming languages. We give exact characterizations of the co…