The Complexity of Games on Higher Order Pushdown Automata

Simple item page
dc.creatorCachat, Thierry
dc.creatorWalukiewicz, Igor
dc.date2007-05-02
dc.date.accessioned2026-07-07T07:59:08Z
dc.date.available2026-07-07T07:59:08Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0705.0262
dc.identifierhttp://arxiv.org/abs/0705.0262
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/128256
dc.subjectComputer Science and Game Theory
dc.titleThe Complexity of Games on Higher Order Pushdown Automata
dc.typetext

Files

Collections

arXiv