Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree

Julian C. Bradfield

Abstract


We provide an elementary proof of the fixpoint alternation
hierarchy in arithmetic, which in turn allows us to simplify the proof of the modal mu-calculus alternation hierarchy. We further show that the alternation hierarchy on the binary tree is strict, resolving a problem of Niwinski.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v5i53.19499
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library