On the axiomatisability of priority III: Priority strikes again

Luca Aceto, Elli Anastasiadi, Valentina Castiglioni (Corresponding author), Anna Ingólfsdóttir, Bas Luttik, Mathias Ruggaard Pedersen

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Aceto et al., proved that, over the process algebra BCCSP with the priority operator of Baeten, Bergstra and Klop, the equational theory of order-insensitive bisimilarity is not finitely based. However, it was noticed that by substituting the action prefixing operator of BCCSP with BPA's sequential composition, the infinite family of equations used to show that non-finite axiomatisability result could be proved by a finite collection of sound equations. That observation left as an open question the existence of a finite axiomatisation for order-insensitive bisimilarity over BPA with the priority operator. In this paper we provide a negative answer to this question. We prove that, in the presence of at least two actions, order-insensitive bisimilarity is not finitely based over BPA with priority.

Original languageEnglish
Pages (from-to)223-246
Number of pages24
JournalTheoretical Computer Science
Volume837
DOIs
Publication statusPublished - 12 Oct 2020

Keywords

  • Bisimilarity
  • Finite axiomatisations
  • Priority operator
  • Sequential composition

Fingerprint Dive into the research topics of 'On the axiomatisability of priority III: Priority strikes again'. Together they form a unique fingerprint.

Cite this