Dirk Nowotka and Stefan Göller
A Note on an Extension of PDL
Journal of Applied Logic, 6(4):606-608, 2008.

Abstract

Recently visibly pushdown automata have been extended to so called k-phase multi-stack visibly pushdown automata (k-MVPAs). On the occasion of introducing k-MVPAs, it has been asked whether the extension of Propositional Dynamic Logic with k-MVPAs still leads to a decidable logic. This question is answered negatively here.

Keywords: PDL extension, multi-stack visibly pushdown automata

Full paper: [ps - 224 KB] [ps.gz - 112 KB] [pdf - 84 KB].