Distributive Laws
and Decidable Properties of SOS Specifications∗
Bartek Klin

Beata Nachyła

University of Warsaw

Institute of Computer Science, Polish Academy of Sciences

klin@mimuw.edu.pl

beatanachyla@gmail.com

Some formats of well-behaved operational specifications, correspond to natural transformations of
certain types (for example, GSOS and coGSOS laws). These transformations have a common generalization: distributive laws of monads over comonads. We prove that this elegant theoretical generalization has limited practical benefits: it does not translate to any concrete rule format that would be
complete for specifications that contain both GSOS and coGSOS rules. This is shown for the case of
labeled transition systems and deterministic stream systems.

1

Introduction

Distributive laws (see [14, 8] for more information) are an abstract approach to several kinds of wellbehaved operational specifications. For example, for a fixed set A of labels, a family of inference rules
a

a

x −→ x′

y −→ y′
a

x ⊗ y −→ x′ ⊗ y′

(for a ∈ A)

that define synchronous composition over labeled transition systems (LTSs), can be presented as a natural
transformation λ : ΣB =⇒ BΣ (a distributive law of Σ over B), where ΣX = X × X and BX = Pω (A × X )
are functors on the category Set of sets and functions. Similarly, a family of rules
a

b

x −→ x′

y −→ y′
a

x ⋊ y −→ y′ ⋊ x′

(for a, b ∈ A)

that define an alternating composition operator ⋊ on infinite streams of labels, can be understood as a
transformation λ : ΣB =⇒ BΣ where ΣX = X × X again, and BX = A × X .
Typically Σ is a polynomial functor arising from an algebraic signature. Specifications that give rise
to distributive laws of Σ over B enjoy several desirable properties: they induce a B-coalgebra (e.g. an
LTS) on the carrier of the initial Σ-algebra (the algebra of Σ-terms) so that bisimilarity is a congruence,
and they provide an interpretation of the signature on the final B-coalgebra (provided that it exists).
These desirable properties extend to other, more expressive types of laws, including:
(a) GSOS laws ρ : Σ(B × Id) =⇒ BΣ∗ , where Σ∗ is the free monad over Σ (see Section 2.1),
(b) coGSOS laws ρ : ΣB∞ =⇒ B(Id + Σ), where B∞ is the cofree comonad over B (see Section 2.2),
(c) distributive laws of monads over comonads, i.e., natural transformations λ : Σ∗ B∞ =⇒ B∞ Σ∗ subject to a few axioms. (In this paper we only consider distributive laws of free monads over cofree
comonads, see Section 2.4.)
∗ This

work was supported by the Polish National Science Centre (NCN) grant 2012/07/E/ST6/03026.

J. Borgström, S. Crafa (Eds.): Combined Workshop on Expressiveness in
Concurrency and Structural Operational Semantics (EXPRESS/SOS 2014)
EPTCS 160, 2014, pp. 79–93, doi:10.4204/EPTCS.160.8

c B. Klin & B. Nachyła
This work is licensed under the
Creative Commons Attribution License.

Distributive Laws and Decidable Properties of SOS

80

GSOS and coGSOS laws are incomparable, i.e., there are specifications that conform to one type but not
the other, and distributive laws of monads over comonads are a common generalization of both. From
now on, for brevity, we shall call them simply distributive laws.
For standard examples of B, GSOS and coGSOS laws correspond to rule formats, i.e., syntactic restrictions on the form of inference rules that are allowed in a specification for it to define a corresponding
type of law. For BX = Pω (A × X ), where Pω is the finite powerset functor, it was observed in [14] that
GSOS laws correspond to previously known GSOS [2] specifications (hence the name of the law type),
that allow rules such as:
a1,1

x1 −→ y1,1

a1,2

x1 −→ y1,2

ai, j

···

xi −→ yi, j

···

bi, j

xi 6−→

···

b

f(x1 , . . . , xk ) −→ t
where variables xi can be tested for the presence and/or absence of transitions labeled with different
labels, and the resulting transition can go to an arbitrary term t built over the variables xi and yi, j . On the
other hand, coGSOS laws for the same functor B are induced by safe ntree [5, 14] specifications, where
additionally lookahead is allowed, i.e., variables that are targets of premise transitions can be further
tested for other transitions as in the rule:
a

b

x −→ y −→ z
c

f(x) −→ g(z)
On the other hand, coGSOS is restricted in that the target term t in the conclusion must be either a
variable or a flat term built of a single operation symbol and variables.
Both GSOS and coGSOS laws, are generalized by distributive laws. In fact, desired properties of
systems induced by GSOS and coGSOS laws were proved in [14] by showing first that these laws induce
distributive laws, and then proving those properties for the latter, more general laws. This is tantalizing,
as it suggests that for standard functors B one could find new, more expressive syntactic rule formats
that would correspond to distributive laws and hence guarantee good properties of specifications. The
problem of finding such a format was left open in [14] and mentioned as still open in later works [1, 8].
The purpose of this paper is to suggest a negative answer to that problem. Specifically, we claim that
there is no rule format that would adequately recognize those specifications that induce distributive laws
of monads over comonads, within a class of specifications that extends both GSOS and coGSOS.
This claim is rather vague, and we must make it precise before we attempt to prove it. First of all,
there is no hope to prove it for all monads and comonads; clearly, for some trivial monads and comonads
all distributive laws are easily enumerated, and even for some nontrivial comonads a complete description
of distributive laws is known [7]. Therefore in this paper we shall consider laws λ : Σ∗ B∞ → B∞ Σ∗ for Σ∗
the free monad over a polynomial functor Σ, and B∞ the cofree comonad over BX = A × X , pertaining to
stream systems, or BX = Pω (A × X ), pertaining to labeled transition systems. Hopefully it shall be clear
how our arguments for the lack of expressive formats for these two behaviour functors, might extend to
other standard functors used to model transition systems coalgebraically.
To make our claim precise, the first question we need to answer is: what is a format? In positive
results about GSOS and coGSOS laws mentioned above, the answer was easy: one simply formulated
some “syntactic forms” of rules and provided ways of defining laws from sets of rules that conformed to
them. Now that we want a negative result, we need to quantify over all “syntactic forms”, so we need to
understand what a syntactic form is in general. We opt for a general and permissive answer: a format is a
decidable property of specifications. Indeed, no matter what a “format” may be, it should be effectively
checkable whether a specification conforms to it.

