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

Authors

  • Julian C. Bradfield

DOI:

https://doi.org/10.7146/brics.v5i53.19499

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.

Downloads

Published

1998-12-23

How to Cite

Bradfield, J. C. (1998). Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree. BRICS Report Series, 5(53). https://doi.org/10.7146/brics.v5i53.19499