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 journalArticleAcademicpeer-review

2 Citations (Scopus)
11 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 languageUndefined
Pages (from-to)3035-3044
Number of pages15
JournalTheoretical computer science
Volume412
Issue number28
DOIs
Publication statusPublished - 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

Cite this

Bethke, I. (Ed.), Aceto, L., Ponse, A. (Ed.), Chen, T., Ingolfsdottir, A., Rodenburg, P. H. (Ed.), ... van de Pol, J. C. (2011). On the axiomatizability of priority II. Theoretical computer science, 412(28), 3035-3044. https://doi.org/10.1016/j.tcs.2011.02.033
Bethke, I. (Editor) ; Aceto, Luca ; Ponse, A. (Editor) ; Chen, T. ; Ingolfsdottir, Anna ; Rodenburg, P.H. (Editor) ; Luttik, Bas ; van de Pol, Jan Cornelis. / On the axiomatizability of priority II. In: Theoretical computer science. 2011 ; Vol. 412, No. 28. pp. 3035-3044.
@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 = "6",
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",

}

Bethke, I (ed.), Aceto, L, Ponse, A (ed.), Chen, T, Ingolfsdottir, A, Rodenburg, PH (ed.), Luttik, B & van de Pol, JC 2011, 'On the axiomatizability of priority II' Theoretical computer science, vol. 412, no. 28, pp. 3035-3044. https://doi.org/10.1016/j.tcs.2011.02.033

On the axiomatizability of priority II. / Bethke, I. (Editor); Aceto, Luca; Ponse, A. (Editor); Chen, T.; Ingolfsdottir, Anna; Rodenburg, P.H. (Editor); Luttik, Bas; van de Pol, Jan Cornelis.

In: Theoretical computer science, Vol. 412, No. 28, 20.06.2011, p. 3035-3044.

Research output: Contribution to journalArticleAcademicpeer-review

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

VL - 412

SP - 3035

EP - 3044

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

IS - 28

ER -

Bethke I, (ed.), Aceto L, Ponse A, (ed.), Chen T, Ingolfsdottir A, Rodenburg PH, (ed.) et al. On the axiomatizability of priority II. Theoretical computer science. 2011 Jun 20;412(28):3035-3044. https://doi.org/10.1016/j.tcs.2011.02.033