B. Klin & B. Nachyła

81

This leads to another question: what is a specification? Some definitions of this term would immediately invalidate our claim; for example, if we say that “a specification is either a GSOS specification or
a coGSOS specification”, then every specification induces a distributive law as described already in [14]
and the problem is trivially decidable. However, we are interested in more permissive notions of specification that would allow a more substantial combination of GSOS and coGSOS features. We therefore
focus on mixed-GSOS specifications, where every rule is either a GSOS or a coGSOS rule.
Note that there are other interesting notions of specification where the claim becomes false. For
example, as proved in [13], in the context of LTSs one may consider so-called (positive) tyft/tyxt [4]
specifications, and guarantee the existence of a distributive law for every specification. However, tyft/tyxt
specifications extend neither full GSOS nor coGSOS, so this does not match the abstract observation that
distributive laws generalize both GSOS laws and coGSOS laws.
There is still one vague point in our claim: what does it mean for a specification to induce a distributive law? In positive results about GSOS and coGSOS specifications [8, 14], one simply provides
particular ways of inducing distributive laws from specifications that look so natural that everybody is
convinced. Here, to show undecidability, we shall need to prove that some instances do not induce
distributive laws, so we need to quantify over all possible “ways of inducing laws”, a vague notion itself.
We approach this problem by observing that every mixed-GSOS specification induces, in a very
natural way, a natural transformation ρ : ΣB∞ =⇒ BΣ∗ which we call a biGSOS law. Then we define
(Definition 13) what it means for a distributive law λ to extend a biGSOS law ρ ; essentially, λ must
restrict to ρ when composed with obvious inclusions and projections. Our claim then becomes:
Claim. It is undecidable whether a given mixed-GSOS specification extends to a unique distributive law.
One may worry whether our insistence on a unique extension is not overly restrictive. Indeed, perhaps
sometimes a specification may extend to several distributive laws, but one of these laws is somehow
better than the other ones, for example (in the LTS setting) the least one, or canonical in some other way?
However, as will be evident from our proofs, this is not a problem: all our instances of specifications
will either extend to one distributive law or to none at all, therefore no matter what notion of “canonical
extension” one may come up with, the problem remains undecidable.
We prove undecidability by reduction from the halting problem of a variant of queue machines defined in Section 4. Then, in Section 5, we prove the Claim for the case of stream systems (Theorem 24),
and in Section 6 we explain how the proof is adapted to the case of LTSs (Theorem 29).

2

Preliminaries

The reader should be familiar with notions of category theory such as functors and natural transformations, see e.g. [11]. All functors we consider are endofunctors on the category of sets and functions.

2.1 Algebras and monads
An algebra for a functor Σ is a set X (the carrier) together with a function g : ΣX → X (the structure).
An algebra morphism from g : ΣX → X to h : ΣY → Y is a function f : X → Y such that f ◦ g = h ◦ Σ f .
Algebras for Σ and their morphisms form a category. Of particular interest in this category are initial
objects, i.e., initial Σ-algebras.
Assume that, for any set X , an initial algebra for the functor Σ(−) + X exists, denote its carrier Σ∗ X
and its structure by:
ΣΣ∗ X

ψX

/ Σ∗ X o ηX

X.

Distributive Laws and Decidable Properties of SOS

82

Then Σ∗ , defined on functions using initiality, becomes a functor and ψ : ΣΣ∗ =⇒ Σ∗ and η : Id =⇒ Σ∗
are natural transformations. Moreover, Σ∗ is a monad, i.e., it is equipped with a natural transformation
µ : Σ∗ Σ∗ =⇒ Σ∗ such that the following diagrams commute:
Σ∗ η

∗
+3 Σ∗ Σ∗ ks η Σ Σ∗
②
❊❊❊❊
②②②②②
❊❊❊❊
❊❊❊❊ µ ②②②②②②②
❊  ②②②
∗

Σ∗ ❊❊❊

Σ∗ Σ∗ Σ∗

Σ∗ µ

+3 Σ∗ Σ∗
µ

µ Σ∗

Σ

(1)





Σ∗ Σ∗

+3 Σ∗ .

µ

