On the consistency of Koomen's fair abstraction rule

J.C.M. Baeten; J.A. Bergstra; J.W. Klop

doi:10.1016/0304-3975(87)90052-1

On the consistency of Koomen's fair abstraction rule

J.C.M. Baeten, J.A. Bergstra, J.W. Klop

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

92 Citations (Scopus)

137 Downloads (Pure)

Abstract

We construct a graph model for ACPt, the algebra of communicating processes with silent steps, in which Koomen's Fair Abstraction Rule (KFAR) holds, and also versions of the Approximation Induction Principle (AIP) and the Recursive Definition & Specification Principles (RDP&RSP). We use this model to prove that in ACPT (but not in ACP!) each computably recursively definable process is finitely recursively definable.

Original language	English
Pages (from-to)	129-176
Journal	Theoretical Computer Science
Volume	51
Issue number	1-2
DOIs	https://doi.org/10.1016/0304-3975(87)90052-1
Publication status	Published - 1987

Access to Document

10.1016/0304-3975(87)90052-1

586713Final published version, 2.21 MB

Cite this

@article{87f41e9e0a8847acb9f91dd1f349955b,

title = "On the consistency of Koomen's fair abstraction rule",

abstract = "We construct a graph model for ACPt, the algebra of communicating processes with silent steps, in which Koomen's Fair Abstraction Rule (KFAR) holds, and also versions of the Approximation Induction Principle (AIP) and the Recursive Definition & Specification Principles (RDP&RSP). We use this model to prove that in ACPT (but not in ACP!) each computably recursively definable process is finitely recursively definable.",

author = "J.C.M. Baeten and J.A. Bergstra and J.W. Klop",

year = "1987",

doi = "10.1016/0304-3975(87)90052-1",

language = "English",

volume = "51",

pages = "129--176",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - On the consistency of Koomen's fair abstraction rule

AU - Baeten, J.C.M.

AU - Bergstra, J.A.

AU - Klop, J.W.

PY - 1987

Y1 - 1987

N2 - We construct a graph model for ACPt, the algebra of communicating processes with silent steps, in which Koomen's Fair Abstraction Rule (KFAR) holds, and also versions of the Approximation Induction Principle (AIP) and the Recursive Definition & Specification Principles (RDP&RSP). We use this model to prove that in ACPT (but not in ACP!) each computably recursively definable process is finitely recursively definable.

AB - We construct a graph model for ACPt, the algebra of communicating processes with silent steps, in which Koomen's Fair Abstraction Rule (KFAR) holds, and also versions of the Approximation Induction Principle (AIP) and the Recursive Definition & Specification Principles (RDP&RSP). We use this model to prove that in ACPT (but not in ACP!) each computably recursively definable process is finitely recursively definable.

U2 - 10.1016/0304-3975(87)90052-1

DO - 10.1016/0304-3975(87)90052-1

M3 - Article

SN - 0304-3975

VL - 51

SP - 129

EP - 176

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

On the consistency of Koomen's fair abstraction rule

Abstract

Access to Document

Fingerprint

Cite this