| Issue |
RAIRO-Theor. Inf. Appl.
Volume 33, Number 4-5, July October 1999
|
|
|---|---|---|
| Page(s) | 341 - 356 | |
| DOI | https://doi.org/10.1051/ita:1999122 | |
| Published online | 15 August 2002 | |
Fixpoint alternation: arithmetic, transition systems, and the binary tree
1
LFCS, Division of Informatics, University of Edinburgh,
Edinburgh EH9 3JZ, U.K., jcb@lfcs.ed.ac.uk.
2
BRICS, Department of Computer Science,
Aarhus University, Bygning 540, Ny Munkegade, 8000 Århus C,
Denmark.
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 Niwiński.
Mathematics Subject Classification: 68Q60 / 03D55 / 03D70 / 03D80
Key words: Fixpoints / mu-calculus / alternation / modal logic.
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.