Σ∗ is called the free monad over Σ. Another relevant transformation is ι : Σ =⇒ Σ∗ defined by ι = ψ ◦Ση ;
it further satisfies the equation ψ = µ ◦ ι Σ∗ .
Example 1 Any algebraic signature
(qi )i∈I , where each qi is an operation symbol of arity ni ∈ N, gives
`
rise to an endofunctor ΣX = i∈I X ni . Then Σ-algebras are algebras for the signature in the sense of
universal algebra, and Σ-algebra morphisms are exactly algebra homomorphisms. Moreover, Σ∗ X is the
set of terms over the signature with variables taken from X , η interprets variables as terms, ψ and µ glue
together terms built of terms, and ι interprets terms built of single operation symbols as terms.

2.2 Coalgebras and comonads
The following development is dual to the one for algebras and monads; we include it for completeness
and to introduce some basic terminology and notation. For more information about coalgebras, see [12].
A coalgebra for a functor B is a set X (the carrier) together with a function g : X → BX (the structure).
A coalgebra morphism from g : X → BX to h : Y → BY is a function f : X → Y such that h ◦ f = B f ◦ g.
Coalgebras for B and their morphisms form a category.
Assume that, for any set X , a final coalgebra for the functor B(−) × X exists, denote its carrier B∞ X
and its structure by:
θX

BB∞ X o

B∞ X

εX

/ X.

Then B∞ , defined on functions using finality, becomes a functor and θ : B∞ =⇒ BB∞ and ε : B∞ =⇒ Id
are natural transformations. Moreover, B∞ is a comonad, i.e., it is equipped with a natural transformation
δ : B∞ =⇒ B∞ B∞ such that diagrams dual to (1) commute. B∞ is called the cofree comonad over B.
Another relevant transformation is π : B∞ =⇒ B defined by π = Bε ◦ θ ; it further satisfies the equation
θ = π B∞ ◦ δ .
Example 2 Let BX = A × X , for a fixed set A of labels. B-coalgebras are stream systems, i.e., sets X
(of states) equipped with functions to A and to X again; the intuition is that a state produces a label and
transforms into another state. The cofree comonad over B is given by B∞ X = (X × A)ω ; we will depict
elements of B∞ X as streams of labeled transitions:
0
3
1
2
B∞ X ∋ σ = x0 −→
x1 −→
x2 −→
x3 −→
···

a

a

a

a

with xi ∈ X and ai ∈ A. For any n ∈ N, by σ (n) ∈ B∞ X denote the n-th tail of σ , i.e., the substream of σ
that starts at xn . Natural transformations explained above are then given by:

εX (σ ) = x0

θX (σ ) = a0 , σ (1) )
a

a

a

0
1
2
δX (σ ) = σ −→
σ (1) −→
σ (2) −→
σ (3) −→ · · · )

πX (σ ) = (a0 , x1 )

B. Klin & B. Nachyła

83

One may look at elements of B∞ X as streams of labels “colored” with elements of X ; elements of B∞ B∞ X
are then streams colored by streams, and δX (σ ) is the stream that arises from σ by coloring each node
with the substream of σ that starts in it.
Example 3 Let Pω denote the finite powerset functor, and let BX = Pω (A × X ), for a fixed set A
of labels. B-coalgebras are (finitely branching) labeled transition systems. The cofree comonad over
B is a functor B∞ that maps a set X to the set of finitely branching, but possibly infinitely deep trees,
edge-labeled with elements of A and node-colored by elements of X , quotiented by a version of strong
bisimilarity that takes into account both edge labels and node colors.
Natural transformations listed above are defined by analogy to Example 2. For a tree T ∈ B∞ X :
• εX (T) ∈ X is the color of the root node of T,
• δX (T) ∈ B∞ B∞ X arises from T by coloring every node with the subtree rooted in it,
• θX (T) ∈ BB∞ X is the set of immediate subtrees of the root together with labels of the edges that
lead to these subtrees,
• πX (T) ∈ BX is similar, but with the immediate subtrees replaced by the colors of their roots.
A little care is needed to show that components of these transformations are well-defined on bisimilarity
classes of trees. For example, if T1 and T2 are related by a bisimulation, then δX (T1 ) and δX (T2 ) also are,
as bisimilar nodes get assigned the same colors (here colors are bisimilarity classes of trees).

2.3 GSOS and coGSOS laws
Algebras, coalgebras, monads and comonads can be combined in distributive laws of various kinds. We
only recall a few basic definitions and examples here; for a more comprehensive treatment see [8].
For any functor B, denote B̃ = Id × B.
Definition 4 Given endofunctors Σ and B such that the free monad Σ∗ over Σ exists, a GSOS law is a
natural transformation ρ : ΣB̃ =⇒ BΣ∗ .
Example 5 Consider BX = A × X , and let ΣX = X × X arise from a signature with a single binary
function symbol zip. A family of rules
a

b

x −→ x′

y −→ y′
a

zip(x, y) −→ zip(y, x′ )

(for a, b ∈ A)

together defines a GSOS law by:

ρX (zip((x, (a, x′ )), (y, (b, y′ )))) = (a, zip(y, x′ ))
for any x, x′ , y, y′ ∈ X and a, b ∈ A.
Dually, for any functor Σ, denote Σ̄ = Id + Σ.
Definition 6 Given endofunctors Σ and B such that the cofree comonad B∞ over B exists, a coGSOS law
is a natural transformation ρ : ΣB∞ =⇒ BΣ̄.

Distributive Laws and Decidable Properties of SOS

84

Example 7 Consider BX = A × X , and let ΣX = X arise from a signature with a single unary function
symbol q. The family of rules (that define a unary operation that drops every second label from a given
stream):
a

a

1
2
x −→
x′ −→
x′′

(for a1 , a2 ∈ A)

a

2
q(x) −→
q(x′′ )

together defines a coGSOS law by:
a

a

a

1
2
3
x′ −→
x′′ −→
· · · )) = (a2 , q(x′′ ))
ρX (q(x −→

for any x, x′ , x′′ , . . . ∈ X and a1 , a2 , a3 , . . . ∈ A.
Example 8 Now, consider the LTS behaviour functor BX = Pω (A × X ), and let ΣX = X as in Example 7. The rules:
a

a

a

1
x −→
x′ 6−→

1
2
x −→
x′ −→
x′′

a

2
q(x) −→
q(x′′ )

(for a1 , a2 ∈ A)

a

1
q(x) −→
q(x)

define a coGSOS law ρ : ΣB∞ =⇒ BΣ̄, where ρX (q(T)) is the set of pairs (a, q(x)) such that T has (1) a
two-step path from the root to a node colored by x with the second step labeled by a, or (2) a single step,
labeled with a, to a leaf (i.e. a node without successors), and the root of T is colored by x.

2.4 Distributive laws
In [14] it was noticed that both GSOS and coGSOS laws are generalized by distributive laws of monads
over comonads; in this paper we call them simply distributive laws.
Definition 9 A distributive law of a monad (Σ∗ , η , µ ) over a comonad (B∞ , ε , δ ) is a natural transformation λ : Σ∗ B∞ =⇒ B∞ Σ∗ subject to the following four axioms:
B∞

B∞ η

η B∞



(i)

Σ∗ B ∞

λ

!

µ B∞

(iii)

∗
+3 Σ∗ B∞ Σ∗ λ Σ 3+ B∞ Σ∗ Σ∗

B∞ µ

Σ∗ δ



+3 B∞ Σ∗
δ Σ∗

(iv)



Σ∗ B ∞ B ∞

Σ∗



λ

Σ∗ B ∞

ε Σ∗

%-

Σ∗ λ



+3 B∞ Σ∗
(ii)

Σ∗ ε

Σ∗ Σ∗ B ∞

λ B∞

+3 B∞ Σ∗ B∞



B∞ λ

+3 B∞ B∞ Σ∗

`
Example 10 Consider BX = A × X as in Example 2, and a functor ΣX = q∈Q X ∼
= Q × X arising as in
Example 1 from an algebraic signature consisting of a set of unary operation symbols Q = {q1 , . . . , qk }.
Then B∞ X = (X × A)ω and Σ∗ X = Q∗ × X ; for t ∈ Q∗ , we shall write t(x) instead of (t, x) ∈ Σ∗ X , and
simply x instead of ε (x), for the empty string ε ∈ Q∗ .
For a distributive law λ : Σ∗ B∞ =⇒ B∞ Σ∗ , the naturality condition means that if
a

