A1 Journal article (refereed)
All congruences below stability-preserving fair testing or CFFD (2020)

Valmari, Antti (2020). All congruences below stability-preserving fair testing or CFFD. Acta Informatica, 57 (3-5), 353-383. DOI: 10.1007/s00236-019-00364-4

JYU authors or editors

Publication details

All authors or editors: Valmari, Antti

Journal or series: Acta Informatica

ISSN: 0001-5903

eISSN: 1432-0525

Publication year: 2020

Volume: 57

Issue number: 3-5

Pages range: 353-383

Publisher: Springer

Publication country: Germany

Publication language: English

DOI: http://doi.org/10.1007/s00236-019-00364-4

Open Access: Open access publication published in a hybrid channel


In process algebras, a congruence is an equivalence that remains valid when any subsystem is replaced by an equivalent one. Whether or not an equivalence is a congruence depends on the set of operators used in building systems from subsystems. Numerous congruences have been found, differing from each other in fine details, major ideas, or both, and none of them is good for all situations. The world of congruences seems thus chaotic, which is unpleasant, because the notion of congruence is at the heart of process algebras. This study continues attempts to clarify the big picture by proving that in certain sub-areas, there are no other congruences than those that are already known or found in the study. First, the region below stability-preserving fair testing equivalence is surveyed using an exceptionally small set of operators. The region contains few congruences, which is in sharp contrast with an earlier result on the region below Chaos-Free Failures Divergences (CFFD) equivalence, which contains 40 well-known and not well-known congruences. Second, steps are taken towards a general theory of dealing with initial stability, which is a small but popular detail. This theory is applied to the region below CFFD.

Keywords: data processing; parallel processing

Contributing organizations

Ministry reporting: Yes

Reporting Year: 2020

Preliminary JUFO rating: 2

Last updated on 2020-09-07 at 23:11