Fixpoint alternation: arithmetic, transition systems, and the binary tree

J. C. Bradfield

doi:10.1051/ita:1999122

Fixpoint alternation: arithmetic, transition systems, and the binary tree

Research output: Contribution to journal › Article › peer-review

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 Niwiński.

Original language	English
Pages (from-to)	341-356
Number of pages	16
Journal	RAIRO: Theoretical Informatics and Applications
Volume	33
DOIs	https://doi.org/10.1051/ita:1999122
Publication status	Published - 1 Jul 1999

Keywords / Materials (for Non-textual outputs)

Fixpoints
mu-calculus
alternation
modal logic

Access to Document

10.1051/ita:1999122

http://www.rairo-ita.org/article_S0988375499001228

Cite this

@article{475162dab4da4c5eb5ca7d558c514359,

title = "Fixpoint alternation: arithmetic, transition systems, and the binary tree",

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 Niwi{\'n}ski.",

keywords = "Fixpoints, mu-calculus, alternation, modal logic",

author = "Bradfield, {J. C.}",

year = "1999",

month = jul,

day = "1",

doi = "10.1051/ita:1999122",

language = "English",

volume = "33",

pages = "341--356",

journal = "RAIRO: Theoretical Informatics and Applications",

issn = "0988-3754",

publisher = "EDP Sciences",

}

TY - JOUR

T1 - Fixpoint alternation: arithmetic, transition systems, and the binary tree

AU - Bradfield, J. C.

PY - 1999/7/1

Y1 - 1999/7/1

N2 - 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.

AB - 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.

KW - Fixpoints

KW - mu-calculus

KW - alternation

KW - modal logic

U2 - 10.1051/ita:1999122

DO - 10.1051/ita:1999122

M3 - Article

SN - 0988-3754

VL - 33

SP - 341

EP - 356

JO - RAIRO: Theoretical Informatics and Applications

JF - RAIRO: Theoretical Informatics and Applications

ER -

Fixpoint alternation: arithmetic, transition systems, and the binary tree

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this