arXiv (Cornell University) · 2007 · 26 citations · 2 references
ComputingComputer ScienceMathematicsAlgorithmsGame TheoryTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesPushdown AutomataTime ComplexityGraph GamesHigher-order Pushdown AutomataPushdown Automata ComplexityPushdown Automata Decision ProblemsPushdown Automata ReachabilityPushdown GamesReachabilityReachability Games
We prove an n-EXPTIME lower bound for the problem of deciding the winner in a reachability game on Higher Order Pushdown Automata (HPDA) of level n. This bound matches the known upper bound for parity games on HPDA. As a consequence the mu-calculus model checking over graphs given by n-HPDA is n-EXPTIME complete.
2
Pushdown Processes: Games and Model Checking
Igor Walukiewicz · BRICS Report Series · 1996 · 93 citations · Full text
Iterated stack automata and complexity classes
Joost Engelfriet · Information and Computation · 1991 · 55 citations