The Complexity of CaRet + Chop
Laura Bozzelli · 2008
.We investigate the complexity of satisfiability and pushdown model-checking of the extension of the logic CaRet with the binary regular modality 'Chop'. We present automata-theoretic decision procedures based on a direct and compositional construction, which for finite (resp., infinite) words require time of exponential height equal to the nesting depth of chop modality plus one (resp., plus two). Moreover, we provide lower bounds which match the upper bounds for the case of finite words.