The modal mu-calculus alternation hierarchy is strict

J.C. Bradfield

doi:10.1016/S0304-3975(97)00217-X

The modal mu-calculus alternation hierarchy is strict

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

Abstract

One of the open questions about the modal mu-calculus is whether the alternation hierarchy collapses; that is, whether all modal fixpoint properties can be expressed with only a few alternations of least and greatest fixpoints. In this paper, we resolve this question by showing that the hierarchy does not collapse.

Original language	English
Pages (from-to)	133 - 153
Number of pages	21
Journal	Theoretical Computer Science
Volume	195
Issue number	2
DOIs	https://doi.org/10.1016/S0304-3975(97)00217-X
Publication status	Published - 30 Mar 1998

Keywords / Materials (for Non-textual outputs)

Fixpoints
Expressivity
Temporal logic
mu-Calculus

Access to Document

10.1016/S0304-3975(97)00217-X

The modal mu-calculus alternation hierarchy is strict
Open archive
Final published version, 1.48 MB

http://www.sciencedirect.com/science/article/pii/S030439759700217X

Cite this

@article{27951d04bff942feaafdfa4712701f10,

title = "The modal mu-calculus alternation hierarchy is strict",

abstract = "One of the open questions about the modal mu-calculus is whether the alternation hierarchy collapses; that is, whether all modal fixpoint properties can be expressed with only a few alternations of least and greatest fixpoints. In this paper, we resolve this question by showing that the hierarchy does not collapse.",

keywords = "Fixpoints, Expressivity, Temporal logic, mu-Calculus",

author = "J.C. Bradfield",

note = "Concurrency Theory",

year = "1998",

month = mar,

day = "30",

doi = "10.1016/S0304-3975(97)00217-X",

language = "English",

volume = "195",

pages = "133 -- 153",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - The modal mu-calculus alternation hierarchy is strict

AU - Bradfield, J.C.

N1 - Concurrency Theory

PY - 1998/3/30

Y1 - 1998/3/30

N2 - One of the open questions about the modal mu-calculus is whether the alternation hierarchy collapses; that is, whether all modal fixpoint properties can be expressed with only a few alternations of least and greatest fixpoints. In this paper, we resolve this question by showing that the hierarchy does not collapse.

AB - One of the open questions about the modal mu-calculus is whether the alternation hierarchy collapses; that is, whether all modal fixpoint properties can be expressed with only a few alternations of least and greatest fixpoints. In this paper, we resolve this question by showing that the hierarchy does not collapse.

KW - Fixpoints

KW - Expressivity

KW - Temporal logic

KW - mu-Calculus

U2 - 10.1016/S0304-3975(97)00217-X

DO - 10.1016/S0304-3975(97)00217-X

M3 - Article

SN - 0304-3975

VL - 195

SP - 133

EP - 153

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -

The modal mu-calculus alternation hierarchy is strict

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this