a

a

b

b

b

a

a

a

c

c

c

0
0
1
1
2
2
λX (t(x0 −→
τ1 −→
τ2 −→
x1 −→
x2 −→
···
· · · )) = τ0 −→
0
0
1
2
1
2
λY (t(y0 −→
γ1 −→
γ2 −→
y1 −→
y2 −→
· · · )) = γ0 −→
···

B. Klin & B. Nachyła

85

then for all i ∈ N one has bi = ci , and γi ∈ Σ∗Y arises from τi ∈ Σ∗ X by substituting each x j by the
corresponding y j . Informally, the value of λX on t(σ ) essentially depends only on the term t and on the
labels in the stream σ , and the colors x j in σ are merely rearranged into terms τk independently from
their identity or structure. This also implies that all elements from X present in λX (t(σ )) must have been
present in σ .
Further, the four axioms of Definition 9 amount to:
a

a

a

a

a

a

0
0
1
2
1
2
(i) λX (x0 −→
x1 −→
x2 −→
· · · ) = x0 −→
x1 −→
x2 −→
···,

a

a

a

a

a

a

b

b

b

0
1
2
0
1
2
x1 −→
x2 −→
· · · )) = τ0 −→
···
τ1 −→
τ2 −→
(ii) if λX (t(x0 −→
0
1
2
(iii) if λX (s(x0 −→
x1 −→
x2 −→
· · · ))

b0

b1

b

b

b

c0

c1

c2

b

b

b

then τ0 = t(x0 ),

0
1
2
= τ0 −→
···
τ1 −→
τ2 −→

b2

and

λΣ∗ X (t(τ0 −→ τ1 −→ τ2 −→ · · · )) = γ0 −→ γ1 −→ γ2 −→ · · · then
a0
c0
a1
a2
c1
c2
x1 −→
x2 −→
· · · )) = γ0 −→
··· .
λX (ts(x0 −→
γ1 −→
γ2 −→
Informally, λ is defined compositionally with respect to Σ-terms.
a

a

a

0
1
2
(iv) if λX (t(x0 −→
x1 −→
x2 −→
· · · ))

0
1
2
= τ0 −→
···
τ1 −→
τ2 −→

then for every i ∈ N,

bi+1

λX (τi ) = τi −→ τi+1 −→ · · · , where τi ∈ Σ∗ B∞ X arises from τi ∈ Σ∗ X by replacing every x j with
the stream starting at it. Informally, λX is defined “decompositionally” with respect to streams.
bi

3

BiGSOS laws and mixed-GSOS specifications

In [14] it was proved that (1) every GSOS law induces a distributive law and (2) every coGSOS law
induces a distributive law. The two ways of inducing distributive laws explained there are both natural
and convincing, but formally different. We wish to study the problem of inducing distributive laws
from specifications that would generalize both GSOS and coGSOS laws, so we need to have a general
understanding of what it means to induce a distributive law. To this end, we consider the following
simple generalization of GSOS and coGSOS:
Definition 11 Given endofunctors Σ and B such that the free monad Σ∗ over Σ exists and the cofree
comonad B∞ over B exist, a biGSOS law is a natural transformation ρ : ΣB∞ =⇒ BΣ∗ .
GSOS and coGSOS laws give rise to biGSOS laws by composing with injections or projections:
ΣB∞

Σhε ,π i

+3 ΣB̃

ρ′

+3 BΣ∗ ,

ΣB∞

ρ ′′

+3 BΣ̄

B[η ,ι ]

+3 BΣ∗ .

where ρ ′ is a GSOS law and ρ ′′ is a coGSOS law. (Note that hε , π i : B∞ =⇒ B̃ and [η , ι ] : Σ̄ =⇒ Σ∗ are
natural transformations.) As a result, biGSOS laws generalize both GSOS and coGSOS laws. However,
they offer much more flexibility. In particular, for the case of stream systems and LTSs, we consider:
Definition 12 A stream (or LTS) specification is mixed-GSOS if every rule in it is either a GSOS rule or
a coGSOS rule, and moreover, for any operator f, rules that define f (i.e., those that have f on the left
side of the conclusion) are either all GSOS or all coGSOS.
Note that we allow coGSOS-defined operations in conclusions of GSOS rules (and vice versa), so
that e.g. the specification in Example 14 below is mixed-GSOS.
One could also define mixed GSOS more abstractly, by partitioning the signature into two disjoint
subsignatures, Σ = ΣGSOS + ΣcoGSOS , and requesting two natural transformations:

ρGSOS : ΣGSOS B̃ =⇒ BΣ∗

ρcoGSOS : ΣcoGSOS B∞ =⇒ BΣ̄,

Distributive Laws and Decidable Properties of SOS

86

one responsible for the GSOS, the other one the coGSOS part of the specification. It is then clear how
a mixed-GSOS specification induces a biGSOS law, by comparing ρGSOS and ρcoGSOS composed with
suitable injections and projections. Note that biGSOS laws allow still more flexibility than allowed by
mixed-GSOS, as they allow rules that combine complex conclusion terms as in GSOS, with lookahead
as in coGSOS.
It may not be evident what it means for a biGSOS law to induce a distributive law, but it is clear how a
given distributive law may extend a biGSOS law, by composing with relevant injections and projections:
Definition 13 A distributive law λ : Σ∗ B∞ =⇒ B∞ Σ∗ extends a biGSOS law ρ : ΣB∞ =⇒ BΣ∗ if the
following diagram commutes:
ρ

ΣB∞

+3 BΣ∗
KS

ι B∞

π Σ∗



Σ∗ B ∞

λ

(2)

+3 B∞ Σ∗

In other words, λ extends ρ if it equals ρ when its arguments are restricted to Σ-terms of depth 1 and
results projected to B-behaviours of depth 1.
As the following examples show, not every biGSOS law extends to a distributive law, and those that
do may not extend uniquely.
Example 14 For BX = A × X with a chosen element $ ∈ A, consider syntax with one constant C and one
unary operation q, so that ΣX = 1 + X and B∞ X = (X × A)ω . Consider ρ : ΣB∞ =⇒ BΣ∗ defined by rules:
b

a

x −→ x′ −→ x′′
b

$

q(x) −→ q(x′′ )

C −→ q(C)

(for a, b ∈ A)

Consider any distributive law λ : Σ∗ B∞ =⇒ B∞ Σ∗ , and present λ0 (C) as:

λ0 (C)

=

a

a

a

0
1
2
C −→
···
τ1 −→
τ2 −→

∈

B ∞ Σ∗ 0

(3)

with each τi ∈ Σ∗ 0 and ai ∈ A.
If λ extends ρ then, by (2) applied to C ∈ ΣB∞ 0, we have a0 = $ and τ1 = q(C). Since λ is a
distributive law, by axioms (ii) and (iv) of Definition 9 as explained in Example 10, from (3) we get

λ0 (q(C))

a

a

1
2
q(C) −→
···
τ2 −→

=

(4)

Now, by (2) applied to q(λ0 (C)) ∈ ΣB∞ Σ∗ 0, we have:
a

a

a

a

0
1
2
1
· · · )) = q(C) −→
q(τ2 ) −→ · · ·
λΣ∗ 0 (q(λ0 (C))) = λΣ∗ 0 (q(C −→
τ1 −→
τ2 −→

(5)

(only the first step of the stream on the right is determined this way). By axiom (iii) of Definition 9 as
explained in Example 10, the stream (5) is equal to (4) (or, more precisely, it is mapped to it by pointwise
application of µ0 ); as a result, τ2 = q(τ2 ). However, there is no such term τ2 and, as a consequence, a
distributive law λ that extends ρ does not exist.
Example 15 Consider the previous example with the rightmost rule slightly modified to:
b

a

x −→ x′ −→ x′′
b

q(x) −→ x′′

(for a, b ∈ A)

B. Klin & B. Nachyła

87

If, say, A = {$, e}, then the corresponding ρ can be extended e.g. to distributive laws λ , λ ′ such that:
$

$

$

$

$

e

e

e

λ0 (C) = C −→ q(C) −→ q(C) −→ q(C) −→ · · ·
λ0′ (C) = C −→ q(C) −→ q(C) −→ q(C) −→ · · ·
This example shows that distinct distributive laws λ , λ ′ : Σ∗ B∞ =⇒ B∞ Σ∗ can sometimes be equalized
by composing with both ι B∞ : ΣB∞ =⇒ Σ∗ B∞ and π Σ∗ : B∞ Σ∗ =⇒ BΣ∗ (see Definition 13). However,
distinct distributive laws cannot be equalized by composing with only one of these transformations:
Lemma 16 For any distributive laws λ , λ ′ : Σ∗ B∞ =⇒ B∞ Σ∗ :
and
(b) if π Σ∗ ◦ λ = π Σ∗ ◦ λ ′ then λ = λ ′ .
(a) if λ ◦ ι B∞ = λ ′ ◦ ι B∞ then λ = λ ′ ,
It makes sense to say that a biGSOS law ρ induces a distributive law if there is a unique distributive
law that extends ρ . This is consistent with known results about GSOS and coGSOS laws, which, as has
been understood since [14], induce distributive laws:
Theorem 17 For every GSOS law ρ : ΣB̃ =⇒ BΣ∗ , and for every coGSOS law ρ : ΣB∞ =⇒ BΣ̄ there is
a unique distributive law λ : Σ∗ B∞ =⇒ B∞ Σ∗ that extends the associated biGSOS law.
Proof sketch. For the existence of λ , constructions of distributive laws from GSOS and coGSOS laws
were given already in [14], and later explained more elegantly in [10]. It is not difficult to prove that
those constructions extend the respective GSOS and coGSOS laws in the sense of Definition 13.
2
For the uniqueness of λ , Lemma 16 is used.

4

Queue machines

We shall prove that it is undecidable whether a given biGSOS law uniquely extends to a distributive law.
To this end, we use the undecidability of the halting problem of queue machines.
A queue machine (QM) is a deterministic finite automaton additionally equipped with a first-in-firstout queue to store letters. A machine can read letters off the queue, and depending on their contents
change their state while adding new letters to the queue. Under the classical definition [9], a QM in each
transition (a) removes exactly one letter from the queue and (b) adds some (possibly zero) letters to it.
For our purposes, it will be convenient to consider instead a variant of QMs that, in each step: (a) remove
zero, one or two letters from the queue, and (b) add exactly one letter to it. Formally:
Definition 18 A queue machine (QM) M = (Q, A, $, q1 , δ0 , δ1 , δ2 ) consists of a finite set Q of states, a
finite alphabet A with a chosen symbol $ ∈ A, a starting state q1 ∈ Q, and three partial transition functions:

δ0 : Q ⇀ Q × A

δ1 : Q × A ⇀ Q × A

δ2 : Q × A × A ⇀ Q × A

that are disjointly defined and jointly total, i.e., such that for each q ∈ Q and a, b ∈ A, exactly one of
δ0 (q), δ1 (q, a) or δ2 (q, a, b) is defined. A configuration of M is a pair (q, w) ∈ Q × A∗ ; the machine
induces a transition function  on the set of configurations by:
(q, w)

 (q′ , wc)

if

(q, aw)

 (q′ , wc)

if

′

if

(q, abw)

 (q , wc)

δ0 (q) = (q′ , c)
δ0 (q) undefined and δ1 (q, a) = (q′ , c)
δ0 (q) and δ1 (q, a) undefined and δ2 (q, a, b) = (q′ , c).

Distributive Laws and Decidable Properties of SOS

88

Note that an MQM never makes a queue empty, and it terminates if and only if it reaches a configuration
(q, a) with a single letter a in the queue, such that δ0 (q) and δ1 (q, a) are undefined.
Theorem 19 It is undecidable whether a given QM terminates from the configuration (q1 , $), called the
initial configuration.
Proof. As is well known, it is undecidable whether a classical QM M as defined in [9] terminates on its
initial configuration. For every classical M one constructs a QM M as in Definition 18 that terminates
on its initial configuration if and only if M does.
2

5

From queue machines to stream specifications

Given a QM M = (Q, A, $, q1 , δ0 , δ1 , δ2 ), consider a signature with a single constant C and a family of
unary operation symbols {q | q ∈ Q}, and a family of rules:
a

$

C −→ q1 (C)

(C)

c

q(x) −→ q′ (x)

a

x −→ y

(R0)

c

q(x) −→ q′ (y)

(R1)

b

x −→ y −→ z
c

q(x) −→ q′ (z)

(R2)

(6)

for all q, q′ ∈ Q and a, b, c ∈ A subject to the following conditions:
• R0 is included when δ0 (q) = (q′ , c),
• R1 is included when δ0 (q) is undefined and δ1 (q, a) = (q′ , c), and
• R2 is included when δ0 (q) and δ1 (q, a) are undefined and δ2 (q, a, b) = (q′ , c).
These rules are mixed GSOS, so they define a biGSOS law ρM : ΣB∞ =⇒ BΣ∗ , where BX = A × X
and ΣX = 1 + Q × X . We shall now prove, in a sequence of lemmas, that ρM uniquely extends to
a distributive law if and only if M does not terminate from the initial configuration. Our argument
relies on the following correspondence between partial runs of M and prefixes of streams produced by
distributive laws that extend ρM :
Lemma 20 For every n > 0, if a QM M makes n − 1 steps from the initial configuration:
q1 , w1

 q2 , w2

 ···

 q3 , w3

 qn , wn

(where w1 = $) then every distributive law λ that extends ρM maps the constant symbol C ∈ Σ∗ B∞ 0 to a
stream λ0 (C) ∈ B∞ Σ∗ 0 that begins with
$

a

a

a

an−1

1
3
3
· · · −→ τn ,
τ0 −→ τ1 −→
τ2 −→
τ3 −→

where
• each ai ∈ A is the last letter of wi+1 , i.e., the letter added to the queue in the i-th step of M ,
• τ0 = C, and τ1 , . . . , τn ∈ Σ∗ 0 are such that each τi = qi (τ j ), where 0 ≤ j < i is such that i − j = |wi |.
(Note that from these properties it follows that a j a j+1 · · · ai−1 = wi .)

B. Klin & B. Nachyła

89

Proof. We proceed by induction on n. For the base case n = 1, if λ extends ρM then, thanks to rule C,
the stream λ0 (C) must begin with:
$

λ0 (C) = C −→ q1 (C)
which satisfies the inductive statement.
For the inductive step, assume that M makes n steps:
q1 , w1

 q2 , w2

 ···

 q3 , w3

 qn , wn

 qn+1 , wn+1

By the inductive assumption, for any λ that extends ρM , the stream λ0 (C) must begin with:
$

a

a

an−1

a

3
3
1
· · · −→ τn ,
τ0 −→ τ1 −→
τ2 −→
τ3 −→

(7)

where τn = qn (τ j ) such that n − j = |wn |, and wn = a j a j+1 a j+2 · · · an−1 .
There are three cases to consider, depending on how the configuration (qn+1 , wn+1 ) is derived from
(qn , wn ):
• δ0 (qn ) = (qn+1 , an ) and wn+1 = wn an , for some an ∈ A. Then ρM includes a corresponding rule
an
R0, and if λ extends ρM then the initial part (7) in λ0 (C) is necessarily extended with τn −→
τn+1 = qn+1 (τ j ), and the inductive statement is preserved.
• δ0 (qn ) is undefined, and δ1 (qn , a j ) = (qn+1 , an ) and wn+1 = a j+1 a j+2 · · · an−1 an , for some an ∈ A.
Then ρM includes a corresponding rule R1, and if λ extends ρM then the initial part (7) in λ0 (C)
an
τn+1 = qn+1 (τ j+1 ), and the inductive statement is preserved.
is necessarily extended with τn −→
• δ0 (qn ) and δ1 (qn , a j ) are undefined, and δ2 (qn , a j , a j+1 ) = (qn+1 , an ) and wn+1 = a j+2 · · · an−1 an ,
for some an ∈ A. (Note that, since M does not terminate in (qn , wn ), we know that n − j ≥ 2.) Then
ρM includes a corresponding rule R2, and if λ extends ρM then the initial part (7) in λ0 (C) is
an
τn+1 = qn+1 (τ j+2 ), and the inductive statement is preserved.
necessarily extended with τn −→
2
Lemma 21 For any QM M that does not terminate from the initial configuration, the transformation
ρM is extended by at most one distributive law.
Proof. Consider distributive laws λ , λ ′ : Σ∗ B∞ =⇒ B∞ Σ∗ that both extend ρM . For any set X , we wish
to prove that the component functions λX , λX′ : Σ∗ B∞ X → B∞ Σ∗ X are equal. We prove this by structural
induction on terms t ∈ Σ∗ B∞ X .
For the first base case, if t = σ ∈ B∞ X then λX (t) = λX′ (t) follows immediately from axiom (i) of
Definition 9. For the second base case, if t = C then the equality follows from Lemma 20, since M
makes arbitrarily many steps from the initial configuration.
For the inductive step, we need to prove that for all terms t ∈ Σ∗ B∞ X and states q ∈ Q, if λX (t) = λX′ (t)
then λX (q(t)) = λX′ (q(t)). Denote

σ

=

λX (t)

=

λX′ (t)

=

a

a

a

0
1
2
···
τ0 −→
τ1 −→
τ2 −→

(τi ∈ Σ∗ X ).

We begin by proving that the desired equality holds when postcomposed with πΣ∗ X : B∞ Σ∗ X → BΣ∗ X , i.e.,
that the streams λX (q(t)) and λX′ (q(t)) coincide on their first transitions. This is proved by case analysis
similar to that used in the proof of Lemma 20. For example, if δ0 (q) is undefined and δ1 (q, a0 ) = (q′ , b)

Distributive Laws and Decidable Properties of SOS

90

for some q′ ∈ Q and b ∈ A, then ρM includes a relevant R1 rule and if λ and λ ′ both extend ρM then
b
λX (q(t)) and λX′ (q(t)) must both begin with q(τ0 ) −→ q′ (τ1 ).
We proved that for any term t ∈ Σ∗ B∞ X the streams λX (t) and λX′ (t) coincide on the first transitions,
i.e., π Σ∗ ◦ λ = π Σ∗ ◦ λ ′ . Hence, by Lemma 16(b), λ = λ ′ .
2
Lemma 22 If a QM M does not terminate from the initial configuration, then there exists a distributive
law that extends ρM .
Proof. Fix a QM M that does not terminate from the initial configuration (q1 , $). We shall define a
distributive law λ that extends ρM . For any set X , begin by defining

λX (C)

a

a

a

0
1
2
···
τ0 −→
τ1 −→
τ2 −→

=

∈

B ∞ Σ∗ X

with τi ∈ Σ∗ X and ai ∈ A such that:
• τ0 = C and a0 = $,
• for any i > 0, τi = qi (τ j ), where the i-th configuration reached by M is (qi , wi ) and j = i − |wi |;
moreover, a j is the first letter of wi .
To define λX on other terms in Σ∗ B∞ X , note that apart from rule C, the entire specification ρM is a
coGSOS specification, therefore, by Theorem 17, there exists a distributive law λ̂ that extends all rules
of ρM apart from C. For any term t ∈ Σ∗ B∞ X where C does not appear, define λX (t) to be λ̂X (t). If C
appears in t, replace it with the stream λX (C) and use λ̂Σ∗ X followed by B∞ µX on the term obtained.
It is easy to see that λ defined in this manner is natural and satisfies axioms (i)-(iii) of Definition 9
(see also Example 10).
The only remaining axiom is (iv), which in principle could fail if the above procedure, on one of the
terms τi present in λX (C), returned a stream that differs from the substream of λX (C) starting at τi . This
is, however, not the case, as can be proved by induction on i, using case analysis similar to that used in
the proof of Lemma 20.
2
Lemma 23 If a QM M terminates from the initial configuration, then there is no distributive law that
extends ρM .
Proof. Assume to the contrary, that M terminates after n steps in a configuration (qn , wn ) and there is a
distributive law λ that extends ρM . By Lemma 20, the stream λ0 (C) begins with:
a

a

a

a

1
2
3
n
C −→
· · · τn−1 −→
τ1 −→
τ2 −→
τn

where τn = qn (τn−|wn | ). Note that M can terminate in (qn , wn ) only if wn has length 1, hence τn =
qn (τn−1 ) and wn = an ; moreover, δ0 (qn ) and δ1 (qn , an ) must be undefined.
an+1
The remaining argument follows the line of Example 14. Suppose that the next step in λ0 (C) is τn −→
τn+1 , for some an+1 ∈ A and τn+1 ∈ Σ∗ 0. Since δ0 (qn ) and δ1 (qn , an ) are undefined, δ2 (qn , an , an+1 ) =
(q′ , b) must be defined for some q′ ∈ Q and b ∈ A. As a result, ρM contains an R2 rule:
an+1

a

n
x −→
y −→ z

b

qn (x) −→ q′ (z)

B. Klin & B. Nachyła

91

and, since λ extends ρM , instantiating x to τn−1 we obtain b = an+1 and τn+1 = q′ (τn+1 ), a contradiction.
2
Note that all rules in ρM are either GSOS or coGSOS rules; we call specifications with this property
mixed-GSOS specifications. We arrive at a proof of our Claim from the Introduction:
Theorem 24 For the case of stream systems, it is undecidable whether a given mixed-GSOS specification extends to a unique distributive law.
Proof. Combine Lemmas 21-23 with Theorem 19

6

2

Labelled transition systems

We shall now show how to encode Queue Machines into mixed-GSOS specifications for LTSs, to prove
that distributive laws admit no format for BX = Pω (A × X ) either. Since the general idea and most
technical details are the same as in the case of stream systems (Section 5), we only sketch the differences
between the two cases.
To begin with, note that the set of rules (6) from Section 5 can be read as rules in the mixed-GSOS
format for BX = Pω (A × X ). However, taking the same rules for a QM M would give rise to a biGSOS
law that always extends to some distributive law (a counterpart of Lemma 23 would fail). Intuitively,
unlike in the case of BX = A × X , a distributive law for BX = Pω (A × X ) is allowed to produce an
empty set of successors for a term that corresponds to a terminating configuration of M .
Our solution is to extend the specification (6), now understood as a mixed-GSOS specification for
the LTS behaviour, with additional rules:
a

x −→ y

y6−→

a

q(x) −→ q(x)

(R2’)

(8)

for q ∈ Q and a ∈ A. These new rules are included whenever δ0 (q) and δ1 (q, a) are undefined. We denote
the biGSOS law defined by the extended specification by ρEXT : ΣB∞ =⇒ BΣ∗ , where BX = Pω (A × X )
and ΣX = 1 + Q × X .
For any QM M , the biGSOS law ρEXT uniquely extends to a distributive law if and only if M does
not terminate from the initial configuration. The proof of this follows the line of Section 5, and we shall
only explain the main differences here.
The main technical step in Section 5, Lemma 20, holds in a very similar form:
Lemma 25 For every n > 0, if a QM M makes n− 1 steps from the initial configuration as in Lemma 20,
then every distributive law λ that extends ρEXT maps the constant symbol C ∈ Σ∗ B∞ 0 to a tree λ0 (C) ∈
B∞ Σ∗ 0 that begins with a degenerate tree, i.e., a sequence:
$

a

a

a

an−1

1
3
3
· · · −→ τn
τ0 −→ τ1 −→
τ2 −→
τ3 −→

where ai and τi are as in Lemma 20.
Proof. By induction on n entirely analogous to the proof of Lemma 20. Intuitively, the initial part of
λ0 (C) is degenerate because the specification ρEXT is deterministic, i.e., it only infers one transition from
C, and infers at most one transition for q(x) if x can make at most one transition.
2
The next two lemmas are proved entirely analogously to Section 5:

Distributive Laws and Decidable Properties of SOS

92

Lemma 26 For an QM M that does not terminate from the initial configuration, the transformation
ρEXT is extended by at most one distributive law.
Lemma 27 If a QM M does not terminate from the initial configuration, then there exists a distributive
law that extends ρEXT .
In particular, the distributive law defined in Lemma 27 is exactly as in the proof of Lemma 22, with
the streams produced in the latter considered as (degenerate) trees.
The only step that requires some care is Lemma 23, which now takes the form:
Lemma 28 If a QM M terminates from the initial configuration, then there is no distributive law that
extends ρEXT .
Proof. Assume to the contrary, that M terminates after n steps in a configuration and there is a distributive law λ that extends ρM . By Lemma 25, the tree λ0 (C) begins with a sequence:
a

a

a

a

3
1
2
n
τ1 −→
τ2 −→
τn
C −→
· · · τn−1 −→

where, as in the proof of Lemma 23, τn = qn (τn−1 ), and δ0 (qn ) and δ1 (qn , an ) are undefined.
What successors can τn have in the tree λ0 (C)? Assume first that is has no successors. Since λ
extends ρEXT , by applying a corresponding rule R2’ instantiated to q = qn , x = τn−1 and a = an we infer
that τn = q(τn−1 ) indeed does have at least one successor, which is a contradiction.
Now assume that τn has some successors. All these successors are terms in Σ∗ 0. Some of these successors are minimal, i.e., have the smallest depth of nesting of operations qi . Pick one of these minimal
b
successors and call it τ ′ . Since λ extends ρEXT , the transition τn −→ τ ′ must be derivable from rules
in ρEXT . The only rule that can be used to this end is a corresponding rule R2, instantiated to q = qn ,
x = τn−1 , y = τn and a = an . But this means that τn must have a successor z such that τ ′ = q′ (z), which
2
contradicts the minimality of τ ′ .
Thus we prove our Claim from the Introduction for the case of LTSs:
Theorem 29 For the case of labeled transition systems (BX = Pω (A × X )), it is undecidable whether a
given mixed-GSOS specification extends to a unique distributive law.
Proof. Combine Lemmas 26-28 and Theorem 19.

7

2

Related work

We have proved, for the case of stream systems and LTSs, that there is no format for distributive laws
of monads over comonads that would be complete for mixed-GSOS specification, i.e., that would cover
exactly those mixed-GSOS specification that extend to a distributive law. The specifications used in
our proofs are actually coGSOS specifications extended with only one GSOS rule that has no premises.
Moreover, the coGSOS rules only uses lookahead of depth 2, and the GSOS rule uses a rule conclusion
of height 2. As a result, there is no complete format even for such restricted specifications.
On the other hand, our results do not contradict the existence of formats complete for classes of
specifications that do not cover the mixed-GSOS format. Indeed as shown in [13], in the context of
LTSs one can combine GSOS and coGSOS but restrict to specifications with positive premises only, and

B. Klin & B. Nachyła

93

guarantee the existence of a corresponding distributive law. (Note that specifications used in Section 6
rely on negative rule premises.)
Our proofs can be easily modified to show undecidability of other problems related to operational
specifications, some of them phrased without reference to distributive laws. For example, in the case of
LTSs, it is undecidable whether a transition system specification (or even a mixed-GSOS specification)
has a supported model, a unique supported model, or a unique stable model [6]; the constructions needed
for these are minor variations of the one used in Section 6.
In the case of stream systems, our results are related to studies of the productivity of stream definitions [3]. Specifications used in Section 5 can be seen as definitions in the “pure stream specification
format” of [3]. Indeed, that format is closely related to stream coGSOS extended with premise-less GSOS
rules for constants. In [3] it was proved that productivity of pure stream specifications is decidable for
specifications that are data-oblivious, i.e., natural with respect to transition labels. Our specifications are
not data-oblivious in that sense. It is easy to use the constructions of Section 5 to prove that productivity
of pure stream specifications becomes undecidable without data-obliviousness.
Acknowledgment. We are grateful to Jurriaan Rot for several helpful discussions, and to anonymous
referees for spotting embarrassing mistakes both in the content and the presentation of our results.

References
[1] F. Bartels (2004): On Generalised Coinduction and Probabilistic Specification Formats. PhD dissertation,
CWI, Amsterdam.
[2] B. Bloom, S. Istrail & A. Meyer (1995): Bisimulation can’t be traced. Journal of the ACM 42, pp. 232–268,
doi:10.1145/200836.200876.
[3] J. Endrullis, C. Grabmayer, D. Hendriks, A. Isihara & J. Klop (2007): Productivity of Stream Definitions.
Fundamentals of Computation Theory, pp. 274–287, doi:10.1007/978-3-540-74240-1_24.
[4] W. Fokkink (1994): The Tyft/Tyxt Format Reduces to Tree Rules. In: Procs. TACS, Lecture Notes in Computer
Science 789, Springer, pp. 440–453, doi:10.1007/3-540-57887-0_109.
[5] W. Fokkink & R. J. van Glabbeek (1996): Ntyft/ntyxt rules reduce to ntree rules. Information and Computation 126, pp. 1–10, doi:10.1006/inco.1996.0030.
[6] R. J. van Glabbeek (2004): The meaning of negative premises in transition system specifications II. J. Log.
Algebr. Program. 60-61, pp. 229–258, doi:10.1016/j.jlap.2004.03.007.
[7] M. Kick (2002): Rule Formats for Timed Processes. In: Proc. CMCIM’02, ENTCS 68, Elsevier, pp. 12–31,
doi:10.1016/S1571-0661(04)80498-5.
[8] B. Klin (2011): Bialgebras for structural operational semantics: An introduction. Theoretical Computer
Science 412(38), pp. 5043–5069, doi:10.1016/j.tcs.2011.03.023. CMCS Tenth Anniversary Meeting.
[9] D. Kozen (1997): Automata and computability. Springer, doi:10.1007/978-1-4612-1844-9.
[10] M. Lenisa, J. Power & H. Watanabe (2004): Category theory for operational semantics. Theoretical Computer Science 327(1-2), pp. 135–154, doi:10.1016/j.tcs.2004.07.024.
[11] S. Mac Lane (1998): Categories for the Working Mathematician, second edition. Springer.
[12] J. J. M. M. Rutten (2000): Universal coalgebra: a theory of systems. Theoretical Computer Science 249, pp.
3–80, doi:10.1016/S0304-3975(00)00056-6.
[13] S. Staton (2008): General Structural Operational Semantics through Categorical Logic. In: Proc. LICS’08,
IEEE Computer Society Press, pp. 166–177, doi:10.1109/LICS.2008.43.
[14] D. Turi & G. D. Plotkin (1997): Towards a Mathematical Operational Semantics. In: Proc. LICS’97, IEEE
Computer Society Press, pp. 280–291, doi:10.1109/LICS.1997.614955.

