The modal mu-calculus alternation hierarchy is strict

被引：61

作者：

Bradfield, JC ^{[1
]}

机构：

[1] Univ Edinburgh, Dept Comp Sci, Lab Fdn Comp Sci, Edinburgh EH9 3JZ, Midlothian, Scotland

来源：

THEORETICAL COMPUTER SCIENCE | 1998年 / 195卷 / 02期

关键词：

mu-calculus; temporal logic; expressivity; fixpoints;

D O I：

10.1016/S0304-3975(97)00217-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 1998-Elsevier Science B.V. All rights reserved.

引用

页码：133 / 153

页数：21

共 24 条

[1]

ANDERSEN HR, 1993, PB445 DAIMI AARH U C

[2]

Arnold A, 1990, J INFORM PROCESS CYB, VEIK 26, P451

[3]

BARWISE J, 1975, ADMISSIBLE SETS STRU

[4]

BEKIC H, 1984, LECT NOTES COMPUTER, V177

[5]

Bradfield J.C., 1996, LNCS, V1119, P233

[6]

BRADFIELD JC, 1996, LECT NOTES COMPUTER, V1046, P479

[7]

BRADFIELD JC, 1991, VERIFYING TEMPORAL P

[8]

Emerson E. A., 1986, Proceedings of the Symposium on Logic in Computer Science (Cat. No.86CH2321-8), P267

[9]

EMERSON EA, 1993, LECT NOTES COMPUT SC, V697, P385, DOI DOI 10.1007/3-540-56922-7_32

[10] ON MODAL MU-CALCULUS AND BUCHI TREE AUTOMATA [J].

KAIVOLA, R .

INFORMATION PROCESSING LETTERS, 1995, 54 (01) :17-22

← 1 2 3 →