Propositional dynamic logic of context-free programs and fixpoint logic with chop

摘要

This paper compares propositional dynamic logic of non-regular programs and fixpoint logic with chop. It identifies a fragment of the latter which is equi-expressive to the former. This relationship transfers several decidability and complexity results between the two logics.