Subcubic algorithms for recursive state machines
S Chaudhuri - Proceedings of the 35th annual ACM SIGPLAN …, 2008 - dl.acm.org
Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of …, 2008•dl.acm.org
We 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. We also show that a better algorithm exists if the input machine does not
have infinite recursive loops.
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. We also show that a better algorithm exists if the input machine does not
have infinite recursive loops.
We 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. We also show that a better algorithm exists if the input machine does not have infinite recursive loops.
ACM Digital Library