Subcubic Algorithms for Recursive State Machines

The authors show that the reachability problem for recursive state machines (or equivalently, pushdown systems), believed for long to have cubic worst-case complexity, can be solved in slightly subcubic time. All that is necessary for the new bound is a simple adaptation of a known technique. They also show that a better algorithm exists if the input machine does not have infinite recursive loops. Pushdown models of programs have numerous uses in program analysis. Recursive state machines (Alur et al. 2005), or finite-state machines that can call other finite-state machines recursively, form a popular class of such models.