%0 Conference Paper %B ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming %D 2008 %T Deciding kCFA is Complete for EXPTIME %A David Van Horn %A Mairson, Harry G. %K complexity %K flow analysis %X 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. %B ICFP '08 Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming %S ICFP '08 %I ACM %P 275 - 282 %8 2008/// %@ 978-1-59593-919-7 %G eng %U http://doi.acm.org/10.1145/1411204.1411243 %0 Conference Paper %B ICFP '07 Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming %D 2007 %T Relating Complexity and Precision in Control Flow Analysis %A David Van Horn %A Mairson, Harry G. %K complexity %K continuation %K control flow analysis %K eta expansion %K geometry of interaction %K linear logic %K normalization %K proofnet %K static analysis %X We analyze the computational complexity of kCFA, a hierarchy of control flow analyses that determine which functions may be applied at a given call-site. This hierarchy specifies related decision problems, quite apart from any algorithms that may implement their solutions. We identify a simple decision problem answered by this analysis and prove that in the 0CFA case, the problem is complete for polynomial time. The proof is based on a nonstandard, symmetric implementation of Boolean logic within multiplicative linear logic (MLL). We also identify a simpler version of 0CFA related to η-expansion, and prove that it is complete for logarithmic space, using arguments based on computing paths and permutations. For any fixed k>0, it is known that kCFA (and the analogous decision problem) can be computed in time exponential in the program size. For k=1, we show that the decision problem is NP-hard, and sketch why this remains true for larger fixed values of k. The proof technique depends on using the approximation of CFA as an essentially nondeterministic computing mechanism, as distinct from the exactness of normalization. When k=n, so that the "depth" of the control flow analysis grows linearly in the program length, we show that the decision problem is complete for exponential time. In addition, we sketch how the analysis presented here may be extended naturally to languages with control operators. All of the insights presented give clear examples of how straightforward observations about linearity, and linear logic, may in turn be used to give a greater understanding of functional programming and program analysis. %B ICFP '07 Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming %S ICFP '07 %I ACM %P 85 - 96 %8 2007/// %@ 978-1-59593-815-2 %G eng %U http://doi.acm.org/10.1145/1291151.1291166 %0 Journal Article %J Computing in Science Engineering %D 2000 %T A perspective on Quicksort %A JaJa, Joseph F. %K algorithm; %K algorithms; %K analysis; %K complexity %K complexity; %K computational %K geometry; %K Parallel %K Quicksort %K sorting; %X This article introduces the basic Quicksort algorithm and gives a flavor of the richness of its complexity analysis. The author also provides a glimpse of some of its generalizations to parallel algorithms and computational geometry %B Computing in Science Engineering %V 2 %P 43 - 49 %8 2000/02//jan %@ 1521-9615 %G eng %N 1 %R 10.1109/5992.814657 %0 Journal Article %J Software Engineering, IEEE Transactions on %D 1995 %T Complexity measure evaluation and selection %A Tian,J. %A Zelkowitz, Marvin V %K alternative %K complexity %K criteria;evaluation %K development %K domain;classification %K environment;evaluation %K evaluation;empirically %K evaluation;software %K feasible %K guided %K measure %K measures;application %K measures;program %K measures;software %K metrics;software %K model;feasible %K performance %K quality;software %K selection; %K software %K trees;complexity %X A formal model of program complexity developed earlier by the authors is used to derive evaluation criteria for program complexity measures. This is then used to determine which measures are appropriate within a particular application domain. A set of rules for determining feasible measures for a particular application domain are given, and an evaluation model for choosing among alternative feasible measures is presented. This model is used to select measures from the classification trees produced by the empirically guided software development environment of R.W. Selby and A.A. Porter, and early experiments show it to be an effective process %B Software Engineering, IEEE Transactions on %V 21 %P 641 - 650 %8 1995/08// %@ 0098-5589 %G eng %N 8 %R 10.1109/32.403788 %0 Journal Article %J Computer Languages %D 1988 %T Program complexity using Hierarchical Abstract Computers %A Bail,William G %A Zelkowitz, Marvin V %K CASE tools %K complexity %K ENVIRONMENTS %K measurement %K Prime programs %X A model of program complexity is introduced which combines structural control flow measures with data flow measures. This complexity measure is based upon the prime program decomposition of a program written for a Hierarchical Abstract Computer. It is shown that this measure is consistent with the ideas of information hiding and data abstraction. Because this measure is sensitive to the linear form of a program, it can be used to measure different concrete representations of the same algorithm, as in a structured and an unstructured version of the same program. Application of the measure as a model of system complexity is given for “upstream” processes (e.g. specification and design phases) where there is no source program to measure by other techniques. %B Computer Languages %V 13 %P 109 - 123 %8 1988/// %@ 0096-0551 %G eng %U http://www.sciencedirect.com/science/article/pii/0096055188900197 %N 3–4 %R 10.1016/0096-0551(88)90019-7