| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10225751 | Theoretical Computer Science | 2018 | 18 Pages |
Abstract
The main technical contribution of this work is a translation of VLDL into Ï-visibly pushdown automata of exponential size via one-way alternating jumping automata. This translation yields exponential-time algorithms for satisfiability, validity, and model checking. We also show that visibly pushdown games with VLDL winning conditions are solvable in triply-exponential time. We prove all these problems to be complete for their respective complexity classes.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alexander Weinert, Martin Zimmermann,