Nested Semantics over Finite Trees are Equationally Hard Invited Talk

AbstractOne of the criteria that has been put forward for studying the mathematical tractability of the behavioural equivalences in van Glabbeek's linear time- banching time spectrum is that they afford elegant, finite equational axiomatizations over fragments of process algebraic languages. A review of existing complete equational axiomatizations for many of the behavioural semantics in van Glabbeek's spectrum is offered in his encyclopedic chapter in the [Handbook of Process Algebra, Jan A. Bergstra, Alban Ponse, and Scott A. Smolka, Editors. North-Holland, Amsterdam, 2001]. The equational axiomatizations offered ibidem are over the language BCCSP, a common fragment of Milner's CCS and Hoare's CSP suitable for describing finite synchronization trees, and characterize the differences between behavioural semantics in terms of a few revealing axioms.The main omissions in this menagerie of equational axiomatizations for the behavioural semantics in van Glabbeek's spectrum are axiomatizations for 2-nested simulation semantics and possible futures semantics. The relation of 2-nested simulation was introduced by Groote and Vaandrager as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. Possible futures semantics, on the other hand, was proposed by Brookes and Rounds as far back as 1981, and is one of the nested trace equivalences introduced by Hennessy and Milner.In this talk, I shall present, amongst other results, a mathematical answer to the following natural question:Why have these semantics not been given complete axiomatizations yet, even for the language of finite synchronization trees?More precisely, I shall argue that the 2-nested simulation and the possible futures preorder and equivalence do not admit a finite (in)equational axiomatization over the language BCCSP. I then generalize these negative results to show that, for n⩾2, none of the n-nested simulation or trace preorders and equivalences defined by Groote and Vaandrager, and Hennessy and Milner, respectively, afford finite equational axiomatizations over the language BCCSP.Interestingly, the intersection of all of the n-nested simulation or trace equivalences or preorders over image-finite labelled transition systems, and therefore over the language BCCSP, is bisimulation equivalence. Hennessy and Milner proved that bisimulation equivalence is axiomatized over the language BCCSP by means of four classic equations. It follows that this fundamental behavioural equivalence, albeit finitely based over BCCSP, is the limit of sequences of relations that do not afford finite equational axiomatizations themselves. Thus “finite axiomatizability” is an example from process theory of a “discontinuous” property of a behavioural equivalence—i.e., of a property that “appears at the limit”, but is not afforded by its finite approximations. This talk is based upon joint work with Wan Fokkink (CWI), Rob van Glabbeek (INRIA, Sophia Antipolis) and Anna Ingólfsdóttir (BRICS, Aalborg University)