Title :
On the cubic bottleneck in subtyping and flow analysis
Author :
Heintze, Nevin ; McAllester, David
Author_Institution :
Bell Labs., Murray Hill, NJ, USA
fDate :
29 Jun-2 Jul 1997
Abstract :
We prove that certain data-flow and control-flow problems are 2NPDA-complete. This means that these problems are in the class 2NPDA and that they are hard for that class. The fact that they are in 2NPDA demonstrates the richness of the class. The fact that they are hard for 2NPDA can be interpreted as evidence they can not be solved in sub-cubic time-the cubic time decision procedure for an arbitrary 2NPDA problem has not been improved since its discovery in 1968
Keywords :
computational complexity; context-free grammars; data flow analysis; directed graphs; reachability analysis; type theory; 2NPDA-complete; control-flow; cubic bottleneck; data-flow; flow analysis; sub-cubic time; subtyping; Algorithm design and analysis; Automata; Automatic control;
Conference_Titel :
Logic in Computer Science, 1997. LICS '97. Proceedings., 12th Annual IEEE Symposium on
Conference_Location :
Warsaw
Print_ISBN :
0-8186-7925-5
DOI :
10.1109/LICS.1997.614960
