Efficient algorithms for alternating pushdown systems : application to certificate chain discovery with threshold subjects

Dejvuth Suwimonteerabuth, Stefan Schwoon & Javier Esparza
Motivated by recent applications of pushdown systems to computer security problems, we present an efficient algorithm for the reachability problem of alternating pushdown systems. Although the algorithm is exponential, a careful analysis reveals that the exponent is usually small in typical applications. We show that the algorithm can be used to compute winning regions in pushdown games. In a second contribution, we observe that the algorithm runs in polynomial time for a certain subproblem, and...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.