On the axiomatizability of priority II

I. Bethke; Luca Aceto; A. Ponse; T. Chen; Anna Ingolfsdottir; P.H. Rodenburg; Bas Luttik; Jan Cornelis van de Pol

doi:10.1016/j.tcs.2011.02.033

On the axiomatizability of priority II

I. Bethke (Editor), Luca Aceto, A. Ponse (Editor), T. Chen, Anna Ingolfsdottir, P.H. Rodenburg (Editor), Bas Luttik, Jan Cornelis van de Pol

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

5 Citations (Scopus)

39 Downloads (Pure)

Abstract

This paper contributes to the study of the equational theory of the priority operator of Baeten, Bergstra and Klop in the setting of the process algebra BCCSP. It is shown that, in the presence of at least two actions, the collection of process equations over BCCSP with the priority operator that are valid modulo bisimilarity, irrespective of the chosen priority order over actions, is not finitely based. This holds true even if one restricts oneself to the collection of valid process equations that do not contain occurrences of process variables.

Original language	Undefined
Pages (from-to)	3035-3044
Number of pages	15
Journal	Theoretical computer science
Volume	412
Issue number	28
DOIs	https://doi.org/10.1016/j.tcs.2011.02.033
Publication status	Published - 20 Jun 2011

Keywords

Priority operator
EWI-19749
CR-F.4.1
CR-I.1
FMT-PA: PROCESS ALGEBRAS
Non-finitely based algebras
IR-76410
Bisimilarity
Equational logic
Process Algebra
METIS-278703

Access to Document

10.1016/j.tcs.2011.02.033

prioII

http://eprints.eemcs.utwente.nl/secure2/19749/02/TCS8256.pdf

Cite this

@article{dfdb00a434b54ee590541b6bea8f997a,

title = "On the axiomatizability of priority II",

abstract = "This paper contributes to the study of the equational theory of the priority operator of Baeten, Bergstra and Klop in the setting of the process algebra BCCSP. It is shown that, in the presence of at least two actions, the collection of process equations over BCCSP with the priority operator that are valid modulo bisimilarity, irrespective of the chosen priority order over actions, is not finitely based. This holds true even if one restricts oneself to the collection of valid process equations that do not contain occurrences of process variables.",

keywords = "Priority operator, EWI-19749, CR-F.4.1, CR-I.1, FMT-PA: PROCESS ALGEBRAS, Non-finitely based algebras, IR-76410, Bisimilarity, Equational logic, Process Algebra, METIS-278703",

author = "I. Bethke and Luca Aceto and A. Ponse and T. Chen and Anna Ingolfsdottir and P.H. Rodenburg and Bas Luttik and {van de Pol}, {Jan Cornelis}",

note = "10.1016/j.tcs.2011.02.033 ",

year = "2011",

month = jun,

day = "20",

doi = "10.1016/j.tcs.2011.02.033",

language = "Undefined",

volume = "412",

pages = "3035--3044",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier",

number = "28",

}

TY - JOUR

T1 - On the axiomatizability of priority II

AU - Aceto, Luca

AU - Chen, T.

AU - Ingolfsdottir, Anna

AU - Luttik, Bas

AU - van de Pol, Jan Cornelis

A2 - Bethke, I.

A2 - Ponse, A.

A2 - Rodenburg, P.H.

N1 - 10.1016/j.tcs.2011.02.033

PY - 2011/6/20

Y1 - 2011/6/20

N2 - This paper contributes to the study of the equational theory of the priority operator of Baeten, Bergstra and Klop in the setting of the process algebra BCCSP. It is shown that, in the presence of at least two actions, the collection of process equations over BCCSP with the priority operator that are valid modulo bisimilarity, irrespective of the chosen priority order over actions, is not finitely based. This holds true even if one restricts oneself to the collection of valid process equations that do not contain occurrences of process variables.

AB - This paper contributes to the study of the equational theory of the priority operator of Baeten, Bergstra and Klop in the setting of the process algebra BCCSP. It is shown that, in the presence of at least two actions, the collection of process equations over BCCSP with the priority operator that are valid modulo bisimilarity, irrespective of the chosen priority order over actions, is not finitely based. This holds true even if one restricts oneself to the collection of valid process equations that do not contain occurrences of process variables.

KW - Priority operator

KW - EWI-19749

KW - CR-F.4.1

KW - CR-I.1

KW - FMT-PA: PROCESS ALGEBRAS

KW - Non-finitely based algebras

KW - IR-76410

KW - Bisimilarity

KW - Equational logic

KW - Process Algebra

KW - METIS-278703

U2 - 10.1016/j.tcs.2011.02.033

DO - 10.1016/j.tcs.2011.02.033

M3 - Article

SN - 0304-3975

VL - 412

SP - 3035

EP - 3044

JO - Theoretical computer science

JF - Theoretical computer science

IS - 28

ER -