Paper: On the Cubic Bottleneck in Subtyping and Flow Analysis (at LICS 1997)

Authors: Nevin Heintze David A. McAllester

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.

BibTeX

  @InProceedings{HeintzeMcAllester-OntheCubicBottlenec,
    author = 	 {Nevin Heintze and David A. McAllester},
    title = 	 {On the Cubic Bottleneck in Subtyping and Flow Analysis},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS 1997)},
    year =	 {1997},
    month =	 {June}, 
    pages =      {342--351},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }