Article ID Journal Published Year Pages File Type
426372 Information and Computation 2006 22 Pages PDF
Abstract

Fixpoint Logic with Chop extends the modal μ-calculus with a sequential composition operator which results in an increase in expressive power. We develop a game-theoretic characterisation of its model checking problem and use these games to show that the alternation hierarchy in this logic is strict. The structure of this result follows the lines of Arnold’s proof showing that the alternation hierarchy in the modal μ-calculus is strict over the class of binary trees.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics