arXiv:1706.05893v1 [cs.FL] 19 Jun 2017

SIGNAL MACHINE AND
C E L L U L A R A U T O M AT O N
TIME-OPTIMAL
QUASI-SOLUTIONS OF THE
FIRING SQUAD/MOB
S Y N C H R O N I S AT I O N
PROBLEM ON CONNECTED
GRAPHS
simon wacker
simon.wacker@kit.edu

We construct a time-optimal quasi-solution of the firing
mob synchronisation problem over finite, connected, and
undirected multigraphs whose maximum degrees are uniformly bounded by a constant. It is only a quasi-solution
because its number of states depends on the graph or, from
another perspective, does not depend on the graph but
is countably infinite. To construct this quasi-solution we
introduce signal machines over continuum representations
of such multigraphs and construct a signal machine whose
discretisation is a cellular automaton that quasi-solves the
problem. This automaton uses a time-optimal solution of
the firing squad synchronisation problem in dimension one
with one general at one end to synchronise edges, and freezes
and thaws the synchronisation of edges in such a way that
all edges synchronise at the same time.
introduction. The firing squad synchronisation problem in dimension one with one general at one end is to synchronise each finite
one-dimensional array of cells starting from one end of the array and
the cell at this end is called general. It was proposed by John R. Myhill in 1957, solved by John McCarthy and Marvin Lee Minsky, and
published by Edward Forrest Moore in 1962 (see [Moo64]). The first

1

time-optimal several-thousand-states solution was found by Eiichi Goto
in 1962 (see [Got62]), reduced to 16 states by Abraham Waksman in
1966 (see [Wak66]), and reduced to 8 states by Robert Balzer in 1967
(see [Bal67]). Hein D. Gerken found another time-optimal 7-states solution in 1987 (see [Ger87]) and Jacques Mazoyer found a time-optimal
6-states solution also in 1987 (see [Maz87]). It is unknown whether
there is a time-optimal 5-states solution but it is known that there is
no time-optimal 4-states solution, a result due to Robert Balzer and
Peter Sanders (see [Bal67; San94]).
The firing mob synchronisation problem is to synchronise each finite,
connected, and undirected graph whose maximum degree is bounded
by a fixed constant starting from any vertex and this vertex is called
general. It was solved by P. Rosenstiehl, J. R. Fiksel, and A. Holliger
in 1972 (see [RFH72]) and also by Francesco Romani in 1976 (see
[Rom76]), where the latter solution achieves better running times than
the former. The problem for specific classes of graphs were for example
studied by Kojiro Kobayashi in 1977 and 1978 (see [Kob77; Kob78a;
Kob78b]) and by Zsuzsanna Róka in 2000 (see [Rók00]). Karel Culik
II and Simant Dube presented a solution of the general case in 1991 (see
[CD91]). It needs 3.5r-many steps, where r is the maximal distance of
the general to a vertex and is called radius of the graph with respect
to the general. By using more and more states, the solution can be
adjusted such that the number of steps it needs approaches 3r.
It was shown that r + d is a lower bound for the number of steps
that solutions of the firing mob synchronisation problem need by John
J. Grefenstette in 1983 (see [Gre83]), where d is the maximal distance
between two vertices of the graph and is called diameter of the graph.
Because there are graphs and choices of generals such that the diameter is 2r, the solutions by Karel Culik II and Simant Dube approach
the optimal number of steps, namely 3r, if r is taken as problem size.
However, if r + d is taken as problem size, then their solutions do not
approach the optimal number of steps.
In the present chapter we construct a time-optimal quasi-solution
that needs exactly r + d steps but whose number of states depends
on the graph or, from another perspective, does not depend on the
graph but is countably infinite (this is why we call it a quasi-solution).
It can also be turned into a time-optimal quasi-solution of the firing
squad synchronisation problem for any region in any dimension with
one general at any position by regarding each region to be synchronised as a graph, where cells in the region are vertices and edges are
neighbourhood relationships.
However, restricted to specific classes of problems, the quasi-solution
may not be time-optimal. For example, restricted to rectangular regions
with one general at one corner, the quasi-solution needs 2(k + ` − 2)many steps whereas (k + ` + max{k, `} − 3)-many steps is optimal (see
for example [UYY09]), where k and ` are the side lengths of the rect-

2

angle. Nevertheless, because the quasi-solution is (trivially) embeddable
in the sense of [Gre83], according to theorem 1 in [Gre83], it can be
combined with finitely many embeddable time-optimal solutions for
specific classes of problems to get one quasi-solution that is also timeoptimal for those classes. Examples of solutions for specific classes, like
rectangular regions with one general at the upper left corner, are given
in sections 5 and 6 in [Gre83].
To design, explain, and draw solutions of firing squad/mob synchronisation problems, it is convenient to think about, talk about, and draw
continuous space-time diagrams of different kinds of signals that move
across the cell space, vanish or give rise to new signals upon reaching
boundaries or junctions of the space or upon colliding with each other.
This is mostly done in an informal way, but the idea of signals has
also been formalised for one-dimensional cellular automata by Jérôme
Olivier Durand-Lose in 2005 (see [Dur05]).
This formalisation however does not handle accumulations of events
like collisions and does not allow infinitely many signals of different
speeds, which naturally occur and are necessary in descriptions of many
solutions of the firing squad synchronisation problem by signals. For example, collisions accumulate at the time synchronisation finishes and
infinitely many signals of different speeds may originate from the general. In the time evolutions of the actual cellular automata, the accumulations of collisions disappear due to the discreteness of space and
time, and the infinitely many signals are cleverly produced by finitely
many states (see for example [Maz87]).
Because we want to describe our quasi-solution in terms of signals
in a formal way, we first introduce continuum representations of finite
and connected multigraphs (without self-loops), we secondly introduce
signal machines over such representations that allow infinitely many signals of different speeds and seamlessly handle accumulations of events
and accumulations of accumulations of events and so forth, and we
thirdly construct a signal machine for the continuous firing mob synchronisation problem over such representations and shortly note how
to discretise it to get a cellular automaton quasi-solution of the firing
mob synchronisation problem.
contents. In section 1 we state the firing squad and the firing
mob synchronisation problems. In section 2 we introduce undirected
multigraphs (without self-loops) and direction-preserving paths in such
graphs, which are paths that do not make U-turns. In section 3 we
introduce continuum representations of undirected multigraphs, which
are in a sense drawings of graphs in a high-dimensional Euclidean space.
In section 4 we introduce signal machines, which can be studied in their
own right, but which can also be thought of as high-level views of time
evolutions of cellular automata over graphs, like cellular automata over
finitely right generated cell spaces, that are restricted to configurations

3

with a fixed finite support. In section 5 we construct a signal machine
whose discretisation is a cellular automaton that quasi-solves the firing
mob synchronisation problem in (r + d)-many steps. And in section 6
we sketch a proof for that statement. The impatient may right now have
a look at the continuous space-time diagrams of the synchronisations
of small trees as performed by the quasi-solution: See figures 5.2 to 5.5
on pages 32 to 35.
affinely extended
real numbers R
extended real
intervals [r, r0 ],
]r, r0 [, and [r, r0 [
and ]r, r0 ]
closed
integer-valued
interval [z : z 0 ]

preliminary notions. The affinely extended real numbers R ∪
{−∞, +∞} are denoted by R. For each tuple (r, r0 ) ∈ R × R such that
r ≤ r0 , the closed, open, and the two half-open extended real intervals
with the endpoints r and r0 are denoted by [r, r0 ], ]r, r0 [, and [r, r0 [ and
]r, r0 ] respectively. And, for each tuple (z, z 0 ) ∈ Z × Z such that z ≤ z 0 ,
the closed integer-valued interval with the endpoints z and z 0 , namely
{z, z + 1, . . . , z 0 } or equivalently [z, z 0 ] ∩ Z, is denoted by [z : z 0 ].
1

the firing squad/mob synchronisation problems

We formally state the problems for generalised cellular automata as
introduced in [Wac16] over spaces as introduced in [Wac17]. However,
you do not need to be familiar with these automata and spaces to
understand the problems on an intuitive level or to understand the
quasi-solutions in detail. Such an automaton is essentially a cellular
automaton over a vertex-transitive graph, which means that each vertex
of the graph is a copy of a fixed possibly-infinite-state machine, its
inputs are the states of the vertex’s neighbours, and all vertices change
their states synchronously.
In this section, let R = ((M , G, .), (m0 , {gm0 ,m }m∈M )) be a finitely
right generated cell space, let N be a finite right generating set of R that
contains G0 , where G0 is the stabiliser of m0 under ., let G = (M , E ) be
the coloured N -Cayley graph of R, let C be a semi-cellular automaton
over R with state set Q, neighbourhood N , and local transition function
δ, and let ∆ be the global transition function of C.
To state the problems succinctly we introduce the notions of passive
subsets of states, dead states, supports of global configurations with
respect to a distinguished dead state, and what it means for a global
configuration to be of the form of a pattern in the following four definitions.
passive set of
states

Definition 1.1. Let P be a subset of Q. It is called passive if and
only if, for each local configuration ` ∈ QN with im(`) ⊆ P , we have
δ ( ` ) = ` ( G0 ) .


dead state

Definition 1.2. Let q be a state of Q. It is called dead if and only if, for
each local configuration ` ∈ QN with `(G0 ) = q, we have δ (`) = q. 

4

In the remainder of this section, let Q contain a distinguished dead
state named #.
Definition 1.3. Let c be a global configuration of QM . The set supp(c) =
M r c−1 (#) is called support of c.
support supp(c) of

c

Definition 1.4. Let A be a subset of M , let p be a pattern of QA ,
and let c be a global configuration of QM . The global configuration c
is said to be of the form p if and only if there is an element g ∈ G such
that cg.A = g I p and cM r(g.A) ≡ #.


global
configuration is of
the form p

We state the firing squad synchronisation problem in
Definition 1.5. Let #, g, s, and f be four distinct states, and let
Q0 be the set that consists of those states. A solution of the firing
squad synchronisation problem in dimension one with one general at
the left end is a cellular automaton C over ((Z, Z, +), (0, {z}z∈Z )) with
neighbourhood {−1, 0, 1} and finite set of states that includes Q0 such
that the state # is dead and the set {#, s} is passive, and whose global
transition function ∆ has the following property:
For each global configuration c with finite support of the form gss · · · s,
there is a non-negative integer k such that the global configuration
∆k (c) is of the form ff · · · f and has the same support as c, and such
that the state f does not occur in any of the global configurations ∆j (c),
for j ∈ N0 with j < k.

Remark 1.6. Let C be a solution of the above problem, let c be a
global configurations of the form gss · · · s, and let k be the non-negative
integer from the problem definition. Then, because the state # is dead
and the support of ∆k (c) is the same as the one of c, for each nonnegative integer j with j ≤ k, the support of ∆j (c) is the same as
the one of c. Broadly speaking, in the time evolution of solutions, the
support of initial configurations can neither shrink nor grow before
synchronisation is finished. Moreover, because the set {#, s} is passive,
if the support of c consists of at least 3 cells, then ∆(c) cannot be
of the form ff · · · f. Broadly speaking, the problem cannot be solved
trivially.

Remark 1.7. As mentioned above, for each global configuration c of
the form gss · · · s, the supports of the global configurations that are
observable in the time evolutions that begin in the configuration c of
cellular automata that solve the above problem, are included in the
support of c. Hence, we can regard such cellular automata as automata
over one-dimensional arrays with one dummy neighbour in the state #
at each end.


5

firing squad
synchronisation
problem in
dimension one
with one general at
the left end

Remark 1.8. The above problem can be generalised in many ways. For
example, by allowing the general to be placed anywhere or by allowing
more than one general.

We state the firing mob synchronisation problem in

firing mob
synchronisation
problem in R with
respect to S

Definition 1.9. Let #, g, s, and f be four distinct states, and let
Q0 be the set that consists of those states. A solution of the firing
mob synchronisation problem in R with respect to S is a semi-cellular
automaton over R with neighbourhood S and finite set of states that
includes Q0 such that the state # is dead and the set {#, s} is passive,
and whose global transition function ∆ has the following property:
For each finite subset A of M such that the subgraph G [A] of G
induced by A is connected, each element a ∈ A, each pattern p ∈ QA
such that p(a) = g and pAr{a} ≡ s, and each global configuration c
of the form p, there is a non-negative integer k such that the global
configuration ∆k (c) is of the form A → Q, a 7→ f, and such that the
state f does not occur in any of the global configurations ∆j (c), for
j ∈ N0 with j < k.

Remark 1.10. The firing squad synchronisation problem with one general at an arbitrary position is the firing mob synchronisation problem
in ((Z, Z, +), (0, {z}z∈Z )) with respect to {−1, 0, 1}. Note that the
notions of semi-cellular and cellular automata are identical over (Z, Z,
+).

Remark 1.11. Each semi-cellular automaton over R with neighbourhood S is equivalent to a cellular automaton over the coloured S-Cayley
graph of R acted upon by its automorphism group, in the sense that,
for each of the former kind of automata, there is one of the latter kind
with the same global transition function, and vice versa. Note that the
stabilisers of coloured S-Cayley graphs of R are trivial, and hence the
notions of semi-cellular and cellular automata are identical over such
graphs.

Remark 1.12. We can regard semi-cellular automata that solve the
above problem as semi-cellular automata over subgraphs of G that are
induced by finite subsets of M with one dummy neighbour in the state
# at each edge that leads out of the subgraph. Note that, because the
graph G is of bounded degree, the maximum degrees of the subgraphs
it induces are uniformly bounded by a constant.

Remark 1.13. Ideally we would like an abstract description of a semicellular automaton that does not depend on any specifics of R and S
and that yields a solution for each choice of R and S or at least for as
huge a class of such choices as possible.


6

2

undirected multigraphs

Undirected multigraphs without self-loops are introduced in
Definition 2.1. Let V and E be two disjoint sets, and let ε be a
map from E to {{v, v 0 } ⊆ V | v 6= v 0 }. The triple G = (V, E, ε) is
called undirected multigraph; each element v ∈ V is called vertex; each
element e ∈ E is called edge; and, for each edge e ∈ E, each vertex of
ε(e) is called end of e.

Remark 2.2. Because each set in the codomain of ε consists of exactly two distinct vertices, there are no self-loops in the undirected
multigraph G. With minor modifications the theory and the automata
presented in this chapter also work if there are self-loops. They were
merely excluded to make the presentation a little simpler.


undirected
multigraph
G = (V, E, ε)
vertex v
edge e
ends ε(e) of e

In the remainder of this section, let G = (V, E, ε) be an undirected
multigraph.
What being finite means for multigraphs is said in
Definition 2.3. The multigraph G is called finite if and only if the
sets V and E are both finite.


finite multigraph

Isolated vertices are the ones without incident edges as introduced
in
Definition 2.4. Let v be a vertex of G. It is called isolated if and only
if, for each edge e ∈ E, we have v ∈
/ ε(e).


isolated vertex

Directed edges are edges with distinguished source and target vertices
as introduced in
Definition 2.5. Let e be an edge of G, and let v1 and v2 be two
vertices of G such that {v1 , v2 } = ε(e). The triple ~e = (v1 , e, v2 ) is
called directed edge from v1 through e to v2 ; the vertex σ (~e) = v1 is
called source of ~e; the edge β (~e) = e is called bed of ~e; and the vertex
τ (~e) = v2 is called target of ~e.

At each vertex there is an empty path that starts and ends at the
vertex, and non-empty paths are concatenations of directed edges with
matching source and target vertices as introduced in
Definition 2.6.
a. Let v be a vertex of G. The singleton p = (v )
is called empty path in v, the vertex σ (p) = τ (p) = v is called
source and target of p, and the non-negative integer |p| = 0 is
called length of p.

directed edge ~e
from v1 through e
to v2
source σ (~e) of ~e
bed β (~e) of ~e
target τ (~e) of ~e

empty path (v ) in
v
source σ ((v )) and
target τ ((v )) of (v )
length |(v )| of (v )

7

b. Let n be a positive integer and, for each index i ∈ [1 : n], let ~ei
be a directed edge of G such that, if i 6= 1, then σ (~ei ) = τ (~ei−1 ).
The (2n + 1)-tuple p = (σ (~e1 ), β (~e1 ), τ (~e1 ), . . . , β (~en ), τ (~en )) is
called path from σ (~e1 ) to τ (~en ); the vertex σ (p) = σ (~e1 ) is called
source of p; the vertex τ (p) = τ (~en ) is called target of p; and the
positive integer |p| = n is called length of p.

path p from σ (~e1 )
to τ (~en )
source σ (p) of p
target τ (p) of p

c. The set of paths is denoted by P.

length |p| of p
set P of paths

Remark 2.7. Each directed edge is a path of length 1.




Subpaths are connected parts of paths as introduced in

subpath p[k:`] of p

Definition 2.8. Let p = (v0 , e1 , v1 , . . . , en , vn ) be a path of G, and
let k and ` be two indices of [0 : n] such that k ≤ `. The path (vk ),
if k = `, or (vk , ek+1 , vk+1 , . . . , e` , v` ), otherwise, is called subpath of p
and is denoted by p[k:`] .

Direction-preserving paths are the ones without U-turns as introduced in

directionpreserving
set P of
directionpreserving
paths

concatenation of p
and p0

Definition 2.9. Let p = (v0 , e1 , v1 , . . . , en , vn ) be a path of G. It is
called direction-preserving if and only if, for each index i ∈ [1 : n − 1],
we have ei 6= ei+1 . The set of direction-preserving paths is denoted by
P .

Two paths with matching target and source vertices can be concatenated as introduced in
Definition 2.10. Let p = (v0 , e1 , v1 , . . . , en , vn ) and p0 = (v00 , e01 , v10 ,
. . . , e0n0 , vn0 0 ) be two paths of G such that vn = v00 . The path p • p0 =
(v0 , e1 , v1 , . . . , en , vn , e01 , v10 , . . . , e0n0 , vn0 0 ) is called concatenation p • p0 of
p and p0 .

Remark 2.11. Each non-empty path is the concatenation of directed
edges.

What being connected means for multigraphs is said in

connected
multigraph

Definition 2.12. The multigraph G is called connected if and only if,
for each tuple (v, v 0 ) ∈ V × V, there is a path from v to v 0 .

Remark 2.13. The multigraph G is connected if and only if, for each
tuple (v, v 0 ) ∈ V × V, there is a direction-preserving path from v to
v0.

We can assign weights to edges as done in

8

Definition 2.14. Let ω be a map from E to R>0 . It is called edge
weighting of G, and, for each edge e ∈ E, the element ω (e) is called
edge weight of e.


edge weighting ω
of G
edge weight ω (e)
of e

Edge weights induce weights of paths as introduced in
Definition 2.15. Let ω be an edge weighting of G and let p = (v0 , e1 , v1 , . . . , en , vn )
P
be a path of G. The sum ω (p) = ni=1 ω (ei ) is called weight of p.
weight ω (p) of p

Remark 2.16. Each empty path has weight 0.



Remark 2.17. Each directed edge has the same weight as its bed.



3

continuum representation

In this section, let G = (V, E, ε) be an undirected multigraph without
isolated vertices and let ω be an edge weighting of G.
An orientation is a choice of source and target vertices for each edge
as introduced in
Definition 3.1. Let σ and τ be two maps from E to V such that, for
each edge e ∈ E, we have {σ (e), τ (e)} = ε(e). The tuple (σ, τ ) is called
orientation of G.


orientation (σ, τ )
of G

Realising weighted edges as disjoint intervals and gluing these intervals together at shared ends yields a continuum representation of G and
is done in
Definition 3.2. Let (σ, τ ) be an orientation of G, let
ζ : R r {0} → {σ, τ },
(
σ, if r < 0,
r 7→
τ , if r > 0,

map ζ from
R r {0} to {σ, τ }

let


 φ : E → R<0 ,



e 7→ −








 ψ : E → R>0 , 


ω (e)  and 

,
2

e 7→

ω (e) 
,
2

and let ∼ be the equivalence relation on R × E such that, for each tuple
(r, e) ∈ R × E and each tuple (r0 , e0 ) ∈ R × E,

(r, e) ∼ (r0 , e0 ) ⇐⇒ r ∈ {φ(e), ψ (e)}

maps φ and ψ
from E to R<0
and R>0
equivalence
relation ∼ on
R×E

∧ r0 ∈ {φ(e0 ), ψ (e0 )}
∧ ζ (r )(e) = ζ (r0 )(e0 ).
The set G = (
ation of G.

S

e∈E [φ(e), ψ (e)] × {e}) /∼

is called continuum represent

9

continuum
representation G
of G

Remark 3.3. Each weighted edge is realised as a closed interval whose
length is the edge’s weight. These intervals are made disjoint by taking
the Cartesian product with the respective edge. And they are glued
together at shared ends by taking the set of all these disjoint intervals
modulo the equivalence relation ∼. The vertices are implicitly realised
as end points or junctions of the glued disjoint intervals.

Remark 3.4. If the graph G contained isolated vertices, then they
would not be represented in G. With minor modifications the theory
presented in this chapter also works if there are isolated vertices. They
were merely excluded to make the presentation a little simpler.

In the remainder of this section, let G be a continuum representation
of G with respect to an orientation (σ, τ ), and let ζ, φ, ψ, and ∼ be
the maps and the equivalence relation from definition 3.2.
Vertices are canonically embedded into G as is done in
Definition 3.5. The map
: V → G,

vertex embedding

σ (e) 7→ [(φ(e), e)]∼ ,
τ (e) 7→ [(ψ (e), e)]∼ ,
vertices V
vertex v

embeds vertices of G into G. Its image is denoted by V and each element
v ∈ V is called vertex.

Remark 3.6. The embedding is well-defined due to the definition of
the equivalence relation ∼.

Edges are canonically embedded into the power set of G as is done
in
Definition 3.7. The map
: E → P (G),

edge embedding

e 7→ ([φ(e), ψ (e)] × {e})/∼,
edges E
edge e

embeds edges of G into G. Its image is denoted by E and each element
e ∈ E is called edge.

At each point of G there is at least one direction to move: In a vertex
of degree k, there are k directions; and on an edge but not in one of its
endpoints, there are 2 directions. An inefficient but immediate way to
represent these directions is as in

set Dir of
directions
direction d on e

Definition 3.8. The set {−1, 1} × E is denoted by Dir, each element
d = (o, e) ∈ Dir is called direction on e, the element o is called orient-

10

ation of d, the involution

orientation o of d

− : Dir → Dir,

orientation
reversing
involution −

(o, e) 7→ (−o, e),
reverses the orientation of directions, and the map
dir : G → P (Dir),
(

[(r, e)]∼ 7→

map dir that
assigns directions

{(−1, e), (1, e)}, if r ∈ ]φ(e), ψ (e)[,
{(− sgn(r0 ), e0 ) | (r0 , e0 ) ∈ [(r, e)]∼ }, otherwise,

assigns to each point in G the set of possible directions in which
someone standing on that point can move.

Remark 3.9. This representation of directions is inefficient in the following sense: If we stand on an edge but not on one of its endpoints,
then the orientation is enough directional information; and if we stand
on a vertex, then the edge is enough directional information, because
the orientation is implicit in the fact that we can only move onto the
edge but not off it since we are in one end of the edge. On a vertex we
do not even need the edge itself but only an identifier for the edge that
is locally unique; for example, we could colour the edges such that no
two edges of the same colour are incident to the same vertex and use
this colour instead.

Like vertices, paths of G are also canonically embedded into G and
each embedding can be unit-speed parametrised by the interval from 0
to the path’s weight as is inductively done in
Definition 3.10. The map
: P → G{[0,r ]|r∈R≥0 } ,
"
#
[0, 0] → G,
(v ) 7→
r 7→ v
"

(σ (e), e, τ (e)) 7→

path embedding

#

[0, ω (e)] → G,

r 7→ [(φ(e) + r, e)]∼ ,
"

(τ (e), e, σ (e)) 7→

#

[0, ω (e)] → G,
r 7→ [(ψ (e) − r, e)]∼ ,



(v0 , e1 , v1 ) • p0 7→ 


[0, ω ((v0 , e1 , v1 ) • p0 )] → G,
(



r 7→




(v0 , e1 , v1 )(r ), if r ≤ ω (e1 ), 


p0 (r − ω (e1 )),

otherwise,

maps paths of G to unit-speed parametrisations of them in G.



Remark 3.11. The base cases of the inductive definition do not overlap
because there are no self-loops, and the inductive step is well-defined
because ω ((v0 , e1 , v1 ) • p0 ) = ω (e1 ) + ω (p0 ).


11

The images P and P consist broadly speaking of paths and directionpreserving paths in G from vertices to vertices that only change direction at vertices. Restricting the parametrisation intervals of paths in
P to subintervals and doing a reparametrisation such that the new
parametrisation starts at 0 yields all direction-preserving paths in G
and is done in
Definition 3.12. The set
{p[r,s] (_ + r ) | p ∈ P and r, s ∈ [0, ω (p)] with r ≤ s}
set P of
directionpreserving paths
p
length ω (p) of p
source σ (p) of p
target τ (p) of p
empty path

is denoted by P ; each element p ∈ P is called direction-preserving
path, the length of the interval dom(p) is called length of p and is
denoted by ω (p), the point σ (p) = p(0) is called source of p, the point
τ (p) = p(ω (p)) is called target of p, and the path p is called empty if
and only if ω (p) = 0.

Remark 3.13. Doing the same with the paths in P does not yield all
paths in G but only those that change direction at vertices and not on
edges. Because we only need direction-preserving paths in what is to
come, we do not define what a general path on G is.

Remark 3.14. Sources and targets of direction-preserving paths in G
are in general not vertices.

The distance between two points is the length of the shortest path
between the points as introduced in
Definition 3.15. The map
d : G × G → R≥0 ∪ {∞},

distance d

(m, m0 ) 7→ inf{ω (p) | p ∈ P with σ (p) = m and τ (p) = m0 }
is called distance, where the infimum of the empty set is infinity.



Remark 3.16. If the graph G is finite and connected, then the distance
map d is a metric. Otherwise, it may not be a metric. For example, if
there are two distinct vertices v, v 0 ∈ V such that, for each n ∈ N+ ,
there is an edge e ∈ E whose weight is 1/n, then the distance of v and
v 0 is 0 although v 6= v 0 . Or, if the graph G is not connected, then there
are two points m, m0 ∈ G whose distance is ∞.

Each non-zero vector of a vector space is uniquely determined by its
magnitude and its direction, and the zero vector is already uniquely
determined by its magnitude, which is 0, and can be thought of as
pointing in every direction, which can be represented by the set of
directions. A generalisation of vector spaces is given in

12

Definition 3.17. Let vry be the set Dir. The set
Arr = {(0, vry)} ∪ (R>0 × Dir)

arrow space Arr

is called arrow space; each element a ∈ Arr is called arrow; the set
vry is called semi-direction; for each element a = (r, d) ∈ Arr, the
real number kak = r is called magnitude of a, and the (semi-)direction
dir(a) = d is called (semi-)direction of a.

Arrow spaces will be used to represent both velocities, which are
directed speeds, and directed distances. Multiplying a velocity by a
time yields a directed distance. This scalar multiplication is introduced
in

arrow a
semi-direction vry
magnitude kak of
a
(semi-)direction
dir(a) of a

Definition 3.18. The map
· : Arr ×R≥0 → Arr,
(
(0, vry), if s = 0,
((r, d), s) 7→
(r · s, d), if s > 0,
is called scalar multiplication.

scalar
multiplication ·



When we stand at the beginning of a non-empty direction-preserving
path and walk along it until we reach its end, we start our walk on the
first edge of the path in a certain direction and we end it on the last
edge of the path in a certain direction. These directions are introduced
in
Definition 3.19. Let p be a direction-preserving path of P . If p is
empty, let dirσ (p) = vry and let dirτ (p) = vry.
Otherwise, there are two edges eσ , eτ ∈ E, which may be the same,
and there are two positive real numbers ξσ , ξτ ∈ ]0, ω (p)] such that
p([0, ξσ ]) ⊆ eσ and p([ω (p) − ξτ , ω (p)]) ⊆ eτ . Moreover, there are
four real numbers rσ , rσ0 , rτ , and rτ0 such that [(rσ , eσ )]∼ = p(0),
[(rσ0 , eσ )]∼ = p(ξσ ), [(rτ , eτ )]∼ = p(ω (p) − ξτ ), and [(rτ0 , eτ )]∼ =
p(ω (p)). Let dirσ (p) = (sgn(rσ0 − rσ ), eσ ) and let dirτ (p) = (sgn(rτ0 −
rτ ), eτ ).
In both cases, the (semi-)direction dirσ (p) is called source direction
of p and the (semi-)direction dirτ (p) is called target direction of p. 
Remark 3.20. The edge eσ is the first edge of the path p and the
edge eτ is its last edge. The numbers ξσ and ξτ are two positive real
numbers such that the first ξσ length units of the path run on its first
edge and the last ξτ length units of the path run on its last edge. The
numbers rσ and rσ0 are the positions of the path on its first edge at its
very beginning and after ξσ length units, and the numbers rτ , and rτ0
are the positions of the path on its last edge ξτ length units before its
end and at its very end. Therefore, the signum of rσ0 − rσ is the start

13

source direction
dirσ (p) of p
target direction
dirτ (p) of p

direction on the first edge of the path and the signum of rτ0 − rτ is the
end direction on the last edge of the path.

Remark 3.21. For each non-empty path p ∈ P , we have dirσ (p) ∈
dir(σ (p)) and dirτ (p) ∈ − dir(τ (p)).

4

event

set Knd
map spd

signal machines

In this section, let G = (V, E, ε) be a non-trivial, finite, and connected
undirected multigraph, let ω be an edge weighting of G, and let M be a
continuum representation of G. Recall that, according to our definition
of undirected multigraphs, there are no self-loops in G. To motivate the
definitions in this section, we talk as if there were a signal machine in
front of us whose time evolution we can observe, although this evolution
is not completely defined until the end of this section.
If you observe the time evolution of a signal machine on the graph M ,
you see signals of different kinds and various speeds each carrying some
data move along edges. When signals collide, they may be reflected,
removed, new signals may be created, and so on. Similarly, when signals
reach a vertex, they may be removed, copies of them may be sent onto
all incident edges, new signals may be created, and so on. You may
also see stationary signals and signals that travel side-by-side at the
same speed. What happens when signals collide or reach a vertex is
decided by two local transition functions, one that handles such events
in vertices and one that handles them on edges.
The only events on edges are collisions. In each collision on an edge,
there are at least two signals involved, the involved signals are either
stationary or they move in one of the two possible directions, and at
least two of the signals collide head-on or rear-end. Such a collision
results in a set of signals that are either stationary or move in one of
the two possible directions.
A vertex may be reached by just one signal or multiple signals may
collide in it. In both cases, there is at least one signal involved, the
involved signals are either stationary or they moved towards the vertex
just before the event, and at least one signal is moving. Such an event
results in a set of signals that are either stationary or move away from
the vertex along incident edges.
Definition 4.1. Let Knd be a set, let spd be a map from Knd to R≥0 ,
let {Dtk }k∈Knd be a family of sets, let

family
{Dtk }k∈Knd

Sgnl = {(k, d, u) | k ∈ Knd , (spd(k ), d) ∈ Arr , and u ∈ Dtk },

set Sgnl
set Dire

let Dire = {{d, −d} | d ∈ Dir}, let
dom(δe ) = {S ∈ P (Sgnl) | ∃ D ∈ Dire : |S| ≥ 2 and

set dom(δe )

∀(k, d, u) ∈ S : d ∈ {vry} ∪ D and

14

∃(k, d, u) ∈ S ∃(k 0 , d0 , u0 ) ∈ S : d 6= d0 or
spd(k ) 6= spd(k 0 )},
let δe be a map from dom(δe ) to P (Sgnl) such that

map δe

∀ S ∈ dom(δe ) ∃ D ∈ Dire : ∀(k, d, u) ∈ S ∪ δe (S ) : d ∈ {vry} ∪ D,
let Dirv = dir(V), let

set Dirv

dom(δv ) = {(D, S ) ∈ Dirv × P (Sgnl) | |S| ≥ 1 and

set dom(δv )

∀(k, d, u) ∈ S : d ∈ {vry} ∪ −D and
∃(k, d, u) ∈ S : spd(k ) > 0},
and let δv be a map from dom(δv ) to P (Sgnl) such that

map δv

∀(D, S ) ∈ dom(δv ) ∀(k, d, u) ∈ δv (D, S ) : d ∈ {vry} ∪ D.
The quadruple S = (Knd, spd, {Dtk }k∈Knd , (δe , δv )) is called signal
machine; each element k ∈ Knd is called kind; for each kind k ∈ Knd,
the non-negative real number spd(k ) is called speed of k and the set
Dtk is called data set of k; each element s ∈ Sgnl is called signal; and
the maps δe and δv are called local transition function on edges and in
vertices respectively.

Remark 4.2. The local transition function δe is used to handle events
on edges but not in their endpoints. It gets the signals that are involved
in the event and returns the resulting signals. Because in each event at
least one moving signal is involved, the direction of this signal and the
map that reverses orientation can be used by δe to determine the two
possible directions the resulting signals may have.
The local transition function δv is used to handle events in vertices.
It gets the directions signals may take at the respective vertex and the
signals that are involved in the event and returns the resulting signals.
The local transition functions δe and δv are supposed to regard directions as black boxes that can merely be distinguished and whose
orientation can be reversed. They must not determine edges or vertices by deconstructing directions, which is possible with the chosen
representation of directions. If they did something like that, the signal
machine would not be uniform.

Remark 4.3. At the beginning of this section we fixed a general multigraph. This multigraph should be regarded as the blueprint of a multigraph. A signal machine depends only on that blueprint and not on
any specific properties that a concrete choice of a multigraph may have.
So, one and the same signal machine can be instantiated for any multigraph, each instantiation results in a machine on a concrete multigraph,
and these instantiations are uniform in the chosen multigraphs. In other
words, a signal machine is a map from the set of all multigraphs to the

15

signal machine S
kind k
speed spd(k ) of k
data set Dtk of k
signal s
local transition
functions δe and
δv on edges and in
vertices

set of quadruples that describe instantiations of the machine on concrete multigraphs and this map depends only in a trivial way on its
argument.
The quadruple that describes signal machines could be made independent of multigraphs by choosing a different representation for directions. They could for example be represented by integers or vectors
or colours equipped with an involution to switch the orientation of
directions.
Even the global transition function, which is introduced below and
describes the time evolution of a signal machine, could be made independent of multigraphs by representing them as patterns in highdimensional Euclidean spaces (think of the drawing of a graph on a
piece of paper). The directions are then vectors that are tangential to
edges.
In classical solutions of the firing squad synchronisation problem the
regions to be synchronised are actually represented as patterns in integer lattices: The cells outside the region are in the same state, say 0,
and all cells inside the region are not in state 0, more precisely, one cell
inside the region is in a state that distinguishes it as the general, say 1,
and the other cells inside the region are all in the same state, say 2. 
In the remainder of this section, let S = (Knd, spd, {Dtk }k∈Knd , (δe ,
δv )) be a signal machine.
To describe the time evolution of our signal machine, the following
notions are convenient.
set T
set T
set Q
set Cnf
time t
improper time
state q
configuration c

kind knd(s) of s
speed spd(s) of s
(semi-)direction
dir(s) of s
velocity vel(s) of s
datum dt(s) of s

Definition 4.4. Let T be the set R≥0 , let T be the set T ∪{∞}, let
Q be the set P (Sgnl), and let Cnf be the set QM . Each element t ∈ T
is called time and the time ∞ is called improper, each element q ∈ Q
is called state, and each element c ∈ Cnf is called configuration.

The components of signals and some compounds of them are named
in
Definition 4.5. Let s = (k, d, u) be a signal of Sgnl. The kind k of s
is denoted by knd(s); the speed spd(k ) of s is denoted by spd(s); the
(semi-)direction d of s is denoted by dir(s); the velocity (spd(k ), d) of
s is denoted by vel(s); and the datum u of s is denoted by dt(s).

Remark 4.6. For each time t ∈ T, the arrow vel(s) · t is equal to the
arrow (spd(k ) · t, d), which can be interpreted as a directed distance. 
Signals of speed 0 are named in

stationary signal

Definition 4.7. Let s be a signal of Sgnl. It is called stationary if and
only if spd(s) = 0.


16

When we stand on a point facing in a direction and from there we
walk a fixed distance without making U-turns but otherwise making
arbitrary choices at each vertex, then there is a finite number of points
that we may reach and we reach them walking in some direction. The
set of these points with and without target-directions is introduced in
Definition 4.8. Let m be a point of M and let (`, d) be an arrow.
The set of points with target-directions that can be reached from m by
a direction-preserving path of length ` with source-direction d is
R→
(`,d) (m) = {(τ (p), dirτ (p)) | p ∈ P , ω (p) = `,

R→
(`,d) (m)

dirσ (p) = d, and σ (p) = m}

and without target-directions it is
R (`,d) (m) = {m0 | ∃ d ∈ Dir : (m0 , d) ∈ R→
(`,d) (m)}.

R (`,d) (m)



An event occurs when a signal reaches a vertex or two signals coming
from different points collide. The time of the next event is given a name
in
Definition 4.9. Let c be a configuration of Cnf. The minimum time
until a signal in c reaches a vertex is
t0 = inf

inf

m∈M s∈c(m)
spd(s)>0

inf{t ∈ R>0 | Rvel(s)·t (m) ∩ V 6= ∅}.

The minimum time until at least two signals in c collide is
t00 =

inf

inf

m,m0 ∈M s∈c(m)
m6=m0 s0 ∈c(m0 )

inf{t ∈ R>0 | Rvel(s)·t (m) ∩ Rvel(s0 )·t (m0 ) 6= ∅}.

The minimum time until the next event(s) in c occurs is t0 (c) =
min{t0 , t00 }.

Remark 4.10. A stationary signal at a vertex does never reach the
vertex (it is already there) and two signals that already are at the
same vertex do never collide (they may have collided when they got
there but now they just are at the same vertex; if they have a nonzero velocity, then they will leave the vertex without interfering each
other, and, if they have the same positive velocity, then they will travel
alongside each other).

Remark 4.11. The next event time may be 0, which means that events
accumulate at time 0, or ∞, which means that there are no more events
in the future; note that inf ∅ = ∞. It is for example 0 if there is a
sequence of signals moving at the same velocity towards the same vertex
each one being already a little closer to the vertex than the previous
one. And it is for example ∞ if there are no signals at all or there are
only stationary signals.


17

next event(s) time
t0 ( c )

If each signal moves with its velocity and upon reaching a vertex
propagates to all incident edges except the one it came from (making
copies of itself if necessary) and if collisions of signals are ignored, then
the set of points an event occurs in at a time in the future is given a
name in
Definition 4.12. Let c be a configuration of Cnf and let t be a time
of T. The set of vertices that signals in c reach at time t (under the
assumptions given in the introduction to the present definition) is

M0 =


∅,




 [

if t = 0,
Rvel(s)·t (m) ∩ V, otherwise.


m∈M



 s∈c(m)

spd(s)>0

The set of points that signals in c collide in at time t is
M 00 =

set Mt (c) of points
that signals in c
are involved in an
event in at time t

[

[

m,m0 ∈M
m6=m0

s∈c(m)
s0 ∈c(m0 )

Rvel(s)·t (m) ∩ Rvel(s0 )·t (m0 ).

The set of points that signals in c are involved in an event in at time t
is Mt (c) = M 0 ∪ M 00 .

Remark 4.13. For times t before and including the time t0 (c) of the
next event, the definition of Mt (c) is natural. And for other times, it is
plausible with the explanation given before the definition and it is used
to handle accumulations of events and accumulations of accumulations
of events and so on.

As above, if each signal moves with its velocity and upon reaching
a vertex propagates to all incident edges except the one it came from
(making copies of itself if necessary) and if collisions of signals are ignored, then starting our signal machine in a configuration c and letting
it run for a time t without handling propagation of signals in vertices
at time t yields a new configuration (t)(c) as defined in
Definition 4.14.

 : T → (Cnf → Cnf ),

map  from T to
Cnf → Cnf

0 7→ idCnf ,
t 7→ [c 7→ [m 7→ {s ∈ Sgnl | ∃ m0 ∈ M ∃ s0 ∈ c(m0 ) :
0
(m, dir(s)) ∈ R→
vel(s0 )·t (m ),

knd(s) = knd(s0 ), and
dt(s) = dt(s0 )}]].



Remark 4.15. For each time t ∈ T and each configuration c ∈ Cnf,
if there is a signal in c that reaches a vertex in time t (or one of its

18

duplicates does), then in the configuration (t)(c) that signal is at
the vertex and its velocity is the one it had just before reaching the
vertex. The direction of that velocity points away from the edge the
signal came from and it does not point to any edge that is incident to
the vertex. It is then up to the local transition function to decide what
to do with the signal and, if it is not removed, what its direction shall
be.

Remark 4.16. The map  is used to determine future configurations
before or right until the next event occurs and needs to be handled,
and also to make crude predictions of future configurations beyond the
next event time by propagating at vertices and ignoring collisions as explained above. These predictions will be used to handle accumulations
of events and accumulations of accumulations of events and so on. 
Until the first events occur, signals move along edges without colliding. At the time the first events occur, a signal reached a vertex
or two signals collided (on a vertex or edge) or multiple such events
happened. An event in a vertex is handled by the local transition function δv and on an edge by δe . This global behaviour can be described
by a map that maps a configuration to the configuration right after the
first events occurred and have been handled. This map is given in
Definition 4.17.
∆
· 0 : Cnf → Cnf,

c 7→


c, if t0 (c) ∈ {0, ∞},



 0



c (m),







[m 7→











map ∆
· 0 from Cnf
to Cnf

if m ∈
/ Mt0 (c) (c),






δv (dir(m), c0 (m)), if m ∈ Mt0 (c) (c) ∩ V, ],






δe (c0 (m)),
if m ∈ Mt0 (c) (c) r V,
otherwise,

where c0 = (t0 (c))(c).



Remark 4.18. The map ∆
· 0 maps a configuration to itself if the next
event time is 0, which means that event times accumulated at 0, or ∞,
which means that there is no next event. And it maps a configuration
to the configuration that is reached after the first events have been
handled, by first using  to determine the configuration in which the
events occur and then handling all occurring events with δv and δe . 
If the next event time is 0, which we call singularity of order −1
(see figure 4.1b), then the machine is sometimes stuck, in the sense
that there is no natural way to define what configuration the machine
is in at any time in the future, and sometimes the machine can go
forward in time, in the sense that there is a natural way to define what

19

singularity of
order −1

singularity of
order 0

singularity of
order j, for
j ∈ N+

configuration the machine is in at least until some time in the future;
the latter case is handled later and largely ignored for now. If the next
event time is ∞, then the machine does nothing for eternity.
Otherwise, the machine can at least proceed until the next event time
and handle the occurring events, which we call singularities of order
0, and then the next event time may again be 0, ∞, or something in
between. It may happen that the next event times are never 0 or ∞
but accumulate at some time in the future, which we call singularity of
order 1 (see figure 4.1a). In that case repeated applications of ∆
· 0 never
reach a configuration at that future time or a time beyond. But we can
in a sense take the limit of the sequence of configurations that repeated
applications of ∆
· 0 yield. Yet, it may even happen that singularities of
order 1 accumulate at some time in the future, which we call singularity
of order 2. Again, we can in the same sense as before take the limit of
the sequence of configurations at these singularities. It may continue
this way ad infinitum. In precise terms this is done in
Definition 4.19. The sequence (tnj−1 )n∈N0 , where the n in tnj−1 is an
upper index and does not stand for exponentiation, the map tj , and
the map ∆
· j , for j ∈ N+ , are defined by mutual induction as follows:
The maps t0 and ∆
· 0 have already been defined and, for each positive
integer j, let
 n
tj−1 : Cnf → T,

n−1

X


map tn
j−1 from
Cnf to T

c 7→






tj−1 (∆
· ij−1 (c)),

i=0

n∈N0

(note that t0j−1 = 0), let
tj : Cnf → T,

map tj from Cnf
to T

c 7→ lim tnj−1 (c),
n→∞

and let
∆
· j : Cnf → Cnf,

map ∆
· j from Cnf
to Cnf

c 7→



c, if tj (c) ∈ {0, ∞},








c0 (m),





[m 7→











if m ∈
/ Mj ( c ) ,






δv (dir(m), c0 (m)), if m ∈ Mj (c) ∩ V, ],





δe (c0 (m)),
if m ∈ Mj (c) r V,
otherwise,

where c0 = lim inf (tj (c) − tnj−1 (c))(∆
· nj−1 (c)),
n→∞

and Mj (c) = lim inf Mtj (c)−tnj−1 (c) (∆
· nj−1 (c)),
n→∞

where the first limit inferior is the pointwise limit inferior of sequences
of set-valued maps and the second limit inferior is the limit inferior

20

(a) A singularity of order 1.

(b) A singularity of order −1.

Figure 4.1: Both subfigures depict a space-time diagram of the time evolution of an unspecified
signal machine, where space is drawn on the horizontal axis and time on the vertical axis
evolving from top to bottom. In figure 4.1a, there are infinitely many signals of various
speeds arbitrarily close to 0 and slower than 1 emanating from the left vertex, the fastest
signal, which is the one of speed 1, is reflected at the right vertex, and the reflected
signal collides with all other signals at shorter and shorter time spans between collisions,
resulting in a singularity of order 1 at the last depicted time. In figure 4.1b, there are
infinitely many signals of various speeds arbitrarily close to 0 and slower than 1 emanating
to the right from the middle vertex, and there is one signal of speed 1 emanating to the
left from the middle vertex, this signal is reflected at the left vertex, and at the time the
reflected signal reaches the middle vertex is a singularity of order −1 because it collides
with all signals that emanated to the right and are arbitrarily close to the vertex.

21

of sequences of sets. In greater detail, for each sequence (cn )n∈N0 of
set-valued maps from M to Q, the pointwise limit inferior of (cn )n∈N0
is the map c : M → Q, m 7→ lim inf n→∞ cn (m) and is denoted by
lim inf n→∞ cn ; and, for each sequence (An )n∈N0 of subsets of M , the
S
T
limit inferior of (An )n∈N0 is the subset n∈N0 k≥n Ak of M and is
denoted by lim inf n→∞ An .

Remark 4.20. Let c be a configuration of Cnf. Then, for each positive
integer j, we have t0j−1 (c) = 0 and t1j−1 (c) = tj−1 (c), and the sequence
(tnj−1 (c))n∈N0 in T is non-decreasing and hence converges in T. And,
the sequence (tj (c))j∈N0 in T is non-decreasing and hence converges in
T.

Remark 4.21. Let the signal machine be in a configuration c at time
0 and let there be no future configuration whose next event time is 0 or
∞. The latter is the case if and only if the sequences (tnj−1 (c))n∈N0 , for
j ∈ N+ , and hence also the sequence (tj (c))j∈N0 , are strictly increasing
sequences in T.
Then, for each positive integer j and each non-negative integer n, at
time tnj−1 (c) the machine is in configuration ∆
· nj−1 (c). And, the time
tn0 (c) is the n-th time an event occurs (singularity of order 0), the time
tn1 (c) is the n-th time an accumulation of events occurs (singularity of
order 1), the time tn2 (c) is the n-th time an accumulation of accumulation of events occurs (singularity of order 2), and so forth.
Moreover, for each non-negative integer j, at time tj (c) the machine
is in configuration ∆
· j (c). And, the time t0 (c) is the next time an event
occurs, the time t1 (c) is the next time an accumulation of events occurs,
the time t2 (c) is the next time an accumulation of accumulations of
events occurs, and so forth.
Furthermore, for each positive integer j, the map ∆
· j maps the configuration c to the configuration that is reached after an accumulation of
singularities of order j − 1, which is a singularity of order j. First, it calculates the configurations that accumulate, namely ∆
· nj−1 (c); secondly,
for each of these configurations, it uses  to determine the configuration that would be reached at the accumulation time if there were no
further events, which is a crude prediction of the future that becomes
better the greater n is; thirdly, it calculates the pointwise limit inferior
of these configurations, which is essentially the configuration that contains the signals that all but finitely many of the configurations have
in common (in particular, if for a point m the sequence of signals at m
become constant, then the limit at m is that set of signals); lastly, it
handles collisions.

Remark 4.22. Let the signal machine be in a configuration c at time 0
and let there be a future configuration whose next event time is 0. Then,
there is a least positive integer j such that the sequence (tnj−1 (c))n∈N0

22

is eventually constant. And, there is a least non-negative integer n such
+1
that tnj−1 (c) = tnj−1
(c). The time t0 = tnj−1 (c) is the first time at which
the signal machine is in a configuration whose next event time is 0 and
this configuration is c0 = ∆
· nj−1 (c).
0
For each non-negative integer n0 such that n0 ≥ n, we have tnj−1 (c) =
0
t0 and ∆
· nj−1 (c) = c0 . And, for each positive integer j 0 such that j 0 ≥ j,
the time tj 0 (c) is equal to t0 and the configuration ∆
· j 0 (c) is equal to
n
0
n
c , and the sequences (tj 0 (c))n∈N0 and (∆
· j 0 (c))n∈N0 are the constant
sequences (t0 )n∈N0 and (c0 )n∈N0 . In particular, the limit limj→∞ tj (c)
is equal to t0 and the limit inferior lim inf j→∞ ∆
· j (c) is equal to c0 . 
Remark 4.23. The limit of sequences of configurations and of sets of
points does in general not exist. However, the limit inferior and the
limit superior always exist. We decided not to use the limit, to avoid
case distinctions that would have to be made. Instead, we decided to
use the limit inferior; we could as well have decided to use the limit
superior. Which of the two has the desired outcome depends on the
specific use case.
For the signal machine that solves the firing squad synchronisation
problem that we construct in the next section and the configurations it
is initialised with and the configurations it encounters during its time
evolution, the encountered limit inferiors and superiors are actually
always the same, which means that the limits exist, and hence the
choice of limit inferior or superior is irrelevant in that use case.

If the machine never assumes a configuration in which events accumulate at time 0 and if non-negative singularities of ever higher orders
ad infinitum do not accumulate, then the machine can be observed for
eternity. Otherwise, it can for now only be observed for all times before
limj→∞ tj (c), where c is the initial configuration of the machine. This
time is given a name in
Definition 4.24. For each configuration c ∈ Cnf, the non-negative
real number or infinity t∞ (c) = limj→∞ tj (c) is called ∞-existence time
of c, and the closed interval [0, t∞ (c)] is called ∞-existence interval of
c.

Repeated applications of powers of the maps ∆
· j , for decreasing j ∈
N0 , let us jump to and from configurations right after singularities of
decreasing orders. The resulting map is given a name in

∞-existence time
t∞ (c) of c
∞-existence
interval [0, t∞ (c)]
of c

Definition 4.25. For each non-negative integer j, each non-negative
integer k, and each finite sequence (ni )ki=j of non-negative integers, let
(

∆
· (ni )k

i=j

=

if j > k,

idCnf ,
n
∆
· jj

n
◦∆
· j +j +11

◦···◦∆
· nk k ,

map ∆
· (ni )k from
i=j
Cnf to Cnf

otherwise,

23

and let
t(ni )k

map t(ni )k from
i=j
Cnf to T

=

i=j

k
X
tni i ◦ ∆
· (n )k
.
` `=i+1



i=j

Remark 4.26. Let the signal machine be in a configuration c at time
0 and let there be no future configuration whose next event time is 0 or
∞. The map ∆
· (ni )k applied to c, first applies ∆
· nk k to jump from c to
i=j

the configuration right after the nk -th time a singularity of order k ocnk−1
to jump from that configuration, namely
curs, secondly it applies ∆
· k−1
∆
· (ni )k (c), to the configuration right after the nk−1 -th time a singulari=k
ity of order k − 1 occurs (counting from the time at which the machine
n
is in configuration ∆
· (ni )k (c)), and so forth until it finally applies ∆
· jj
i=k
to jump from the configuration ∆
· (ni )k
(c) to the configuration right
i=j +1

after the nj -th time a singularity of order j occurs (counting from the
time at which the machine is in configuration ∆
· (ni )k
(c)), where in
i=j +1

the case that j = 0, a singularity of order 0 is nothing but an event.
The time it takes the machine to get from c to the configuration
nk−1
∆
· nk k (c) is tnk k (c), the time it takes to get from ∆
· nk k (c) to ∆
· k−1
(∆· nk k (c))
nk−1
is tk−1
(∆· nk k (c)), and so forth; in total, the time it takes to get from c
to ∆
· (ni )k (c) is t(ni )k (c).

i=j

i=j

To compute the configuration the machine is in at the ∞-existence
time of the initial configuration, we can use the maps ∆
· j for increasing j
to jump from singularities of non-negative lower orders to singularities
of ever higher orders, which in the case there are any singularities of
order −1 comes to a halt at the first such singularity at the ∞-existence
time and in the other case yields in a sense the limit configuration. And,
to compute the configuration at time t before the ∞-existence time, we
can use one of the maps ∆
· (ni )k to jump to the configuration right after
i=0
the last event before time t and then we can use the map  to jump
from there to time t. The resulting map describes the time evolution
of the signal machine before or at ∞-existence times and it is given in
Definition 4.27. For each time t ∈ T, the set of configurations whose
∞-existence interval contains t is
Cnf ∞
t = {c ∈ Cnf | t ≤ t∞ (c)}.

set Cnf ∞
t

Let
:T→

from T to
(Cnf ∞
t →
t∈T
Cnf )

map
S

[
t∈T

24

(Cnf ∞
t → Cnf ),

Cnf ∞
t → Cnf,


· j (c),

lim inf ∆

j→∞

c 7→

(t − t
(c))(∆· (ni )k (c)),
t 7→ 
(ni )k










if t = t∞ (c), 




otherwise, 

i=0
i=0

k
k +1 

for the least k ∈ N0 and the (ni )i=0 ∈ N0


with t ∈ [t(ni )k (c), t(n0 +1,n1 ,n2 ,...,nk ) (c)[.
i=0

Note that the least index k and the finite sequence (ni )ki=0 that occur
above are uniquely determined by the time t and the configuration
c.

Remark 4.28. In the second case in the definition of , we have
nk−1 +1
nk−1
(∆· nk k (c)), tk−1
(∆· nk k (c))[,
t ∈ [tnk k (c), tnk k +1 (c)[, and t − tnk k (c) ∈ [tk−1
and so forth.

Remark 4.29. For each configuration c ∈ Cnf, the map
defined on the closed interval [0, t∞ (c)].

(_)(c) is


Remark 4.30. Let t be a time of T and let c be a configuration of
Cnf ∞
t such that t 6= t∞ (c). If events do not accumulate for the initial
configuration c, then (t)(c) = (t − tn0 0 (c))(∆
· n0 0 (c)), for the n0 ∈ N0
with t ∈ [tn0 0 (c), tn0 0 +1 (c)[; in words, we apply ∆
· 0 repeatedly, jumping
from event to event, until we reach the configuration ∆
· n0 0 (c) at time
tn0 0 (c) with the property that the next event (if there even is one) occurs
after t, at which point we use  to move signals along edges for the
remaining time t − tn0 0 (c).
If events do accumulate for c but singularities of order 1 do not
accumulate, then we apply ∆
· 1 repeatedly, jumping from singularity to
singularity, until we reach the configuration ∆
· n1 1 (c) at time tn1 1 (c) with
the property that the next singularity (if there even is one) occurs after
t, at which point we apply ∆
· 0 repeatedly, jumping from event to event,
until we reach the configuration ∆
· n0 0 (∆
· n1 1 (c)) at time tn0 0 (c) + tn1 1 (c)
with the property that the next event (if there even is one) occurs after
t, at which point we use  to move signals along edges for the remaining
time t − tn0 0 (c) − tn1 1 (c).
And so forth.

Remark 4.31. Let the signal machine be in a configuration c at time
0. If there is a singularity of order −1 in the future, then, according
to remark 4.22, the time t∞ (c) is the first time at which the signal
machine is at such a singularity and the corresponding configuration is
(t∞ (c))(c). Otherwise, the time t∞ (c), which may be the improper
time ∞, is the time just after all singularities and the corresponding
configuration is (t∞ (c))(c). In either case, in what is to come, for
simplicity, if t∞ (c) is finite, then we talk as if there is a singularity of
order −1 at time t∞ (c).


25

At the time of a singularity of order 1, there are infinitely many
events that occur just before that time and arbitrarily close to it, and
the problem is to define the configuration at the time of the singularity.
At the time of a singularity of order −1, there are infinitely many
events that occur just after that time and arbitrarily close to it, and the
problem is to define the configurations at all times after the singularity.
Analogous problems exist for accumulations of singularities of order 1
or −1, and accumulations of accumulations of singularities of order 1
or −1, and so forth. For singularities of positive orders these problems
have been solved above but not for singularities of order −1 and its
accumulations.
At a singularity of order −1 at time 0, to compute the configuration
at a small enough time t, first, we make crude predictions of the future
with  by jumping past the singularity to future times ε ignoring events,
secondly, we extrapolate these predictions to the time t with
by
letting the machine evolve them until the time t, and, lastly, we take
the limit inferior of these predictions as ε tends to 0. This does not work
for all singularities of order −1 regardless of how small we choose t (for
example if at each point in time of a time span after and including 0
an event occurs), but it does work for the singularities of order −1 that
occur in our quasi-solution of the firing squad synchronisation problem.
If the ∞-existence time of the current configuration is ∞, then the
machine can be observed for eternity. Otherwise, it can be observed
until the ∞-existence time using
and from there at least until the
least time until which all the crude predictions mentioned above can
be observed; this time span is named in
Definition 4.32.
t−1 : Cnf → T,

if t∞ (c) = ∞,
∞,
c 7→
 inf ((ε + t∞ (c)) + t∞ (cε )), otherwise,

map t−1 from Cnf
to T

ε∈R>0

where cε = (ε)( (t∞ (c))(c)).



How the machine evolves until and beyond t∞ and at most until t−1
is given in
Definition 4.33. For each time t ∈ T, let
Cnf −1
t = {c ∈ Cnf | t ≤ t−1 (c)}

set Cnf −1
t

and let
: T →

map
T to
S  from−1
(
Cnf
t →
t∈T
Cnf )

26

[
t∈T

(Cnf −1
t → Cnf ),

Cnf −1
t → Cnf,




if t ≤ t∞ (c), 
 (t)(c),


t 7→ 
c 7→ lim inf (t − (ε + t (c)))(c ), otherwise, 



∞
ε




ε↓0





where cε = (ε)( (t∞ (c))(c)),
where the limit inferior is the pointwise limit inferior of set-valued maps,
in greater detail, for each family {cε }ε∈R>0 of set-valued maps from M
to Q, the pointwise limit inferior lim inf ε↓0 cε is the map c : M → Q,
S
T
m 7→ r∈R>0 s≥r c1/s (m).

Remark 4.34. For each configuration c ∈ Cnf, we have t∞ (c) ≤
−1
t−1 (c); for each time t ∈ T, we have Cnf ∞
t ⊆ Cnf t ; and for each configuration c ∈ Cnf and each positive real number ε, we have t−1 (c) −
(ε + t∞ (c)) ≤ t∞ (cε ).

Remark 4.35. Let the signal machine be in a configuration c at time
0. If t∞ ( (t∞ (c))(c)) = 0, then there is a singularity of order −1 at
time t∞ (c). Otherwise, there is not. In the latter case, as one would
hope, t−1 (c) = t∞ ( (t∞ (c))(c)), and, for each time t ∈ [t∞ (c), t−1 (c)],
we have (t)(c) = (t − t∞ (c))( (t∞ (c))(c)).

Unlike for a singularity of a non-negative order, for a singularity of
order −1 it is not possible to jump to the time right after the singularity
as there is no such time. However, we may jump over the singularity at
time t∞ to the time t−1 . This is done by the map
Definition 4.36.
∆
· −1 : Cnf → Cnf,
(
c,
if t∞ (c) = ∞,
c 7→
(t−1 (c))(c), otherwise. 

map ∆
· −1 from
Cnf to Cnf

Like for singularities of non-negative orders, such of order −1 may
accumulate, which is a singularity of order −2, such of order −2 my
accumulate, which is a singularity of order −3, and so forth. The map
to jump over singularities of order −1 has already been given and the
maps to jump over singularities of smaller orders are introduced in

singularity of
order −j, for
j ∈ Z≥2

Definition 4.37. The sequence (tn−(j−1) )n∈N0 , where the n in tn−(j−1)
is an upper index and does not stand for exponentiation, the map t−j ,
and the map ∆
· −j , for j ∈ Z≥2 , are defined by mutual induction as
follows: The maps t−1 and ∆
· −1 have already been defined and, for each
integer j such that j ≥ 2, let
 n
t−(j−1) : Cnf → T,

n−1

X


c 7→

i=0



t−(j−1) (∆
· i−(j−1) (c)),





map tn
−(j−1) from
Cnf to T

n∈N0

27

(note that t0−(j−1) = 0), let
t−j : Cnf → T,

map t−j from Cnf
to T

c 7→ lim tn−(j−1) (c),
n→∞

and let
∆
· −j : Cnf → Cnf,

map ∆
· −j from
Cnf to Cnf

c 7→


c, if t−j (c) = ∞,




lim inf (t−j (c) − tn−(j−1) (c))(∆
· n−(j−1) (c)),

n→∞




otherwise.



The machine can be observed for all times before limj→∞ t−j (c),
where c is the initial configuration of the machine. This time is given a
name in

(−∞)-existence
time t−∞ (c) of c
(−∞)-existence
interval
[0, t−∞ (c)] of c

Definition 4.38. For each configuration c ∈ Cnf, the non-negative
real number or infinity t−∞ (c) = limj→∞ t−j (c) is called (−∞)-existence
time of c, and the closed interval [0, t−∞ (c)] is called (−∞)-existence
interval of c.

Like for singularities of non-negative orders, repeated applications of
powers of the maps ∆
· −j , for decreasing j ∈ N+ , let us jump over singularities of decreasing negative orders down to order −1. The resulting
map is given a name in
Definition 4.39. For each positive integer j, each non-negative integer k, and each finite sequence (ni )−k
i=−j of non-negative integers that
is indexed from −j down to −k, let
(

∆
· (ni )−k

map ∆
· (n )−k
i i=−j
from Cnf to Cnf

i=−j

=

if −j < −k,

idCnf ,
n
∆
· −j−j

n−j−1
◦∆
· −j−1

n−k
◦···◦∆
· −k
,

otherwise,

and let
t(ni )−k

map t(n )−k from
i i=−j
Cnf to T

i=−j

−k
X
· (n )−k .
=
tni i ◦ ∆
` `=i−1



i=−j

Like for singularities of non-negative orders, to compute the configuration the machine is in at the (−∞)-existence time of the initial
configuration, we can use the maps ∆
· −j for increasing j to jump from
singularities of negative lower orders to singularities of ever higher orders ad infinitum. And, to compute the configuration at time t before
the (−∞)-existence time, we can use one of the maps ∆
· (ni )−k to jump
i=−1
over all the singularities before time t such that the next jump over a
singularity of order −1 would be beyond time t and then we can use

28

the map  to jump from there to time t whereby we may cross a singularity of order −1. The resulting map describes the time evolution
of the signal machine before or at (−∞)-existence times, which for the
purposes of this treatise is the complete time evolution, and this map
is given in
Definition 4.40. For each time t ∈ T, the set of configurations whose
(−∞)-existence interval contains t is
Cnf −∞
= {c ∈ Cnf | t ≤ t−∞ (c)}.
t

set Cnf −∞
t

The map
: T →

[

(Cnf −∞
→ Cnf ),
t

global transition
function  from T
to
S
(Cnf −∞
→
t
 t∈T
Cnf )

t∈T







t→
7 






Cnf −∞
→ Cnf,
t
c 7→



· −j (c), if t = t−∞ (c),
 lim inf ∆
j→∞





  (t − t
(c))(∆· (ni )−k (c)), otherwise, 
(ni )−k

i=−1
i=−1

−k
k 
for the least k ∈ N+ and the (ni )i=−1 ∈ N0 


with t ∈ [t(ni )−k (c), t(n−1 +1,n−2 ,n−3 ,...,n−k ) (c)[,
i=−1

is called global transition function.



Remark 4.41. Jérôme Olivier Durand-Lose introduces and studies another notion of signal machines in his paper ‘The signal point of view:
from cellular automata to signal machines’[Dur08]. The notable differences are the following: While our machines are defined over continuum
graphs, his machines are defined over the real number line; while our
machines may have infinitely many different kinds of signals, his machines may only have signals of a finite number of kinds (which he calls
meta-signals); while in a configuration of our machines there may exist
infinitely many signals (even at the same point), in configurations of
his machines there may only exist finitely many signals; while the time
evolution of our machines can be observed beyond singularities of any
order, the time evolution of his machines already stops before singularities of order 1, that is, before accumulations of collisions (as there are
no vertices, other events do not exist for his machines).

5

firing squad signal machines

In this section, let G = (V, E, ε) be a non-trivial, finite, and connected
undirected multigraph, let ω be an edge weighting of G, let M be a
continuum representation of G, and let g be a vertex of M , which we
call general. When we say path, we either mean path in G or path in M ;
when we say longest path, we either mean maximum-weight path in G
or longest path in M ; and, when we say path, we often mean non-empty

29

general vertex g

direction-preserving path from vertex to vertex; in all cases it should be
clear from the context what is meant.
From a broad perspective, the signal machine we construct in this
section performs the following tasks: It cuts the graph such that the
graph turns into a virtual tree; it starts synchronisation of edges as
soon as possible and freezes it as late as possible; it determines the
midpoints of all non-empty direction-preserving paths from vertices
to vertices; it determines which midpoints are the ones of the longest
paths; starting from the midpoints of the longest paths, it traverses
midpoints of shorter and shorter paths and upon reaching midpoints of
edges, it thaws synchronisation of the respective edges; all edges finish
synchronisation at the same time with the creation of fire signals that
lie dense in the graph (see figures 5.1 to 5.5). A more detailed account
is given in
Remark 5.1.
a. Turn the graph into a tree: Initiate signals of speed
1 spread from the general throughout the graph without making
U-turns and vanish at leaves. When they collide on an edge but
not in one of its ends, the edge is cut in two at the point of
collision by two stationary leaf signals (also called virtual leaves),
one for each of the two new ends. When they collide in a vertex
coming from all incident edges, all edges are cut off by leaf signals;
and when the do not come from all incident edges, all but one
of the edges the signals come from are cut off. In the latter case,
the initiate signal that comes from the edge that is not cut off
spreads onto the edges from which no initiate signals came.
In this way all cycles are eventually broken up and the graph is
turned into a virtual tree. Because the virtual leaves are created
as soon as possible and because they are treated just like normal
leaves, we may and will assume in the description of the other
tasks that the graph is a tree.
b. Start and freeze synchronisation of edges (see figure 5.2): When
initiate signals reach a vertex, for each incident edge, synchronisation of the edge is started from the vertex immediately and
freezing of this synchronisation is started from the midpoint of
the edge after 3/2 times the edge’s length time units by sending
freeze signals of speed 1 to both ends of the edge and finishes
after twice times the edge’s length time units.
Each edge is synchronised by recursively dividing it into two parts,
one having two-third its length and the other having one-third
its length. This division procedure becomes finer and finer, in
other words, divisions accumulate, the closer the time evolution
gets to the time 2 times the edge’s length after of the edge’s
synchronisation started.

30

(a)

(b)

Figure 5.1: Both subfigures depict a space-time diagram of the time evolution of the signal machine
that we construct in section 5. The diagram in figure 5.1a illustrates how, beginning
from one end of an edge, the midpoint of the edge is found, which works analogously for
paths instead of edges, and the diagram in figure 5.1b illustrates how, beginning from the
inner vertex of a path consisting of two edges, the midpoint of the path is found, which
works analogously for longer paths; above the right space-time diagram is a scaled-down
depiction of the two-edged path. Vertices are thick and solid lines; find-midpoint signals
of speed 1 are thick and dotted lines; reflected find-midpoint signals of speed 1 are densely
dotted lines; slowed-down find-midpoint signals of speed 1/3 are solid lines; stationary
midpoint signals are thick and solid lines.

31

(a)

(b)

Figure 5.2: Both subfigures depict a space-time diagram of the time evolution of the signal machine
that we construct in section 5. The diagram in figure 5.2a illustrates how, beginning
from one end of an edge, the edge is synchronised by recursively dividing it into two
parts, where one part is two-thirds the superpart’s length and the other part is one-third
the superpart’s length, and creating fire signals when reflected divide signals reach the
boundaries they originated at, which happens for all at the same time and these fire
signals lie dense in the edge. And, the diagram in figure 5.2b illustrates how, beginning
from the inner vertex of a path consisting of two edges, the path is synchronised by
synchronising both edges, freezing the synchronisation of individual edges as late as
possible and thawing it as early as possible such that both edges finish at the same time.
Note that in both subfigures, at each boundary, there is a singularity of order 1 at the
last depicted time, and in figure 5.2b, there are additional singularities of order 1 at time
twice the longer edge’s length and at time twice the shorter edge’s length, and of order
−1 at various points of the freeze and thaw signals. Only the most relevant signals are
depicted and these only for the most relevant time spans. Initiate signals, divide signals
of type 0, and find-midpoint signals, all of speed 1, are solid lines; reflected divide signals
and reflected find-midpoint signals, both of speed 1, are solid lines; divide signals of type
n ∈ N+ , which have speed (2/3)n /(2 − (2/3)n ), are densely dotted lines; slowed-down
find-midpoint signals of speed 1/3 are solid lines; stationary boundary and midpoint
signals are thick and solid lines; freeze signals of speed 1 are dashed lines; thaw signals
of speed 1 that do not thaw synchronisation of the edge they are on are thick and loosely
32and the other thaw signals of speed 1 are dashed lines.
dotted lines,

(a)

(b)

Figure 5.3: Both subfigures depict the space-time diagram of the time evolution of the signal machine
that we construct in section 5 for the scaled-down depicted tree with two edges, beginning
with the initial configuration for the firing squad synchronisation problem — which is
the configuration in which initiate signals, find-midpoint signals, and slowed-down findmidpoint signals emanate from the general onto all incident edges — and ending with
the final configuration of the problem — which is the configuration in which the fire
signals lie dense in the multigraph —, where in figure 5.3a the general is the vertex that
is incident to both edges and in figure 5.3b it is the leaf of the longer edge. Only the most
relevant signals are depicted and these only for the most relevant time spans. Initiate
signals and find-midpoint signals, which in the depicted cases always travel alongside
each other, are thick and dotted lines; reflected find-midpoint signals are densely dotted
lines; slowed-down find-midpoint signals are solid lines; midpoint signals are thick and
solid lines; freeze signals are dashed lines; thaw signals that do not thaw synchronisation
of the edge they are on are thick and loosely dotted lines, and the other thaw signals are
dashed lines. The synchronisation of individual edges, before it is frozen and after it is
thawed, is schematically represented by hatch patterns.

33

Figure 5.4: The figure depicts the space-time diagram of the time evolution of the signal machine that
we construct in section 5 for the tree with three edges depicted on the right, beginning
with the initial configuration for the firing squad synchronisation problem — which is
the configuration in which initiate signals, find-midpoint signals, and slowed-down findmidpoint signals emanate from the general onto all incident edges — and ending with
the final configuration of the problem — which is the configuration in which the fire
signals lie dense in the multigraph —, where the general is the second vertex from the
left. Only the most relevant signals are depicted and these only for the most relevant time
spans. Initiate signals and find-midpoint signals are thick and dotted lines; reflected findmidpoint signals are densely dotted lines; slowed-down find-midpoint signals are solid
lines; midpoint signals are thick and solid lines; freeze signals are dashed lines; thaw
signals that do not thaw synchronisation of the edge they are on are thick and loosely
dotted lines, and the other thaw signals are dashed lines. When a midpoint is found and
when the corresponding midpoint signal collides with a matching thaw signal, the path
it is the midpoint of is represented by the colours of the path’s edges in a little disk or
rounded rectangle. The synchronisation of individual edges, before it is frozen and after
it is thawed, is schematically represented by hatch patterns.

34

(a)

(b)

Figure 5.5: Both subfigures depict the space-time diagram of the time evolution of the signal machine that we construct in section 5 for the scaled-down depicted tree with three edges,
beginning with the initial configuration for the firing squad synchronisation problem —
which is the configuration in which initiate signals, find-midpoint signals, and sloweddown find-midpoint signals emanate from the general onto all incident edges — and
ending with the final configuration of the problem — which is the configuration in which
the fire signals lie dense in the multigraph. In figure 5.5a the general is the one that is
incident to all edges; and in figure 5.5b it is the leaf of the shortest edge. Only the most
relevant signals are depicted and these only for the most relevant time spans. Each edge
has a colour, leaves are coloured according to the edge they are incident to, and signals
and hatch patterns are coloured according to the edge they are on. The shortest edge is
depicted twice, once coloured red and overlaying the green edge, and once coloured violet
and overlaying the blue edge; this makes it easier to follow signals that travel from or onto
the shortest edge. Initiate signals and find-midpoint signals, which in the depicted cases
always travel alongside each other, are thick and dotted lines; reflected find-midpoint signals are densely dotted lines; slowed-down find-midpoint signals are solid lines; midpoint
signals are thick and solid lines; freeze signals are dashed lines; thaw signals that do not
thaw synchronisation of the edge they are on are thick and loosely dotted lines, and the
other thaw signals are dashed lines. When a midpoint is found and when the corresponding midpoint signal collides with a matching thaw signal, the path it is the midpoint of
is represented by the colours of the path’s edges in a little disk. The synchronisation of
individual edges, before it is frozen and after it is thawed, is schematically represented
by hatch patterns.
35

The division of one part is performed by sending divide signals
of speed (2/3)n /(2 − (2/3)n ), for n ∈ N0 , from one boundary
onto the part, reflecting the divide signal of speed 1 at the other
boundary, and, upon collision of the reflected divide signal with a
divide signal, letting the reflected divide signal move on, removing
the involved divide signal, creating a stationary boundary signal
and sending divide signals of the above speeds onto the newly
created part the reflected divide signal comes from.
c. Determine the midpoints of all direction-preserving paths from
vertices to vertices (see figure 5.1): The general and initiate signals that reach vertices send find-midpoint signals of speed 1 and
slowed-down find-midpoint signals of speed 1/3 in all directions
to determine the midpoints of all paths that contain the general
and the reached vertex respectively. These signals spread throughout the graph without making U-turns memorising the paths they
take and (fast) find-midpoint signals are additionally reflected.
Reflected find-midpoint signals of speed 1 take the paths back
they took before being reflected memorising the path to the vertex they were reflected at and the remaining path they have to
take. Upon finishing their path at the vertex they originated at,
slowed-down find-midpoint signals of speed 1/3 are sent onto all
edges except the one the reflected signal comes from, they memorise the path from the origin vertex to the reflection vertex of the
reflected find-midpoint signal, and they spread throughout the
graph without making U-turns memorizing the paths they take
and vanish at leaves.
When a reflected find-midpoint signal collides with a slowed-down
find-midpoint signal that originated at the same vertex, the point
of collision is the midpoint of the concatenation of the paths the
two signals took after being reflected, that is, the path from the
vertex the reflected find-midpoint signal was reflected at over the
point of collision over the vertex both signals originated at to
the vertex the reflected find-midpoint signal that spawned the
slowed-down find-midpoint signal was reflected at. Each midpoint
is designated by a stationary midpoint signal that memorises the
path it is the midpoint of along with its position on the path.
When a reflected find-midpoint signal collides with a reflected
find-midpoint signal that originated at the same vertex and the
point of collision is the origin vertex itself, both reflection vertices
have the same distance to the origin vertex and this vertex is the
midpoint of the concatenation of the paths the two signals took
after being reflected.
To get a clearer picture of how midpoints are determined, let us focus on only a few signals and let us ignore boundary cases: When
an initiate signal reaches a vertex, one find-midpoint signal is sent

36

along one incident edge, and another find-midpoint signal is sent
along another incident edge. Both signals travel along edges and
upon reaching a vertex they are either reflected and travel back
or they take one of the incident edges that leads them further
away. At the latest, they are reflected upon reaching a leaf. One
of the reflected find-midpoint signals returns first to the vertex
it originated at, is slowed down there, and the slowed down signal travels towards the other (reflected) find-midpoint signal. At
some time in the future, the slowed-down find-midpoint signal
collides with the other, now reflected, find-midpoint signal and
the point of collision is the midpoint of the concatenation of the
paths the two signals took after being reflected.
d. Determine the midpoints of the longest direction-preserving paths
(see figures 5.3 and 5.4): The midpoints of the longest paths are
eventually found. But this is not sufficient, they also need to be
recognised as such. To that end, each reflected find-midpoint signal and each slowed-down find-midpoint signal carries a boolean
that indicates whether the path it took from the vertex it was
reflected at may be the subpath of a longest path that has the
same source (or target), and whether the signal would be the first
one to find the longest path’s midpoint (recall that a slowed-down
find-midpoint signal was either spawned by the general vertex or
an initiate signal that reached a vertex, in which case we can
think of this vertex as the one the slowed-down find-midpoint signal was reflected at; or it was originally a reflected find-midpoint
signal and knows where that signal was reflected at). Let us call
signals that carry the boolean yes marked and the others not.
At each vertex that is not a leaf, a stationary count signal memorises the directions from which marked reflected find-midpoint
signals that originated at the vertex or from which marked sloweddown find-midpoint signals with any origin have already returned.
Because longest paths always end at leaves, for each leaf, findmidpoint signals are marked when they are the first ones to be
reflected at the leaf and not otherwise. When a marked signal
reaches a vertex, it stays marked, if, including itself, from all but
one direction have marked signals already returned (which is the
case if and only if it is the last signal to return from its direction
and the penultimate signal to return among such signals from
either direction), and it is unmarked, otherwise.
This means that a marked reflected find-midpoint signal is unmarked, if there are at least two other signals that started out
at the same time at the same vertex but take longer to return
(because they have a longer way; the combined paths that two
of the other signals take may be a longest path), and it stays
marked, if all other signals except for one that all started out at

37

the same time at the same vertex returned earlier (because they
had a shorter way).
And it means that a marked slowed-down find-midpoint signal is
unmarked, if it is unclear which of the incident edges belong to
longest paths, and it stays marked, otherwise, which is the case
if from precisely one direction no slowest reflected find-midpoint
signal that originated at the vertex has returned yet. This is not
only pessimistic, meaning that we do not falsely consider midpoints of paths that are not among the longest as such, but also
correct, meaning that we still find the midpoints of all longest
paths in time (see section 6.2).
When a marked reflected find-midpoint signal reaches its origin
and is the penultimate such signal to do so, it turns into a marked
slowed-down find-midpoint signal that travels in the one direction
from which no marked signal has returned yet and the point at
which this signal collides with the one signal that has not yet
returned will be the midpoint of a longest path, if both signals
are still marked at the time of collision.
e. Traverse midpoints, thaw synchronisation of edges, and fire (see
figures 5.4 and 5.5): The midpoints of the longest paths are found
at the same time, at which, from each such midpoint, two thaw
signals of speed 1 are sent that travel along the midpoint’s path
towards both of its ends. When a thaw signal collides with the
midpoint of a path such that one of the two subpaths from the
midpoint to either end of the path coincides with the remaining
path the thaw signal travels along, an additional thaw signal is
created that travels along the other subpath. On its way from the
midpoint of the last edge of the path a thaw signal travels on to
the end of the path, the thaw signal thaws all frozen signals it
collides with. All thaw signals reach the ends of their paths at the
same time, which is also the time all edges finish synchronisation
with the creation of stationary fire signals that lie dense in the
graph.

We introduce a typographic convention in
Definition 5.2. Each word of letters of the Latin alphabet that is
written in typewriter font shall denote the word itself and shall for
example not be the name of a variable.

We introduce a boolean algebra in
booleans
B = {no, yes}

Definition 5.3. Let B = {no, yes}. Each element b ∈ B is called
boolean. The map
¬ : B → B,

negation ¬

38

no 7→ yes,
yes 7→ no,
is called negation. The map
∧ : B × B → B,
(
no,
(b, b0 ) 7→
yes,

conjunction ∧

if no ∈ {b, b0 },
otherwise,

is called conjunction.



We introduce finite lists of directions in
Definition 5.4. Let Dir∗ be the set {w : [1 : n] → Dir | n ∈ N0 }.
Each element w ∈ Dir∗ is called word over Dir; for each word w ∈ Dir∗ ,
the non-negative integer |w| = |dom(w )| is called length of w; the word
λ : ∅ → Dir is called empty; the map
• : Dir∗ × Dir∗ → Dir∗ ,


(w, w0 ) →
7 

set Dir∗
word w over Dir
length |w| of w
empty word λ
concatenation •

0

[1 : |w| + |w |] → Dir,
(
w (i),
if i ≤ |w|, 

i 7→
0
w (i − |w|), otherwise,


is called concatenation.



Remark 5.5. The empty word is the only word of length 0 and it is
the neutral element of •.

The signal machine we construct in this section has infinitely many
kinds of signals, which are explained in remark 5.8, and given names,
speeds, and data sets in
Definition 5.6. Let
~ V, F, T} ∪
Knd = {I, L, C, M, U, U,

 [



~ B, X, FX},
{Dn , FDn } ∪ {D,

set Knd

n∈N0

let
spd : Knd → R≥0 ,

map spd

I 7→ 1,
L 7→ 0,
C 7→ 0,
M 7→ 0,
U 7→ 1,
U~ 7→ 1,
1
V 7→ ,
3

39

F 7→ 1,
T 7→ 1,
 n

Dn 7→

2
3

2−

 n , for n ∈ N0 ,
2
3

FDn 7→ 0, for n ∈ N+ ,
D~ 7→ 1,
B 7→ 0,
X 7→ 0,
FX 7→ 0,
and let
set None

None = {0},

family
{Dtk }k∈Knd

DtI = None,
DtL = Dir,
DtC = P (Dir),
DtM = {{w, w0 } ⊆ Dir∗ | w 6= w0 },
DtU = Dir∗ ,
DtU~ = Dir∗ × Dir∗ ×B,
DtV = Dir∗ × Dir∗ ×B,
DtF = None,
DtT = Dir∗ ×B,
DtDn = None, for n ∈ N0 ,
DtFDn = Dir, for n ∈ N+ ,
DtD~ = None,
DtB = None,
DtX = None,
DtFX = None .



The kinds together with their speeds and data sets determine the
possible signals, which are recalled and given abbreviations in
Definition 5.7. The set of signals is
Sgnl = {(k, d, u) | k ∈ Knd , (spd(k ), d) ∈ Arr , and u ∈ Dtk }.

set Sgnl

Let
Id = (I, d, 0), for d ∈ Dir,

abbreviations of
signals like Id ,
U~bwo ,d,wr and FX

Ld = (L, vry, d), for d ∈ Dir,
CD = (C, vry, D ), for D ∈ DtC ,
M{w,w0 } = (M, vry, {w, w0 }), for {w, w0 } ∈ DtM ,

40

Uwo ,d = (U, d, wo ), for wo ∈ DtU ,
~ d, (wo , wr , b)), for d ∈ Dir and (wo , wr , b) ∈ DtU~,
U~bwo ,d,wr = (U,
Vbd,wo ,wr = (V, d, (wo , wr , b)), for d ∈ Dir and (wo , wr , b) ∈ DtV ,
Fd = (F, d, 0), for d ∈ Dir,
Tbd,w = (T, d, (w, b)), for d ∈ Dir and (w, b) ∈ DtT ,
Dn,d = (Dn , d, 0), for n ∈ N0 and d ∈ Dir,
FDn,d = (FDn , vry, d), for n ∈ N+ and d ∈ Dir,
~ d, 0), for d ∈ Dir,
D~d = (D,
B = (B, vry, 0),
X = (X, vry, 0),
FX = (FX, vry, 0).



What signals of various kinds do when they reach a vertex or collide
with one another, what the data they carry means, and what we call
them is given a glimpse at in
Remark 5.8.
a. Each signal of kind I has speed 1; at each vertex
it reaches it spreads in all directions that lead away from where
it comes from, it initiates synchronisation of all incident edges except the one it comes from by sending divide signals onto them, it
initiates the search for midpoints of paths that contain the vertex
by sending (slowed-down) find-midpoint signals in all directions,
and it initiates one component of the search for the longest paths
of the graph by marking slowed-down find-midpoint signals if the
vertex is a leaf; it carries no data; and it is called initiate signal. The very first initiate signals spread from the general in all
directions.
b. Each signal of kind L is stationary, designates a virtual leaf, carries
the direction that leads onto the edge that is incident to the
virtual leaf, and is called leaf signal. Such signals are created
when initiate signals collide in a vertex (or on an edge), which
means that there is a cycle in the graph, and this cycle is broken
up by virtually terminating the involved edge(s) with leaf signals.
Each leaf signal is treated like a leaf in the following way: When
signals collide with each other and with leaf signals, for each
involved leaf signal, the collision of the signals that move in the
opposite direction than the one the leaf signal carries is handled as
if those signals collided in a leaf. Because leaf signals are created
at points at the same time or before any other signal reaches
them, the graph looks like a tree for all other signals.
c. Each signal of kind C is stationary; is positioned at a vertex that
is not a leaf; memorises the directions from which find-midpoint
signals that originated at the vertex, were reflected, and may

41

initiate signal

leaf signal

be on longest paths and would be the first ones to find their
midpoints have already returned, in other words, it memorises
the directions from which the slowest find-midpoint signals that
originated at the vertex and travelled alongside initiate signals
before they were reflected at a leaf have already returned; and is
called count signal. When an initiate signal reaches a vertex that
is not a leaf, a count signal is created.

count signal

Note that, for the data set of count signals, instead of the infinite set P (Dir), we could have used the finite set P ({1, 2, . . . , k}),
where k is the maximum degree of the graph or the upper bound
of the maximum degrees of the graphs to be considered and the
numbers represent directions that lead away from vertices. The
first choice of k would make the signal machine depend on the
graph, which is unconventional, whereas the latter would not and
would also fit to the fact that solutions of firing mob synchronisation problems are usually considered for graphs whose maximum
degrees are uniformly bounded by a constant.
d. Each signal of kind M is stationary, designates the midpoint of a
path, carries the directions that lead from its position to both
ends of the path, and is called midpoint signal. Such a signal
is created when a reflected find-midpoint signal collides with a
slowed-down find-midpoint signal that originated at the same vertex, or when two reflected find-midpoint signals that originated
at the same vertex collide with each other, which only happens
at the origin vertex itself. See figure 5.1.

midpoint signal

e. Each signal of kind U has speed 1, at each vertex it reaches it
spreads in all directions that lead away from where it comes from
(in the sense that, in each such direction, a signal of its kind
is sent) and it is also reflected (in the sense that a reflected findmidpoint signal is sent in the direction from where it comes from),
it carries the directions that lead from its position to the vertex the signal originated at, and it is called find-midpoint signal.
When an initiate signal reaches a vertex, for each incident edge,
a find-midpoint signal whose origin is the vertex is created that
travels onto the edge.

find-midpoint
signal

f. Each signal of kind U~ has speed 1; is the reflection of a findmidpoint signal at a vertex, travels back along the path this signal
took before it was reflected and slows down when it reaches the
vertex the find-midpoint signal originated at; carries the directions that lead from its position to the vertex the find-midpoint
signal originated at, the directions that lead from its position
to the vertex the find-midpoint signal was reflected at, and a
boolean that indicates whether the path described by its position and both directions, which leads from the reflection vertex
to the origin vertex, may be the subpath of a longest path that

42

has the same source (or target), and the boolean also indicates
whether the signal would be the first one to find the longest path’s
midpoint; and is called reflected find-midpoint signal and, if the
boolean it carries is yes, it is called marked.
As has already been pointed at, when a find-midpoint signal
reaches a vertex, a reflected find-midpoint signal is created that
travels onto the edge the find-midpoint signal comes from. If the
vertex is a leaf and the find-midpoint signal is one of the first signals to reach it, which is precisely the case if the signal reaches the
leaf together with an initiate signal, then its reflection is marked,
and otherwise, not. The reasons are that both ends of a longest
path are leaves and that a find-midpoint signal that is not among
the first signals to reach one end of a longest path would not find
its midpoint after another one has already found it.
When a marked reflected find-midpoint signal reaches a vertex
that is not a leaf, the count signal at the vertex memorises the
direction the marked signal comes from, and the signal stays
marked, if the memory of the count signal contains each but one
direction that leads away from the vertex, and it is unmarked,
otherwise. Why is that? Each vertex that is not the general is
reached precisely once by an initiate signal, at which point findmidpoint signals are sent in all directions; for each direction, the
marked reflected find-midpoint signal to return from that direction is memorised, which is the slowest one or, in other words, the
last one or the one that had the longest way (note that although
only one find-midpoint signal is sent in a direction, multiple reflected find-midpoint signals may return from that direction); the
penultimate marked reflected find-midpoint signal to return may
come from one edge of a longest path that runs through the vertex and hence it stays marked (note that the other edge of the
longest path that is incident to the vertex would be the one from
which the marked signal has not yet returned); the signals that
return before the penultimate one are too fast to be on a longest
path and the last signal to return has already collided with the
slowed-down penultimate signal that returned before it (if they
do not return at the same time) and hence they are unmarked.
g. Each signal of kind V has speed 1/3; is the slow-down of a reflected find-midpoint signal at the vertex the find-midpoint signal
originated at; at each vertex it reaches it spreads in all directions
that lead away from where it comes from; it carries the directions
that lead from its position to the vertex the find-midpoint signal
originated at, the directions that lead from the origin vertex to
the vertex the find-midpoint signal was reflected at, and a boolean
that indicates whether the path described by its position and both
directions, which leads from the reflection vertex over the origin

43

(marked) reflected
find-midpoint
signal

vertex to its position, may be the subpath of a longest path that
has the same source (or target), and the boolean also indicates
whether the signal would be the first one to find the longest path’s
midpoint; and it is called slowed-down find-midpoint signal and,
if the boolean it carries is yes, it is called marked.

(marked)
slowed-down
find-midpoint
signal

As has already been pointed at, when a reflected find-midpoint
signal reaches the vertex the find-midpoint signal originated at,
for each incident edge except the one the reflected find-midpoint
signal comes from, a slowed-down find-midpoint signal is created that travels onto the edge. Additionally, when an initiate
signal reaches a vertex, for each incident edge, a slowed-down
find-midpoint signal is created that travels onto the edge.
The latter case is in the following senses the boundary or limiting case of the former: Imagine that the vertex the initiate signal
reaches is in fact two vertices that are infinitesimally close; then
a find-midpoint signal is created at one vertex, this signal immediately reaches the infinitesimally close other vertex, there it is
reflected, the reflected find-midpoint signal immediately reaches
the infinitesimally close other vertex, and there it is slowed down.
Or, analogously, imagine the limit of the cascade of the creation
of a find-midpoint signal, its reflection, and slow-down for shorter
and shorter distances between the vertex the find-midpoint signal originates at and the one it is reflected at; then in the limit
the find-midpoint signal and its reflection vanish and only the
slowed-down find-midpoint signal remains.
When a marked slowed-down find-midpoint signal reaches a vertex that is not a leaf, the count signal at the vertex memorises
the direction the marked signal comes from, and the signal stays
marked, if the memory of the count signal contains each but one
direction that leads away from the vertex, and it is unmarked,
otherwise. Why is that? The slowed-down signal reaches the vertex at the same time and from the same direction as the slowest
reflected find-midpoint signal from that direction that originated
at the vertex. The latter signal is however not marked, because
it did not travel alongside initiate signals before it was reflected
at a leaf (the reason is that if it had travelled alongside initiate
signals, then it would have been reflected at the same time as
the find-midpoint signal whose reflection turned into the marked
slowed-down find-midpoint signal and hence, because the paths
from the reflection leaves to the vertex they reach together have
the same lengths, the find-midpoint signal that reaches it slowed
down would have taken longer, and therefore the signals would
not reach the vertex at the same time).
Therefore, the memory of the count signal contains each but one
direction if and only if from each but one direction the slowest

44

reflected find-midpoint signals that originated at the vertex have
already returned. If this is the case, then the incident edge belonging to that direction may be the edge of a longest path that runs
through the vertex and the slowed-down find-midpoint signal may
be the one to collide with the not yet returned signal somewhere
on or beyond the edge precisely at the midpoint of the longest
path. If from more than one direction signals are overdue, then
the paths running through each pair of these directions are longer
than the paths running through any of these directions and the
direction the slowed-down find-midpoint signal comes from. And,
if all signals have already returned, then they have already collided with the slowed-down signal and found the midpoints of
the longest paths whose determination involves the slowed-down
signal if there are any.
h. Each signal of kind F has speed 1, is created at the midpoint of an
edge, moves towards one end of the edge, and freezes synchronisation of the edge, carries no data, and is called freeze signal.
When an initiate signal reaches a vertex, for each incident edge,
a find-midpoint signal and a slowed-down find-midpoint signal
are created that travel onto the edge, the former is reflected at
the other end of the edge and collides with the latter at the midpoint of the edge, at which point two freeze signals are created
that travel to both ends of the edge. See figure 5.3
i. Each signal of kind T has speed 1, is created at the midpoint
of a path, travels along the path towards one of end of the path,
creates a new signal of its kind when it collides with the midpoint
signal that designates the midpoint of a path such that one of the
two subpaths from the midpoint to either end of the path (a halfpath) coincides with the path it takes itself and the new signal
travels along the other half-path, and thaws synchronisation of
an edge if it collided with or was created at the midpoint signal
that designates the midpoint of the last edge of the path it takes,
carries the directions of the path it takes and a boolean that
indicates whether it thaws synchronisation of the edge it is on or
not, and is called thaw signal.
The first thaw signals are created simultaneously at the midpoints
of longest paths. For each such midpoint, two thaw signals are
created, one that travels along the path to one end of the path
and the other that travels to the other end of the path. When a
thaw signal collides with the midpoint of a path whose one halfpath coincides with the remaining path the thaw signal travels
along, an additional thaw signal is created that travels along the
other half-path. On its way from the midpoint of the last edge
of the path a thaw signal travels on to the end of the path, the
thaw signal thaws all frozen signals it collides with.

45

freeze signal

half-path

thaw signal

In this way, starting at the midpoints of longest paths, thaw signals traverse the midpoints of shorter and shorter paths, reach the
ends of their paths at the same time, and thaw synchronisation
of edges, which finishes at the same time. See figures 5.3 to 5.5
j. Each signal of kind D0 has speed 1, moves from one boundary
(which may be one end of an edge or a boundary signal) to the
next boundary (which may be the other end of the edge or a
boundary signal) and is reflected there, carries no data, and is
called divide signal of type 0. When an initiate signal reaches a
vertex, for each incident edge, a divide signal of type 0 is created
that travels onto the edge. And, when a divide signal of any type
collides with a reflected divide signal, a divide signal of type 0 is
created that travels in the same direction as the (non-reflected)
divide signal.

divide signal of
type 0

k. Each signal of kind Dn , for n ∈ N+ , has speed (2/3)n /(2 −
(2/3)n ), moves from one boundary (which may be one end of
an edge or a boundary signal) towards the next boundary (which
may be the other end of the edge or a boundary signal) but never
reaches it and can be frozen, carries no data, and is called divide signal of type n. When an initiate signal reaches a vertex,
for each incident edge, and for each n ∈ N+ , a divide signal of
type n is created that travels onto the edge. And, when a divide
signal of any type collides with a reflected divide signal, for each
n ∈ N+ , a divide signal of type n is created that travels in the
same direction as the (non-reflected) divide signal.

divide signal of
type n

Note that although Dn , for n ∈ N+ , are different kinds, events
that involve signals of these kinds are handled the same way, in
other words, signals of these kinds are not differentiated by the
two local transition functions of the signal machine. The only
reason they are different kinds is because we need them to have
different speeds and by definition all signals of the same kind have
the same speed.
l. Each signal of kind FDn , for n ∈ N+ , has speed 0, is a frozen divide
signal of type n, carries the direction the non-frozen divide signal
had, and is called frozen divide signal of type n. When a freeze
signal collides with or is created at the same time as a divide
signal of type n ∈ N+ , the divide signal is frozen.

frozen divide
signal of type n

reflected divide
signal

m. Each signal of kind D~ has speed 1, is the reflection of a divide
signal of type 0, creates a boundary signal when it collides with
a divide signal of type n, creates a fire signal when it reaches the
end of the edge it traverses, carries no data, and is called reflected
divide signal. When a divide signal of type 0 reaches a boundary
(which may be a vertex or a boundary signal), a reflected divide
signal is created that travels in the opposite direction.

46

n. Each signal of kind B is stationary, designates a boundary for the
synchronisation of an edge, carries no data, and is called boundary
signal. Such signals are created when divide signals collide with
reflected divide signals.
On each edge, the interplay of divide signals, reflected divide signals, and boundary signals has the following effect: At first a
divide signal of type 1 collides with a reflected divide signal that
originated at the same end of the edge. This collision results in
the creation of a boundary signal that divides the edge into two
parts. The length of the part from the origin vertex to the boundary signal is 2/3 times the length of the edge and the length of
the part from the boundary signal to the other end of the edge is
1/3 times the length of the edge.
In the same manner as the edge itself, the (1/3)-part is recursively
divided further and further. In the (2/3)-part, a signal of type
2 collides with the reflected divide signal from before. This collision results in the creation of a boundary signal that divides the
(2/3)-part into two subparts. One has (2/3) · (2/3) the length of
the edge and the other has (1/3) · (2/3) the length of the edge.
The ((1/3) · (2/3))-part is recursively divided further and further.
The ((2/3) · (2/3))-part is divided into a ((2/3) · (2/3) · (2/3))part and a ((1/3) · (2/3) · (2/3))-part and so forth.
If there were no freeze and thaw signals, after twice the time the
edge is long — which is precisely the time it took the divide signal
of type 0 to reach the other end of the edge, to be reflected there,
and to return to the end it originated at — the boundary signals
together are dense on the edge, which means that each point
on the edge is arbitrarily close to a boundary signal, and, at this
point in time, each boundary signal collides with a reflected divide
signal, which results in the creation of fire signals that designate
that synchronisation has finished.
However, because the synchronisation of each edge is started at
different times and takes different times depending on how far
away the edge is from the general and how long the edge is, synchronisation of each edge is frozen at the last possible moment
— the freezing starts from the midpoint of the edge 3/2 times
the edge’s length many time units after synchronisation of the
edge was initiated — and it is thawed such that all edges finish
synchronisation at the same time — the thawing starts from the
midpoint of the edge 1/3 times the edge’s length many time units
before the total synchronisation finishes, which is the sum of the
radius of the graph and its diameter. Recall that the radius is the
longest distance from the general to another vertex and that the
diameter is the longest distance between two vertices.

47

boundary signal

Note that, for each edge, collisions of divide signals with reflected
divide signals and with boundary signals accumulate at the times
the two freeze signals and the two thaw signals reach the ends of
the edge. These accumulations are singularities of order 1. See
figure 5.2.
o. Each signal of kind X is stationary, designates that synchronisation has finished and can be frozen, carries no data, and is called
fire signal. Such signals are created when reflected divide signals
collide with boundary signals or reach vertices.

fire signal

p. Each signal of kind FX is stationary, is a frozen fire signal, carries
no data, and is called frozen fire signal. On each edge, one of the
two freeze signals reaches an end of the edge at the same time
as the reflected divide signal, at which point a frozen fire signal
is created; it is thawed at the same time at which all other fire
signals are created, which happens on all edges at the same time
and the fire signals lie dense in the multigraph.


frozen fire signal

In the forthcoming definitions of maps we make extensive use of
pattern matching. To make the exposition concise and readable we
introduce some pattern matching conventions in
order matters

Definition 5.9.
a. In the case that patterns of multiple rules overlap, the rule that occurs first is the one to use. For example, the
map f : Z → Z, 0 7→ 1, 1 7→ 0, z 7→ z, maps 0 to 1 and 1 to 0
and each other integer to itself.

wildcard _

b. In the case that we do not care to name some part of a matched
structure, we write _ instead of a name for the part. For example,
the pattern (E, _, Id ) matches each triple whose last component
is an initiate signal, gives the first component the name E, does
not give a name to the second component, and gives the direction
of the initiate signal the name d. And, the pattern Uwo ,_ matches
each find-midpoint signal, gives the directions to the vertex the
signal originated at the name wo , but gives no name to the direction of the signal.

same names
express equality

c. To express equality of different parts of a matched structure,
we give those parts the same name. For example, the pattern
{D~−d , Dn,d } matches each set that consists of a reflected divide
signal and a divide signal of any type such that the direction of
the reflected divide signal is the opposite of the direction of the
divide signal, gives the direction of the divide signal the name d,
and gives its type the name n.

@-notation

d. To name both a structure and its parts, we use a Haskell-like
@-notation. For example, the pattern s@U~bλ,d,λ matches each reflected find-midpoint signal whose directions to the vertex the

48

signal originated at and to the vertex the signal was reflected at
are empty, gives the direction of the signal the name d, gives the
boolean that indicates whether the signal may be on a longest
path and would be the first to find its midpoint the name b, and
gives the signal itself the name s.

Some of the maps we define below are actually partial maps. We
represent them by (total) maps as specified in
Definition 5.10. Let X and X 0 be two sets, let Y be a subset of X,
let ⊥ be an element that is not in X 0 , which we call bottom, and let f
be a map from X to X 0 ∪ {⊥} such that, for each element x ∈ X, we
have f (x) = ⊥ if and only if x ∈
/ Y . The map f represents a partial
map whose domain of definition is Y , whose domain is X, and whose
codomain is X 0 .
In the following, for maps like f , we do not explicitly specify the
domain Y of definition (it is the set X r f −1 (⊥)) and we implicitly
assume that ⊥ does not occur in the codomain X 0 of the represented
partial map.

To define the local transition functions, we begin with definitions for
special cases and use those to gradually arrive at definitions for the
tree
general case. For trees and without freezing and thawing, the map δv,1
handles the event that precisely one signal reaches a vertex, and the
tree and δ tree handle the event that precisely two signals collide
maps δv,2
e,2
in a vertex and an edge respectively (see definition 5.11). For trees, the
maps δvtree and δetree handle events involving arbitrarily many signals
tree , δ tree , and
by considering unordered pairs of signals and applying δv,1
v,2
tree , and by also freezing and thawing signals if needed (see definiδe,2
tion 5.12). For virtual trees, which means that edges of the graph have
been virtually cut by leaf signals to remove circles, the maps δvvirtualTree
and δevirtualTree handle events by partitioning signals at virtual cuts into
those belonging to one or the other leaf and applying δvtree and δetree (see
definition 5.13). For general graphs, the maps δv and δe handle events
by virtually cutting the graph, which eventually creates a virtual tree,
and applying δvvirtualTree and δevirtualTree (see definition 5.14).
Most of the forthcoming definitions and parts of them are annotated
with intuitive explanations of what they mean. For example, after each
rule that handles a specific kind of event, it is explained what kind of
event in the time evolution of the signal machine is handled, how it is
handled, and sometimes why.
How events for trees and without freezing and thawing, with one or
two signals involved are handled is given in

49

representations of
partial maps using
the bottom symbol
⊥

Definition 5.11. The following map tells whether two words of directions are both empty:
areEmpty : Dir∗ × Dir∗ → B,
(
yes,
0
(w, w ) 7→
no,

map areEmpty

if |w| = 0 and |w0 | = 0,
otherwise.

For trees and without freezing and thawing, the case that precisely
two signals collide on an edge but not in one of its ends is handled by
the following map, which maps colliding unordered pairs of signals for
which a collision rule is specified to the resulting signals and all other
sets of signals to ⊥:
tree
δe,2
: P (Sgnl) → P (Sgnl) ∪ {⊥},
{D0,d , B} 7→ {D~−d , B},

tree
map δe,2

(If a divide signal of type 0 collides with a boundary signal, then reflect
the divide signal.)
{D~−d , Dn,d } 7→ {B} ∪ {Dn0 ,d | n0 ∈ N0 },
(If a reflected divide signal collides with a divide signal of any type,
then create a boundary signal and send divide signals of all types in
the direction of the original divide signal.)
0

{s@U~bλ,d,λ , s0 @Vb−d,λ,λ } 7→
{s, s0 , M{−d,d} , F−d , Fd },

if b = no or b0 = no,

∅,

otherwise,

(

(If a reflected find-midpoint signal collides with a slowed-down findmidpoint signal that originated at the same end of an edge and only
travelled on this edge, then the point of collision is the midpoint of the
edge and, if the graph has at least two edges, then let the signals move
on, designate the point by a midpoint signal, and send freeze signals
to both ends of the edge to freeze synchronisation of the edge, and
otherwise, do not create and send any signals.)
0

{s@U~bwo ,d,wr , s0 @Vb−d,wo ,wr0 } 7→
{s, s0 , M{(−d)•wr ,d•wo •wr0 } },

if b = no or b0 = no,

no
{Tno
−d,wr , Td,wo •wr0 },

otherwise,

(

(If a reflected find-midpoint signal collides with a slowed-down findmidpoint signal that originated at the same vertex, then the point of
collision is the midpoint of the shortest path in the virtual tree from
the vertex the reflected find-midpoint signal was reflected at to the
vertex the signal that spawned the slowed-down find-midpoint signal
was reflected at and, if this midpoint is not the midpoint of a longest
path, then let the signals move on and designate the point by a midpoint
signal, and otherwise, send thaw signals along that longest path to both
its ends.)
areEmpty(w,w0 )

{Tno
d,w , M{d•w,d0 •w0 } } 7→ {Td,w

50

areEmpty(w,w0 )

, Td0 ,w0

},

(If a thaw signal collides with a midpoint signal that designates the
midpoint of a path whose one half-path coincides with the path the
thaw signal is going to take, then send an additional thaw signal along
the other half-path and, if this path is just a directed edge, then make
the thaw signals thaw synchronisation of the edge.)
_ 7→ ⊥.
(If none of the above happened, then indicate that by returning bottom.)

A signal that reaches a vertex is in a leaf if and only if there is
precisely one direction that leads away from the vertex. And a signal
that reaches a vertex is the penultimate one to do so if and only if the
number of signals that have already returned including the signal itself
is one less than the number of directions that lead away from the vertex.
The two maps that express this in an abstract way using booleans are
inLeaf : P (Dir) → B,
(
no,
if |E| 6= 1,
E 7→
yes, otherwise,

map inLeaf

penultimate : P (Dir) × N0 → B,
(
no,
if |E| − 1 6= n,
(E, n) 7→
yes, otherwise.

map penultimate

and

For trees and without freezing and thawing, the case that precisely
one signal reaches a vertex is handled by the following map, which maps
quadruples — consisting of first, the set of directions that lead away
from the vertex; secondly, the number of the directions from which
the slowest reflected find-midpoint signals that originated at the vertex
have already returned or have just arrived; thirdly, a boolean that indicates whether the signal is among the first ones to reach the vertex;
and lastly, the signal that reaches the vertex — to the resulting signals:
tree
δv,1
: P (Dir) × N0 × B × Sgnl → P (Sgnl),
(_, _, _, D0,d ) 7→ {D~−d },

tree
map δv,1

(If a divide signal of type 0 reaches a vertex, then reflect it.)

(_, _, _, D~d ) 7→ {X},
(If a reflected divide signal reaches a vertex, then create a fire signal.)

(E, _, _, Id ) 7→



[

{Ie }



e∈E r{−d}

∪



∪

[

[

{Dn,e | n ∈ N0 }



e∈E r{−d}
inLeaf (E )

{Uλ,e , Ve,λ,λ



} ,

e∈E

51

(If an initiate signal reaches a vertex, then send initiate signals onto all
incident edges except the one the original initiate signal comes from,
send divide signals of all types onto all incident edges except the one the
original initiate signal comes from, and send find-midpoint and sloweddown find-midpoint signals onto all incident edges to find all midpoints
of paths that contain the vertex, where, in the case that the vertex is a
leaf, the slowed-down find-midpoint signal is marked, where the mark
means that it may be on a longest path and would be the first to find
its midpoint.)
b∧inLeaf (E )

}



{U(−d)•wo ,e } ,

(E, _, b, Uwo ,d ) 7→ {U~wo ,−d,λ
∪

[



e∈E r{−d}

(If a find-midpoint signal reaches a leaf, then reflect it and, if it is one
of the first signals to reach the leaf, then also mark it as a signal that
may be on a longest path and would be the first to find its midpoint.
And, if a find-midpoint signal reaches a vertex that is not a leaf, then
reflect it and send find-midpoint signals onto all incident edges except
the one the original signal comes from.)
[

(E, n, _, U~bλ,d,wr ) 7→

b∧penultimate(E,n)

{Ve,λ,(−d)•wr

},

e∈E r{−d}

(If a reflected find-midpoint signal reaches the vertex it originated at,
then send slowed-down find-midpoint signals onto all incident edges
except the one the original signal comes from and, if the original signal
is marked and is the penultimate marked signal that originated at and
has returned to the vertex, then also mark the slowed-down signals as
signals that may be on a longest path and would be the first to find
their midpoints.)
b∧penultimate(E,n)

(E, n, _, U~be•wo ,d,wr ) 7→ {U~wo ,e,(−d)•wr

},

(If a reflected find-midpoint signal reaches a vertex, then it takes the
way back it took before it was reflected and, if it is not one of the penultimate marked signals that reaches the vertex, then it is unmarked.)
[

(E, n, _, Vbd,wo ,wr ) 7→

b∧penultimate(E,n)

{Ve,(−d)•wo ,wr

},

e∈E r{−d}

(If a slowed-down find-midpoint signal reaches a vertex, then send
slowed-down find-midpoint signals onto all incident edges except the
one the original signal comes from, and mark these signals, if the original signal is marked — in which case it arrives at the same time and
from the same direction as the slowest reflected find-midpoint signal
that originated at the vertex, which however is not marked because it
arrived too late at the leaf it was reflected at — and from exactly one
direction the slowest find-midpoint signal that originated at the vertex
has not returned yet.)

(_, _, _, Fd ) 7→ ∅,

52

(If a freeze signal reaches the end of the edge it freezes, then it vanishes.)

(_, _, _, Tyes
d,λ ) 7→ ∅,
(If a thaw signal reaches the end of its path, then it vanishes.)
no
(_, _, _, Tno
d,e•w ) 7→ {Te,w },

(If a thaw signal reaches a vertex, then it takes the direction that makes
it stay on its path.)


 {(s, d, y )}, if spd(s) = 0,
[
(E, _, _, (s, d, y )) →
7
{(s, e, y )}, otherwise.


e∈E r{−d}

(A stationary signal in a vertex stays there, and if a non-stationary
signal reaches a vertex, then copies of it are sent onto each edge except
the one the signal comes from.)

For trees and without freezing and thawing, the case that precisely
two signals collide in a vertex is handled by the following map, which
maps triples — consisting of first, the set of directions that lead away
from the vertex; secondly, the number of the directions from which
the slowest reflected find-midpoint signals that originated at the vertex
have already returned or have just arrived; and lastly, the set of colliding
signals that is supposed to consist of precisely two signals — to the
resulting signals, if a collision rule is specified, and to ⊥, otherwise:
tree
δv,2
: P (Dir) × N0 × P (Sgnl) → P (Sgnl) ∪ {⊥},
(_, _, {D~d , B}) 7→ {X},

tree
map δv,2

(If a reflected divide signal collides with a boundary signal, then create
a fire signal.)
0
(E, n, {s@U~b(−d0 )•wo0 ,d,wr , s0 @Vbd0 ,wo0 ,wr0 }) 7→


tree

δv,1
(E, n, no, s)




tree

∪ δv,1
(E, n, no, s0 )












∪ {M{(−d)•wr ,(−d0 )•wo0 •wr0 }
no
{T−d,wr , Tno
−d0 ,wo0 •wr0 },

if b = no or b0 = no,



},

otherwise,

(If a reflected find-midpoint signal collides with a slowed-down findmidpoint signal that originated at the same vertex, then the vertex of
collision is the midpoint of the shortest path in the virtual tree from
the vertex the reflected find-midpoint signal was reflected at to the
vertex the signal that spawned the slowed-down find-midpoint signal
was reflected at and, if this midpoint is not the midpoint of a longest
path, then treat the original signals as if they reached the vertex alone
and designate the point by a midpoint signal, and otherwise, send thaw
signals along that longest path to both its ends.)
0

(E, n, {s@U~bλ,d,wr , s0 @U~bλ,d0 ,wr0 }) 7→

53


tree

δv,1
(E, n, no, s)




tree

∪ δv,1
(E, n, no, s0 )







∪ {M{(−d)•wr ,(−d0 )•wr0 }






if b = no or b0 = no or n 6= |E|,



},

no
{Tno
−d,wr , T−d0 ,wr0 },

otherwise,

(If two reflected find-midpoint signals that originated at the same vertex
collide with each other, then the vertex of collision is the vertex the
signals originated at and it is the midpoint of the shortest path in the
virtual tree between the vertices the signals were reflected at and, if this
midpoint is not the midpoint of a longest path, then treat the original
signals as if they reached the vertex alone and designate the point by
a midpoint signal, and otherwise, send thaw signals along that longest
path to both its ends.)
no
no
(_, _, {Tno
d,w , M{w@(d0 •w0 ),d00 •w00 } }) 7→ {Td0 ,w0 , Td00 ,w00 },

(If a thaw signal collides with a midpoint signal that designates the
midpoint of a path whose one half-path coincides with the path the
thaw signal is going to take, then send an additional thaw signal along
the other half-path.)
_ 7→ ⊥.
(If none of the above happened, then indicate that by returning bottom.)


How events for trees are handled is given in
Definition 5.12. The maps






χ : Sgnl
ξ
:
Sgnl
→
Sgnl,














FDn,d
Dn,d →
7 FDn,d ,
and



FX
X 7→ FX, 














s
s 7→ s,

maps ξ and χ



→ Sgnl,





7→ Dn,d , 
7→ X,








7→ s,

freeze and thaw signals that can be frozen and thawed respectively.
The map
ν : P (Sgnl) × P (Sgnl) → P (Sgnl),

map ν

(S, S 0 ) 7→


ξ (S 0 ),









χ(S 0 ),








 0
S,

if ∃ Fd ∈ S ∪ S 0
yes

and @ Td,λ ∈ S ∪ S 0 ,
yes

if ∃ Td,λ ∈ S ∪ S 0
and @ Fd ∈ S ∪ S 0 ,
otherwise,

takes a set of old signals and a set of new signals and freezes the new
signals, if the old or new signals contain a freeze signal but not a thaw

54

signal that thaws the synchronisation of an edge; thaws the new signals, if the old or new signals contain a thaw signal that thaws the
synchronisation of an edge but not a freeze signal; and does nothing,
otherwise.
The maps
ζ2 : P (Sgnl) → P (P (Sgnl)),

map ζ2

0

0

S 7→ {{s, s } ⊆ S | s 6= s and

tree
δe,2
({s, s0 })

6= ⊥},

and
η2 : P (Dir) × P (Sgnl) → P (P (Sgnl)),

map η2

0

0

(D, S ) 7→ {{s, s } ⊆ S | s 6= s and
tree
δv,2
(D, x, {s, s0 }) 6= ⊥},

both take a set of signals and return the set of unordered pairs of
distinct signals from the given set for which a collision rule is specified
tree and δ tree respectively.
in δe,2
v,2
The map
δetree : P (Sgnl) → P (Sgnl),


S 7→ ν (S, S r

map δetree

[
P ∈ζ2 (S )



P ∪



[



tree
δe,2
(P ) ),

P ∈ζ2 (S )

handles collisions of signals on edges by leaving signals for which no
tree as is,
pairwise collision rule with any other signal is specified in δe,2
tree
by applying δe,2 to each unordered pair of distinct signals for which a
collision rule is specified, and by applying ν to freeze or thaw signals if
there are or were any freeze or thaw signals.
The map
κ : P (Sgnl) → P (Dir),
S 7→ (

[

map κ

D)

CD ∈S

∪ {d ∈ Dir | ∃ wr ∈ Dir∗ : U~λ,d,wr ∈ S}
yes

∪ {d ∈ Dir | ∃ wo ∈ Dir∗ ∃ wr ∈ Dir∗ : Vd,wo ,wr ∈ S}
yes

takes a set of signals that are at a vertex and returns the directions from
which the slowest reflected find-midpoint signals that originated at the
vertex have already returned or have just arrived. The directions from
which signals have already returned is memorised by a count signal,
and the other directions are the ones from which marked reflected findmidpoint signals that originated at the vertex or marked slowed-down
find-midpoint signals with any origin have just arrived (the slowest ones
of the latter kind always arrive at the same time and from the same
direction as the slowest but unmarked reflected find-midpoint signal
that originated at the vertex arrive from that direction). Note that
although we take the union of the memories of all count signals, there

55

is actually gonna be no such signal in leaves (in which case the union
is ∅) and precisely one such signal in each vertex that is not a leaf (in
which case the union is the memory stored by this signal).
The map

κ : P (Sgnl) → B,
(
yes, if ∃ d ∈ Dir : Id ∈ S,
S 7→
no,
otherwise,

map κ

tells whether a set of signals contains any initiate signals or not. It is
used by δvtree to tell whether a find-midpoint signal that reaches a leaf
is among the first ones to do so, which is the case if and only if the
signal travels alongside an initiate signal.
The map
δvtree : P (Dir) × P (Sgnl) → P (Sgnl),

map δvtree

(

(D, S ) 7→ ν (S,

)

∅,

if inLeaf (D ) = yes,

{Cκ(S ) }, otherwise,


tree
∪ δv,1
D, |κ(S )|, κ(S ), S 0 r

[

P



P ∈η2 (D,S 0 )

∪

[

tree
δv,2
(D, |κ(S )|, P )),

P ∈η2 (D,S 0 )

where S 0 = S r {CD ∈ S | D ⊆ Dir}.
handles events in vertices by updating the memory of the directions
from which the slowest reflected find-midpoint signals that originated
at the vertex have already returned or have just arrived, by applying
tree to non-count signals for which no pairwise collision rule with any
δv,1
tree , by applying δ tree to each
other non-count signal is specified in δv,2
v,2
unordered pair of distinct non-count signals for which a collision rule
is specified, and by applying ν to freeze or thaw signals if there are or
were any freeze or thaw signals.

How events for virtual trees, where virtual leaves already exist, are
handled is given in
Definition 5.13. When colliding signals in the graph and the involved
directions are partitioned with respect to the virtual tree, some of the
components may be degenerated and applying δetree and δvtree to them
may have unwanted effects. Such boundary cases are properly handled
by the maps
δebndryCases : P (Sgnl) → P (Sgnl),
(
∅,
if |S| ≤ 1,
S 7→ tree
δe (S ), otherwise,

map δebndryCases

and
δvbndryCases : P (Dir) × P (Sgnl) → P (Sgnl),

map δvbndryCases

56

(

(D, S ) 7→

∅,

if D = ∅ or S = ∅,

δvtree (D, S ),

otherwise.

To handle an event involving the signals S in a virtual tree we do
the following: We partition the signals into leaf signals, namely SL , for
each leaf signal Ld ∈ SL , the signals coming from the direction −d,
namely Sd , and all other signals, namely So . And we denote the set
of directions that no leaf signal has by D0 . Intuitively, SL is the set of
virtual leaves, Sd is the set of signals that reach the virtual leaf Ld , and
D0 is the set of directions that do not lead away from any virtual leaf.
In the configurations we will encounter, in the case of a collision on an
edge, there are either no leaf signals, in which case So = S, or there are
two leaf signals, in which case So = ∅ (because there are no stationary
signals in virtual leaves besides the leaf signals themselves) and hence
either the signals simply collide, or one subset of signals reaches one
virtual leaf and the other subset reaches the other virtual leaf. And, in
the case of a collision in a vertex, signals coming from some edges may
reach a virtual leaf and signals coming from other edges may reach the
virtual vertex (we call it virtual because some of its original edges have
been cut off; the directions onto the ones that have not been cut off
are those in the set D0 ). Note that some collisions are not collisions in
the virtual tree, because the signals came from different directions of
virtual cuts. The maps that do what we just explained are
δevirtualTree : P (Sgnl) → P (Sgnl),

map δevirtualTree

S 7→ SL ∪ δebndryCases (So )
∪

[



δvbndryCases ({d}, Sd ) ,

d∈X

and
δvvirtualTree : P (Dir) × P (Sgnl) → P (Sgnl),

map δvvirtualTree

(D, S ) 7→ SL ∪ δvbndryCases (D0 , So )
∪

[



δvbndryCases ({d}, Sd ) ,

d∈X

where X = {d ∈ Dir | Ld ∈ S}, the set of directions that lead away from
virtual leaves, SL = {Ld | d ∈ X}, the set of virtual leaves, {Sd }d∈X =
{{s ∈ S | dir(s) = −d}}d∈X , for each direction of a virtual leaf, the
set of signals that reach the virtual leaf corresponding to the direction
S
moving towards it, So = S r (SL ∪ ( d∈X Sd )), the signals that are not
virtual leaves and that do not reach a virtual leaf, and D0 = D r X,
the set of directions that do not lead away from virtual leaves.

How events for graphs are handled is given in
Definition 5.14. The map
µ : P (Sgnl) → P (Sgnl),

map µ

57

S 7→ −{d ∈ Dir | Id ∈ S},
takes a set of signals and returns the set of the reverses of the directions
that initiate signals have.
The map
ϕeL : P (Sgnl) → P (Sgnl),
(
∅,
if |µ(S )| ≤ 1,
S 7→
{Ld | d ∈ µ(S )}, otherwise,

map ϕeL

takes a set of signals and returns the empty set, if there is at most one
initiate signal, and the set that consists of a virtual leaf for each initiate
signal, otherwise.
The map
ϕvL : P (Dir) × P (Sgnl) → P (Sgnl),

map ϕvL

(D, S ) 7→



∅, if |µ(S )| ≤ 1,






{L | d ∈ D}, if |µ(S )| ≥ 2 and µ(S ) = D,

 d

and inLeaf (D ) = no,





{Ld | d ∈ D r {dx }}, if |µ(S )| ≥ 2 and µ(S ) 6= D,





for some dx ∈ D r µ(S ),

takes a set of directions and a set of signals and returns the empty set,
if there is at most one initiate signal, or the set that consists of a virtual
leaf for each initiate signal, if there are at least two initiate signals and
initiate signals reached the vertex from all incident edges, or the set
that consists of a virtual leaf for each initiate signal but one, otherwise.
Note that right now the choice of dx is non-deterministic; however, if
the finite set of directions carried a total order, then we could deterministically choose for example the smallest direction; or if continuum representations of graphs were embedded in high-dimensional Euclidean
spaces and a Cartesian coordinate system was chosen such that the
occurring directions are unit vectors, then the lexicographic order is a
total order on the set of directions.
The map
δe : dom(δe ) → P (Sgnl),

map δe

S 7→ δevirtualTree (S ∪ ϕeL (S ))
handles collisions on edges by creating two virtual leaves, if two initiate signals collide, which cuts the edge virtually, and then applying
δevirtualTree to the maybe new set of signals.
The map
δv : dom(δv ) → P (Sgnl),

map δv

(D, S ) 7→ δvvirtualTree (D, S ∪ ϕvL (D, S ))

58

handles events in vertices by creating a virtual leaf for each incident
edge, if the vertex is not a leaf and initiate signals reached the vertex
from all incident edges, or by creating a virtual leaf for each incident
edge from which an initiate signal arrived except for one such edge,
otherwise, and then applying δvvirtualTree to the maybe new set of signals.
Intuitively, initiate signals are used to turn the graph into a virtual
tree by cutting edges at points where such signals collide. These cuts
create virtual leaves which are represented by leaf signals. More precisely: When two initiate signals collide on an edge, it is cut by two
leaf signals, one for each of the two directions. And when at least two
initiate signals collide in a vertex, there are two cases: If initiate signals
arrive from all directions, then each incident edge is cut by a leaf signal;
otherwise, the incident edges from which initiate signals arrive are cut
except for one such edge — the initiate signal from this excluded edge
will spread to all edges that have not been cut.

Main Theorem 5.15. The signal machine S = (Knd, spd, {Dtk }k∈Knd ,
(δe , δv )) is a time-optimal quasi-solution of the firing mob synchronisation problem over continuum representations of weighted, non-trivial,
finite, and connected undirected multigraphs in the following sense:
For each representation M of such a graph, each vertex g ∈ M , for
the time t = r + d, where r = supm∈M d(g, m) is the radius of M
with respect to g and d = supm,m0 ∈M d(m, m0 ) is the diameter of M ,
for the instantiation of S for M , for the configuration c ∈ Cnf such
S
inLeaf (dir(g))
that c(g) = d∈dir(g) {Id } ∪ {Dn,d | n ∈ N0 } ∪ {Uλ,d , Vd,λ,λ
} and
cM r{g} ≡ ∅, the points in the configuration (t)(c) at which a fire
signal occurs lies dense in M with respect to the metric d, and no fire
signals occur in any of the configurations (s)(c), for s ∈ R≥0 with
s < t.

Proof Sketch. A proof is sketched in section 6.



Remark 5.16. For each positive integer k, under the restriction to
multigraphs whose maximum degree is bounded by k, for each such
multigraph, because directions only need to be locally unique (compare remark 3.9), the set {1, 2, . . . , 2k} can be chosen as the set of
directions, which makes the data sets of the kinds L and FD finite and
independent of the multigraph, the finite set P ({1, 2, . . . , k}) can be
chosen as the data set of the kind C, and, depending on the diameter d
of the multigraph, the finite set of words over Dir with maximum length
d can be chosen as the sets of words over Dir that occur in the data sets
~ V, and T — altogether, the data sets of all kinds
of the kinds M, U, U,
can be chosen to be finite but some depend on the multigraph.

Corollary 5.17. A discretisation of the signal machine S is a timeoptimal cellular automaton quasi-solution of the firing mob synchron-

59

signal machine S

isation problem over non-trivial, finite, and connected undirected multigraphs.

Proof Sketch. Let G be a non-trivial, finite, and connected undirected multigraph. It is made up of paths whose source and target vertices
are not of degree 2 and whose other vertices are of degree 2. Each such
path together with its inverse can be regarded as an undirected uberedge whose weight is the length of the path and whose ends are the
source and target vertices of the path or its inverse. We call vertices
that are not of degree 2 uber-vertices and vertices that are of degree 2
under-vertices.
Signals jump from vertices to vertices along edges. They collide when
they jump simultaneously from different vertices onto the same vertex or along the same edge but in different directions, or when signals
jump onto vertices on which stationary signals reside. Collisions in ubervertices are handled as collisions in vertices, collisions in under-vertices
are handled as collisions on edges (namely on the uber-edges that contain the under-vertices), and collisions in the midst of edges are handled
as collisions on edges (namely on the uber-edges that contain the edges).
Signals reach a vertex when they jump onto an uber-vertex, but not
when they jump onto an under-vertex (because the latter just means
that they travel along an uber-edge).
When signals collide in a vertex, be it a uber- or under-vertex, the
resulting signals are on the vertex. But when signals collide in the midst
of an edge, the resulting signals must be distributed onto both its ends
depending on their directions. This last case makes it rather cumbersome to write down the local transition functions explicitly. Vertices
must be virtually divided into multiple parts: One part that plays the
role of the vertex itself and, for each incident edge, an additional part
that plays the role of the midpoint of the edge together with the corresponding part of the other end of the edge. And signals must be cleverly
distributed onto these parts depending on their direction and how they
came into being, and collisions of signals must also be cleverly handled
taking the parts the involved signals came from and are on into account.
This discretisation of the signal machine is actually a cellular automaton over the multigraph with appropriate dummy neighbours that are
in a dead state (think for example of the multigraph as being embedded in a coloured S-Cayley graph with sufficient maximum degree and
of the vertices that do not belong the multigraph as being in a dead
state).

Remark 5.18. Jacques Mazoyer showed in 1987 that all infinitely
many divide signals of type n, for n ∈ N0 , that emanate from the
same point can be generated by a cellular automaton with only finitely
many states (see [Maz87]). And, as illustrated in remark 5.16, under
the restriction to multigraphs whose maximum degrees are uniformly

60

bounded by a constant, the data sets of all kinds can be chosen to be
finite but some depend on the multigraph. Therefore, depending on the
multigraph, the discretisation of S is a cellular automaton with a finite
number of states.

Open Problem 5.19. Are there time-optimal signal machine and cellular automaton solutions of the firing mob synchronisation problem
over non-trivial, finite, and connected undirected multigraphs whose
maximum degrees are uniformly bounded by a constant? Or, more specifically, is it possible to adapt the signal machine S (and thereby its
discretisation) such that the data sets of all kinds can be chosen to
be finite and independent of the multigraph (and thereby making its
discretisation have a finite set of states), for example by reducing the
number of midpoints that are and need to be determined?

6

proof sketch of the main theorem

In this section, we sketch a proof of main theorem 5.15. To that end,
let G = (V, E, ε) be a non-trivial, finite, and connected undirected
multigraph, let ω be an edge weighting of G, let M be a continuum representation of G, identify vertices of G and M and direction-preserving
paths from vertices to vertices of G and M , and let g be a vertex of M ,
which we call general. Furthermore, let S be the signal machine and let
c be the initial configuration of the firing mob synchronisation problem
from main theorem 5.15, and, whenever we talk about time evolution,
we mean the one of S that is in the configuration c at time 0, for example, at time t either means in configuration (t)(c) or essentially in
configuration (t)(c) but before events have been handled.
To proof main theorem 5.15, we need to ascertain that the signal
machine performs the following tasks: First, it cuts the multigraph
such that the multigraph turns into a virtual tree and looks like a
tree to all other tasks; secondly, it starts synchronisation of edges and
freezes it in time; thirdly, it determines the midpoints of all non-empty
direction-preserving paths from vertices to vertices in time; fourthly, it
determines which midpoints are the ones of the longest paths; fifthly,
starting from the midpoints of the longest paths, it traverses midpoints
of shorter and shorter paths and upon reaching midpoints of edges, it
thaws synchronisation of the respective edges; sixthly, all edges finish
synchronisation at time r + d with the creation of fire signals that lie
dense in the graph, where r is the radius of the graph with respect to
the general and d is the diameter of the graph.
That the first task is performed is evident from the definitions of
δe , δv , δevirtualTree , and δvvirtualTree . The only subtlety here is that besides leaf signals there cannot be stationary signals in virtual leaves or,
more precisely, at points that are virtually cut by leaf signals, because
stationary signals carry the semi-direction vry, which is insufficient to

61

general vertex g

associate them with one or the other leaf signal as is done for nonstationary signals. This is no problem because the other tasks do not
place stationary signals in (virtual) leaves. Therefore, we assume from
now on, without loss of generality, that the multigraph G is a tree.
That the second task is performed can be seen from a careful examtree , δ tree , and δ tree , where from
ination of the definitions of δetree , δvtree , δe,2
v,1
v,2
the third task it is used that midpoints of edges are found in time to
start the freezing process.
That the third, fourth, and fifth and sixth parts are performed is
proven in section 6.1, section 6.2, and section 6.3.
6.1 Midpoints are Determined
The midpoint of a path in a multigraph is the midpoint of its embedding
in the continuum representation of the multigraph as introduced in

midpoint mp of p

Definition 6.1. Let p be a path in G. The point mp = p(ω (p)/2) is
called midpoint of p.

Remark 6.2. The midpoint of the empty path in v is the vertex v
itself.

Remark 6.3. Let p, q, and q 0 be three paths such that τ (p) = σ (q ) =
σ (q 0 ), mp•q ∈ im p, and ω (q ) ≥ ω (q 0 ). Then, mp•q0 ∈ im p and
d(mp•q , mp•q0 ) = ω (p • q )/2 − ω (p • q 0 )/2 = ω (q )/2 − ω (q 0 )/2.
Analogously, let q, q 0 , and p be three paths such that τ (q ) = τ (q 0 ) =
σ (p), mq•p ∈ im p, and ω (q ) ≥ ω (q 0 ). Then, mq0 •p ∈ im p and
d(mq•p , mq0 •p ) = ω (q • p)/2 − ω (q 0 • p)/2 = ω (q )/2 − ω (q 0 )/2.



When the midpoints of non-empty direction-preserving paths are
found is stated in
Lemma 6.4. Let p be a non-empty direction-preserving path in G. The
midpoint signal that designates the midpoint of p is created at mp at
time tp = max{d(g, σ (p)), d(g, τ (p))} + ω (p)/2.

Proof Sketch. First, let the general g be the source or target of p.
Then, a find-midpoint signal with origin g of speed 1 and a slowed-down
find-midpoint signal with origin g of speed 1/3 travel from g towards
the other end of p. The find-midpoint signal is reflected at the other end
at time (2/2) · ω (p) and this reflection collides with the slowed-down
find-midpoint signal at the midpoint of p at time (3/2) · ω (p) creating
a midpoint signal for p (because both signals have the same origin).
Note that the time of collision is equal to tp (see figure 5.1a).

62

Secondly, let the general g lie on p without being its source or target.
Then, two find-midpoint signals with origin g travel from g to the ends
of p; the source of p is reached at time d(g, σ (p)) and the target at
time d(g, τ (p)). When such a signal reaches its end, it is reflected and
travels back. If d(g, σ (p)) = d(g, τ (p)), then this distance is equal to
ω (p)/2, the reflected signals collide at time ω (p) at the midpoint of p
creating a midpoint signal for p; note that the time of collision is equal
to tp . Otherwise, the reflected signal that is nearer to g reaches this
vertex first, where the signal is slowed down and travels towards the
other reflected signal with which it collides at the midpoint of p at time
tp (see figure 5.1b).
Lastly, let the general g not lie on p. Then, an initiate signal travels
from g to the nearest vertex v on p, where it creates two find-midpoint
signals with origin v that travel to the ends of p, are reflected at these
ends and travel back, one is slowed-down upon reaching v, and the
slowed-down signal collides with the reflected signal in the midpoint
of p at time d(g, v ) + max{d(v, σ (p)), d(v, τ (p))} + ω (p)/2 creating a
midpoint signal for p. Note that the time of collision is equal to tp . 
Remark 6.5. When reflected/slowed-down find-midpoint signals with
different origins collide, nothing happens, the signals just move on.
Hence, no points are falsely found to be midpoints.

That the midpoints of maximum-weight direction-preserving paths
are identical and found at time r + d is shown in
Lemma 6.6. All maximum-weight direction-preserving paths in G have
the same midpoint m̂ and the midpoint signals that designate the midpoints of such paths are created at m̂ at time r + d/2, where r =
maxv∈V d(g, v ) is the radius of G with respect to g and d = maxv,v0 ∈V d(v, v 0 )
is the diameter of G. Note that r is equal to the radius supm∈M d(g, m)
of M with respect to g and d is equal to the diameter supm,m0 ∈M d(m, m0 )
of M .

Proof. We prove both statements by contradiction.
First, suppose that there are two maximum-weight direction-preserving paths p̂ and p̂0 in G that do not have the same midpoint. Then, there
is a non-empty direction-preserving path pm in M from the midpoint
of p̂ to the one of p̂0 . And, there is a direction-preserving subpath p
of p̂ in M from one end of p̂ to its midpoint whose target-direction is
not the reverse of the source-direction of pm . And, there is a directionpreserving subpath p0 of p̂0 in M from the midpoint of p̂0 to one of its
ends whose source-direction is not the reverse of the target-direction of
pm . The concatenation of p, pm , and p0 is a direction-preserving path
from vertex to vertex in M whose length is equal to d/2 + ω (pm ) +
d/2 > d. It corresponds to a direction-preserving path p in G whose

63

g
v0

v
v0

v0
v 00

σ (p̂)

τ (p̂)

v
v
Figure 6.1: Schematic representation of the set-up of the proof of lemma 6.6
with the three cases of where v 0 may be located. The first case
corresponds to the vertices v and v 0 that are incident to the dotted
path, the second case to the dash-dotted path, and the third case
to the dashed path.

weight is greater than d, which contradicts that d is the diameter of
G. Therefore, all maximum-weight direction-preserving paths in G have
the same midpoint, which we denote by m̂.
Secondly, suppose that there is a maximum-weight direction-preserving path p̂ in G such that max{d(g, σ (p̂)), d(g, τ (p̂))} < r. Let v be a
vertex of G such that d(g, v ) = r, let pv , pσ , and pτ be the directionpreserving paths in G from v, σ (p̂), and τ (p̂) to g, let v 0 be the vertex
on pv and pσ or on pv and pτ that is the furthest from g, and let v 00 be
the vertex on p̂ that is the nearest to g. Then, the weight of pv is r, the
one of pσ is d(g, σ (p̂)) < r, and the one of pτ is d(g, τ (p̂)) < r. If v 0 lies
on the subpath of pσ from σ (p̂) to v 00 (which is equal to the subpath of
p̂ with the same ends), then let p be the direction-preserving path from
v over v 0 over v 00 to τ (p̂); if v 0 lies on the subpath of pτ from τ (p̂) to v 00
(which is equal to the subpath of the inverse of p̂ with the same ends),
then let p be the direction-preserving path from v over v 0 over v 00 to
σ (p̂); and otherwise, let p be the direction-preserving path from v over
v 0 over v 00 to τ (p̂) (we could have chosen σ (p̂) as well). See figure 6.1
for a schematic representation of the three cases.
In the first case, because the subpaths of pv and pσ from v 00 to g
coincide and the weight of pv is greater than the weight of pσ , the
weight of the subpath of pv from v over v 0 to v 00 (which is equal to the
subpath of p from v over v 0 to v 00 ) is greater than the weight of the
subpath of pσ from σ (p̂) over v 0 to v 00 (which is equal to the subpath of
p̂ from σ (p̂) over v 0 to v 00 ) and hence, because the subpaths of p and p̂
from v 00 to τ (p̂) coincide, the weight of p is greater than the weight of p̂.
In the second case, it follows analogously that the weight of p is greater
than the weight of p̂. And in the third case, because the subpaths of
pv and pσ from v 0 to g coincide and the weight of pv is greater than
the weight of pσ , the weight of the subpath of pv from v to v 0 is greater
than the weight of the subpath of pσ from σ (p̂) over v 00 to v 0 , hence
the weight of the subpath of p from v over v 0 to v 00 is greater than the

64

weight of the subpath of p̂ from σ (p̂) to v 00 , and therefore, the weight
of p is greater than the weight of p̂.
In either case, the inequality ω (p) > ω (p̂) contradicts that p̂ is a
maximum-weight path. Therefore, for each maximum-weight directionpreserving path in G, we have max{d(g, σ (p̂)), d(g, τ (p̂))} = r. It follows from lemma 6.4 that the midpoint signals that designate the midpoints of maximum-weight direction-preserving paths in G are created
at m̂ at time r + d/2.

It follows that the midpoints of non-empty non-maximum-weight
direction-preserving paths are found before the ones of maximum-weight
direction-preserving paths as shown in
Corollary 6.7. Let p be a non-empty direction-preserving path in G.
The midpoint signal that designates the midpoint of p is created at mp
before time r + d/2.

Proof. This is a direct consequence of lemmata 6.4 and 6.6, because
d(g, σ (p)) ≤ r, d(g, τ (p)) ≤ r, and ω (p) < d.

6.2 Midpoints of Maximum-Weight Paths are Recognised as Such
That the midpoints of maximum-weight direction-preserving paths are
recognised as such is sketched in
Remark 6.8. The first two reflected find-midpoint signals, or the first
two reflected and slowed-down find-midpoint signals to collide that originated at the same vertex and were reflected at the ends of a maximumweight direction-preserving path are marked at the time of collision and
hence recognise that the midpoint of the path they collide at is the one
of a maximum-weight direction-preserving path.

Proof Sketch. Let p̂ be a maximum-weight direction-preserving path
in G (see figure 6.2). Then, the ends v̂1 and v̂2 of p̂ are leaves. And,
among the first find-midpoint signals to reach the ends of p̂ are the two
that originated at the vertex v̂ on p̂ that is nearest to g, and, because
they travel alongside initiate signals, their reflections s and s0 at the
ends of p̂ are marked. When one of them reaches a vertex on its way
back it stays marked, because from all directions excluding from the
direction it is headed but including the direction it is coming from have
the marked reflected find-midpoint signals that originated at the vertex
just or already returned, which is memorised by a count signal that is
located at the vertex; the reason that such marked signals have already
returned is that otherwise there would be a direction-preserving path
with more weight than p̂ that would be the concatenation the maximal
subpath of p̂ that lies in the direction the signal is headed and a path

65

v̂1

g

u1

···

uk

v̂

w1

w`
m̂

v̂2
Figure 6.2: The path p̂ is drawn solid, the direction-preserving path from g to v̂ is drawn dotted, the
two subtrees in sbtrs(v̂ ) that contain v̂1 and v̂2 are represented by dashed triangles, and,
for each depicted vertex v, the possible existence of subtrees in sbtrs(v ) that correspond
to non-depicted edges that are incident to v is hinted at by dashed triangles.

that begins with one of the edges from which no marked signal has
returned yet. Note that the signals s and s0 travel back alongside the
marked reflected find-midpoint signals that originated at the vertices
the signals s and s0 passed by before they were reflected and that therefore, when they reach vertices on their way back, the count signals are
just updated and hence up-to-date.
When s and s0 reach the vertex they originated at at the same time,
then this vertex is found to be the midpoint of the path p̂ and, because
s and s0 are marked, it is recognised as the midpoint of a maximumweight path. When one of the signals, say s, reaches the vertex it originated at, namely v̂, first, then it is slowed down and spreads throughout
the graph away from the edge it comes from, in particular, one sloweddown find-midpoint signal, let us denote it by s00 , travels towards s0 .
When s00 reaches a vertex on its way towards s0 it stays marked, because from all directions excluding from the direction it is headed have
the slowest reflected find-midpoint signals that originated at the vertex
just or already returned, more precisely, from all directions excluding
from the direction it is coming from and the one it is headed have
the marked reflected find-midpoint signals that originated at the vertex just or already returned and from the direction it is coming from
has the slowest but unmarked reflected find-midpoint signal that originated at the vertex and the first marked slowed-down find-midpoint
signal just returned. When s00 and s0 collide, the midpoint of p̂ is found

66

and, because s00 and s0 are marked, it is recognised as the midpoint of
a maximum-weight path.
A detailed proof is given in the remainder of the present subsection.


Symbolic notations for the predicates is a vertex of and is an edge
of are introduced in
Definition 6.9. Let T = (W , F ) be a subtree of G, let v be a vertex
of G, and let e be an edge of G. We write v ∈ T instead of v ∈ W and
e ∈ T instead of e ∈ F .


v∈T
e∈T

The set of greatest subtrees of a vertex v that correspond to its
incident edges is named in
Definition 6.10. Let v be a vertex of G.
a. Let Ev be the set of edges that are incident to v, and, for each
edge e ∈ Ev , let Tv,e be the greatest subtree of G that is rooted
at v, contains the edge e, and does not contain any other edge
of Ev (note that by greatest we mean greatest with respect to
the number of vertices). The set {Tv,e | e ∈ Ev } is denoted by
sbtrs(v ).

set sbtrs(v )

b. The set
max sbtrs(v ) = arg max kT kv

set max sbtrs(v )
of trees

T ∈sbtrs(v )

is the set of maximum-radius trees of sbtrs(v ). In the case that
it is a singleton set, we denote its one and only element by T̂ v .

tree T̂ v

c. The set
sbtrs(v ) =

arg max
T ∈sbtrs(v )rmax sbtrs(v )

kT kv

is the set of second-maximum-radius trees of sbtrs(v ).

set sbtrs(v ) of
trees


Remark 6.11. For each leaf v of G, the set max sbtrs(v ) is a singleton
and it is equal to sbtrs(v ), and the set sbtrs(v ) is empty.

Things associated with a greatest subtree of a vertex are introduced
in
Definition 6.12. Let v be a vertex of G and let T be a tree of sbtrs(v ).
a. Let e be the edge of T that is incident to v. The direction that
leads from v onto e is uniquely determined by T and is denoted
by dirv (T ).

67

direction dirv (T )

b. The non-negative integer kT kv = maxv0 ∈T d(v, v 0 ) is called radius
of T with respect to v.

radius kT kv of T
with respect to v

c. Let PT be the set of direction-preserving paths in T . The set
max pthsv (T ) = {p ∈ PT | σ (p) = v and ω (p) = kT kv }

set max pthsv (T )
of paths

is the set of maximum-weight direction-preserving paths from v
in T .
d. The set
max vrtcsv (T ) = {τ (p) | p ∈ max pthsv (T )}

set max vrtcsv (T )
of vertices

is the set of vertices in T that are furthest away from v.



Remark 6.13. We have |sbtrs(v )| = deg(v ) and dirv (sbtrs(v )) =
dir(v ).

Remark 6.14. Each vertex of max vrtcsv (T ) is a leaf.



The unique direction-preserving path from one vertex to another is
named in

path pv,v0
set Vv,v0 of
vertices

Definition 6.15. Let v and v 0 be two vertices of G. The directionpreserving path in G from v to v 0 is denoted by pv,v0 and the vertices
on this path are denoted by Vv,v0 .

When and why count signals, initiate signals, and (maybe-marked
slowed-down/reflected) find-midpoint signals are created and how they
spread throughout the tree is said in
Remark 6.16. Let the signal machine S be in the configuration cI at
time 0.
a. At time 0, a count signal with empty memory is created at g, and
initiate signals, find-midpoint signals with origin g, and maybemarked slowed-down find-midpoint signals with origin g and reflection vertex g are sent from g in all directions, where the sloweddown signal is marked if and only if g is a leaf. For each vertex
v ∈ V r{g}, at time d(g, v ), an initiate signal reaches v from the
direction towards g, whereupon
a) a count signal with empty memory is created at v,
b) initiate signals are sent from v in all directions away from g,
and
c) find-midpoint signals with origin v, and maybe-marked sloweddown find-midpoint signals with origin v and reflection vertex v are sent from v in all directions,

68

where the slowed-down signal is marked if and only if v is a leaf.
In short, initiate signals spread from g to all leaves, where they
vanish, and they initiate the search for midpoints at all vertices.
Note that to simplify the exposition of the forthcoming proofs,
we also create count signals at leaves.
b. Let v be a vertex of G. As said above, at time d(g, v ), findmidpoint signals with origin v, and maybe-marked slowed-down
find-midpoint signals with origin v and reflection vertex v are sent
from v in all directions, where the slowed-down signal is marked
if and only if v is a leaf. For each vertex v 0 ∈ V r{v},
a) at time d(g, v ) + d(v, v 0 ), a find-midpoint signal with origin v reaches v 0 from the direction towards v, whereupon a
maybe-marked reflected find-midpoint signal with origin v
and reflection vertex v 0 is sent from v 0 towards v and findmidpoint signals with origin v are sent from v 0 in all directions away from v, where the reflected signal is marked if and
only if v is a leaf and an initiate signal just reached v 0 (the
latter is the case if and only if d(g, v ) + d(v, v 0 ) = d(g, v 0 )),
and,
b) at time d(g, v ) + 3 · d(v, v 0 ), a maybe-marked slowed-down
find-midpoint signal with origin v and reflection vertex v
reaches v 0 from the direction towards v, whereupon maybemarked slowed-down find-midpoint signals with origin v and
reflection vertex v are sent from v 0 in all directions away from
v. Note that even if the slowed-down signal that is sent from
v at time d(g, v ) is marked, the slowed-down signal that
reaches v 0 may be unmarked, and even if the latter signal is
marked, the slowed-down signals that are sent from v 0 may
be unmarked.
In short, find-midpoint signals with origin v and maybe-marked
slowed-down find-midpoint signals with origin v and reflection
vertex v spread from v to all leaves, and whenever one of the
former signals reaches a vertex, it is also reflected. Note that
to simplify the exposition of the forthcoming proofs, we talk as
if maybe-marked slowed-down find-midpoint signals only vanish
at leaves, although when a marked slowed-down find-midpoint
signal collides with a marked reflected find-midpoint signal with
the same origin, both signals vanish.
c. Let v and v 0 be two vertices of G such that v 6= v 0 . As said
above, at time d(g, v ) + d(v, v 0 ) a maybe-marked reflected findmidpoint signal with origin v and reflection vertex v 0 is sent from
v 0 towards v. For each vertex w on the direction-preserving path
from v 0 to v except for v 0 , at time d(g, v ) + d(v, v 0 ) + d(v 0 , w ),
the signal reaches w from the direction towards v 0 , whereupon,

69

if w 6= v, the signal is sent from w towards v, and otherwise,
maybe-marked slowed-down find-midpoint signals with origin v
and reflection vertex v 0 are sent from v in all directions away from
v0.
And, for each vertex v 00 of G that from the viewpoint of v lies
in a direction away from v 0 , which means that v 00 6= v and there
is a tree T ∈ sbtrs(v ) such that v 0 ∈
/ T and v 00 ∈ T , at time
0
0
00
d(g, v ) + d(v, v ) + d(v , v ) + 3 · d(v, v ), a maybe-marked sloweddown find-midpoint signal with origin v and reflection vertex v 0
reaches v 00 , whereupon maybe-marked slowed-down find-midpoint
signals with origin v and reflection vertex v 0 are sent from v 00 in
all directions away from v (or, equivalently, away from v 0 ).
In short, each maybe-marked reflected find-midpoint signal travels
back to its origin and when it reaches its origin, it is slowed-down
and spreads to all leaves away from its reflection vertex. Note
that unmarked signals never become marked, but marked signals
may become unmarked; precisely when the latter does or does
not happen is answered in the present subsection.
What is said above is evident from the definition of the signal machine
S (if it is carefully studied).

When and why leaves sent marked reflected/slowed-down find-midpoint
signals is said in
Lemma 6.17. Let v be a leaf of G. At time d(g, v ), an initiate signal
reaches v, for each vertex w ∈ Vg,v r{v}, a find-midpoint signal with
origin w reaches v, and no other find-midpoint signal reaches v, whereupon
a. for each vertex w ∈ Vg,v r{v}, a marked reflected find-midpoint
signal with origin w and reflection vertex v is sent from v towards
w, which is the only possible direction,
b. a marked slowed-down find-midpoint signal with origin v and reflection vertex v is sent from v towards w, and
c. no other marked signal is sent from v.
And before time d(g, v ) no signals reach and are sent from v, and after
time d(g, v ) no marked signals are sent from v (because after this time
no initiate signal reaches v).

Proof. This is a direct consequence of remark 6.16 and the definition
of S.

When does a signal that is sent from a vertex towards the general at
a special time reach the next vertex is answered in

70

Lemma 6.18. Let v be a vertex of G, let T be a tree of sbtrs(v ) r
max sbtrs(v ) such that either v = g or g ∈
/ T , and let v 0 be the one and
only neighbour of v in T . Then,
a. max sbtrs(v 0 ) is a singleton set and its only element T̂ v0 contains
v,
 0

{v },
[
b. max vrtcsv (T ) =
·



if v 0 is a leaf,
max vrtcsv0 (T 0 ),

otherwise,

T 0 ∈sbtrs(v 0 )

c. kT kv = d(v, v 0 ) + maxT 0 ∈sbtrs(v0 ) kT 0 kv0 , and
d. when a signal of speed 1 is sent from v 0 towards v at time d(g, v 0 ) +
2 · maxT 0 ∈sbtrs(v0 ) kT 0 kv0 , it reaches v at time d(g, v ) + 2 · kT kv ,
where in the case that sbtrs(v 0 ) is empty, we define maxT 0 ∈sbtrs(v0 ) kT 0 kv0
as 0.

Proof. The first item is evident, the second and third follow from it,
and the fourth follows from the third with d(g, v 0 ) = d(g, v ) + d(v, v 0 )
and the fact that the signal needs the time span d(v, v 0 ) to traverse the
edge from v 0 to v.

The set of all non-leaf vertices whose unique maximum-radius tree
contains the general is named in
Definition 6.19. The set of all non-leaf vertices v of G such that
max sbtrs(v ) is a singleton set and its only element T̂ v contains the
vertex g, is denoted by Vg .


set Vg of vertices

Remark 6.20. For each vertex v ∈ Vg , each tree T ∈ sbtrs(v ) r {T̂ v },
and each vertex v 0 of T , we have v 0 ∈ Vg . And, for each vertex v ∈ Vg ,
the set sbtrs(v ) is non-empty and, for each tree T ∈ sbtrs(v ), we have
kT kv = maxT ∈sbtrs(v ) kT kv .

When and why non-leaf vertices whose unique maximum-radius tree
contains the general sent marked reflected/slowed-down find-midpoint
signals is shown in
Lemma 6.21. For each vertex v ∈ Vg , at time d(g, v ) + 2 · maxT ∈sbtrs(v ) kT kv ,
a. the count signal at v, before it is updated, has the memory dir(v ) r
dirv (sbtrs(v ) ∪ {T̂ v }),
b. for each tree T ∈ sbtrs(v ), each leaf v~ ∈ max vrtcsv (T ), and
each vertex w ∈ Vg,v , a marked reflected find-midpoint signal with
origin w and reflection vertex v~ reaches v from direction dirv (T ),
and

71

c. no other marked reflected find-midpoint signal reaches v,
whereupon
a. the count signal at v, after it is updated, has the memory dir(v ) r
{dirv (T̂ v )},
b. for each tree T ∈ sbtrs(v ), each leaf v~ ∈ max vrtcsv (T ), and each
vertex w ∈ Vg,v r{v}, a marked reflected find-midpoint signal
with origin w and reflection vertex v~ is sent from v in the direction
dirv (T̂ v ) towards w, and no other marked reflected find-midpoint
signal with origin w and reflection vertex v~ is sent from v, and,
c. for each tree T ∈ sbtrs(v ), each leaf v~ ∈ max vrtcsv (T ), and
each direction d ∈ dir(v ) r {dirv (T )}, a marked slowed-down findmidpoint signal with origin v and reflection vertex v~ is sent from
v in direction d (note that dirv (T̂ v ) ∈ dir(v ) r {dirv (T )}), and,
no other marked slowed-down find-midpoint signal with origin v
and reflection vertex v~ is sent from v.
And before time d(g, v ) + 2 · maxT ∈sbtrs(v ) kT kv , marked signals may
reach v but no marked signal is sent from v, and after that time, no
marked signals as above are sent from v.

Proof. We prove this by induction on nv = max(W ,F )∈sbtrs(v )r{T̂ v } |F |,
for v ∈ Vg . For brevity though, we only treat the existence of signals
and not their absence.
Base Case (see figure 6.3). Let v ∈ Vg such that nv = 1. And, let
T ∈ sbtrs(v ) r {T̂ v }. Then, T consists of one edge e whose one end
is v, whose other end is a leaf v 0 , and whose weight is kT kv . According to lemma 6.17, at time d(g, v 0 ) = d(g, v ) + kT kv , for each vertex
w ∈ Vg,v0 r{v 0 } = Vg,v , a marked reflected find-midpoint signal with
origin w and reflection vertex v 0 is sent from v 0 towards v, in particular, one with origin v. These signals reach v at time d(g, v ) + 2 · kT kv ,
whereupon
a. the count signal at v memorises the direction dirv (T ) (because a
marked reflected find-midpoint signal with origin v reached v),
b. for each vertex w ∈ Vg,v r{v}, a maybe-marked reflected findmidpoint signal with origin w and reflection vertex v 0 is sent from
v in the direction dirv (T̂ v ) towards w, and
c. for each direction d ∈ dir(v ) r {dirv (T )}, a maybe-marked sloweddown find-midpoint signal with origin v and reflection vertex v 0
is sent from v in direction d.
On the timeline, for the trees of sbtrs(v ) r {T̂ v } in non-decreasing order with respect to the radius and at the same time for trees with the
same radius, the signals reach v and are sent from v. For those trees

72

g

v0

w

v

v 00
v 000

Figure 6.3: Schematic representation of the set-up of the base case of the
proof of lemma 6.21. The possible existence of subtrees of vertices
is hinted at by dashed triangles.

g

w

v0
v

v 00
v 000

Figure 6.4: Schematic representation of the set-up of the inductive step of the
proof of lemma 6.21. The possible existence of subtrees of vertices
is hinted at by dashed triangles.

whose radius is less than the second greatest radius among the trees
of sbtrs(v ), which is maxT ∈sbtrs(v ) kT kv , the aforementioned maybemarked signals that are sent from v are unmarked (because the memory
of the count signal, after it is updated, does neither contain the directions of dirv (sbtrs(v )) nor the direction dirv (T̂ v )). And, for the trees
of sbtrs(v ), the aforementioned maybe-marked signals that are sent
from v are marked (because the count signal, after it is updated, has
the memory dir(v ) r {dirv (T̂ v )}). In conclusion, at time d(g, v ) + 2 ·
maxT ∈sbtrs(v ) kT kv , what is to be proven holds.
Inductive Step (see figure 6.4). Let v ∈ Vg such that nv ≥ 2 and such
that what is to be proven holds for each vertex v 0 ∈ Vg with nv0 < nv ,
which is the inductive hypothesis. And, let T ∈ sbtrs(v ) r {T̂ v }, let e
be the edge of T whose one end is v, and let v 0 be the other end of e.
The vertex v 0 is either a leaf or an element of Vg with nv0 < nv .
In the first case, according to lemma 6.17, at time d(g, v 0 ) = d(g, v ) +
d(v, v 0 ), for each vertex w ∈ Vg,v0 r{v 0 } = Vg,v , a marked reflected
find-midpoint signal with origin w and reflection vertex v 0 is sent from
v 0 towards v; note that v 0 is the one and only element of max vrtcsv (T ),
the set sbtrs(v 0 ) is empty, and we define maxT 0 ∈sbtrs(v0 ) kT 0 kv0 as 0 (see
lemma 6.18). In the second case, according to the inductive hypothesis,
at time d(g, v 0 ) + 2 · maxT 0 ∈sbtrs(v0 ) kT 0 kv0 , for each tree T 0 ∈ sbtrs(v 0 ),
each leaf v~0 ∈ max vrtcsv0 (T 0 ), and each vertex w ∈ Vg,v0 r{v 0 } = Vg,v ,
a marked reflected find-midpoint signal with origin w and reflection

73

vertex v~0 is sent from v 0 towards v; note that the set of all vertices v~0
is equal to max vrtcsv (T ) (see lemma 6.18).
In both cases, the marked signals reach v at time d(g, v ) + d(v, v 0 ) +
2 · maxT 0 ∈sbtrs(v0 ) kT 0 kv0 + d(v 0 , v ), which is equal to d(g, v ) + 2 · kT kv ,
whereupon
a. the count signal at v memorises the direction dirv (T ) (because
at least one marked reflected find-midpoint signal with origin v
reached v),
b. for each leaf v~ ∈ max vrtcsv (T ) and each vertex w ∈ Vg,v r{v},
a maybe-marked reflected find-midpoint signal with origin w and
reflection vertex v~is sent from v in the direction dirv (T̂ v ) towards
w, and,
c. for each leaf v~ ∈ max vrtcsv (T ) and each direction d ∈ dir(v ) r
{dirv (T )}, a maybe-marked slowed-down find-midpoint signal with
origin v and reflection vertex v~ is sent from v in direction d.
It follows verbatim as in the base case, that what is to be proven holds.


The set of all vertices whose unique maximum-radius tree does not
contain the general is named in

set Ug of vertices

Definition 6.22. The set of all vertices v of G such that max sbtrs(v )
is a singleton set and its only element T̂ v does not contain the vertex
g, is denoted by Ug .

Remark 6.23. We have g ∈
/ Ug . And, for each vertex v ∈ Ug , we
have Vg,v r{g} ∈ Ug , the vertex v is not a leaf and the set sbtrs(v ) is
non-empty.

The maximal subtree of a non-general vertex that contains the general is named in

tree

Tvg

Tgg = 0

Definition 6.24. Let v be a vertex of G such that v 6= g. The tree of
sbtrs(v ) that does contain the vertex g is denoted by Tvg . And to avoid
case differentiations, we define Tgg as the number 0.

The vertices of the maximal path from a vertex to the general whose
vertices excluding its source have the subtree that contains the general
as second-maximum-radius subtree is named in

set Wg,v of
vertices

Definition 6.25. Let v be a vertex of Ug , and let p be the maximumweight subpath of pg,v such that τ (p) = v and, for each vertex w on p
with w 6= σ (p), we have Twg ∈ sbtrs(w ). The set of the vertices on p is
denoted by Wg,v . See figure 6.5.


74

g w00

w0 w v

Figure 6.5: Schematic representation of G, where v ∈ Ug , Wg,v =
{w00 , w0 , w, v}, Wg,w = {w00 , w0 , w}, Wg,w0 = {w00 , w0 }, Wg,w00 =
{w00 }, and subtrees of vertices and their radii are depicted as
dashed triangles of various sizes.

Remark 6.26. We have v ∈ Wg,v r {g} ⊆ Ug . And, for each w ∈ Wg,v ,
we have Wg,w ⊆ Wg,v . And, if Tvg ∈ sbtrs(v ), then Wg,v = Wg,v0 ∪ {v},
where v 0 is the neighbour of v on pg,v .

When and why vertices whose unique maximum-radius tree does not
contain the general sent marked reflected/slowed-down find-midpoint
signals is shown in
Lemma 6.27. For each vertex v ∈ Ug , at time d(g, v ) + 2 · maxT ∈sbtrs(v ) kT kv ,
a. the count signal at v, before it is updated, has the memory dir(v ) r
dirv (sbtrs(v ) ∪ {T̂ v }),
b. for each tree T ∈ sbtrs(v ) and each leaf v~ ∈ max vrtcsv (T ), a
maybe-marked reflected find-midpoint signal with origin v and reflection vertex v~ reaches v from direction dirv (T ), where the reflected signal is marked if and only if T 6= Tvg , and,
c. for each vertex w ∈ Wg,v r {v}, each tree T ∈ sbtrs(w ) r {Twg },
and each leaf w~ ∈ max vrtcsw (T ), a marked slowed-down findmidpoint signal with origin w and reflection vertex w~ reaches v
from the direction towards w, which is the direction dirv (Tvg ),
whereupon
a. the count signal at v, after it is updated, has the memory dir(v ) r
{dirv (T̂ v )},
b. for each tree T ∈ sbtrs(v ) r {Tvg }, each leaf v~ ∈ max vrtcsv (T ),
and each direction d ∈ dir(v ) r {dirv (T )}, a marked slowed-down
find-midpoint signal with origin v and reflection vertex v~ is sent
from v in direction d (note that {dirv (T̂ v ), dirv (Tvg )} ⊆ dir(v ) r
{dirv (T )}), and,
c. for each vertex w ∈ Wg,v r {v}, each tree T ∈ sbtrs(w ) r {Twg },
each leaf w~ ∈ max vrtcsw (T ), and each direction d ∈ dir(v ) r
{dirv (Tvg )}, a marked slowed-down find-midpoint signal with origin w and reflection vertex w~ is sent from v in direction d (note

75

that dirv (T̂ v ) ∈ dir(v ) r {dirv (Tvg )} and that, if w = g, then
sbtrs(w ) r {Twg } = sbtrs(w )).

Proof. We prove this by induction on nv = |Vg,v |, for v ∈ Ug .
Base Case (compare figure 6.6). Let v ∈ Ug such that nv = 1.
First, for each tree T ∈ sbtrs(v ) r {Tvg , T̂ v }, according to lemma 6.17,
if the neighbour of v in T is a leaf, or lemma 6.21, otherwise, and
lemma 6.18, at time d(g, v ) + 2 · kT kv , for each leaf v~ ∈ max vrtcsv (T ),
a marked reflected find-midpoint signal with origin v and reflection
vertex v~ reaches v from direction dirv (T ), whereupon
a. the count signal at v memorises the direction dirv (T ),
b. for each leaf v~ ∈ max vrtcsv (T ) and each direction d ∈ dir(v ) r
{dirv (T )}, a maybe-marked slowed-down find-midpoint signal with
origin v and reflection vertex v~ is sent from v in direction d.
Secondly, according to remark 6.16, at time d(g, v ) + 2 · kTvg kv , for
each leaf v~ ∈ max vrtcsv (Tvg ), a maybe-marked reflected find-midpoint
signal with origin v and reflection vertex v~ reaches v from direction
dirv (Tvg ). This signal is actually unmarked, because it was reflected at
v~ at time d(g, v ) + kTvg kv = d(g, v ) + d(v, v~), which, because v 6= g
and v~ ∈ Tvg , is greater than the only time, namely d(g, v~), at which an
initiate signal reaches v.
~
Thirdly, because Ug is non-empty, we have g ∈ Vg and v ∈ T̂ g .
According to lemma 6.21, at time 2 · maxT ∈sbtrs(g) kT kg , for each tree
T ∈ sbtrs(g), and each leaf g~ ∈ max vrtcsg (T ), a marked slowed-down
find-midpoint signal with origin g and reflection vertex g~ is sent from g
towards v; note that the set of all vertices g~ is equal to max vrtcsv (Tvg )
(compare lemma 6.18). The marked signals reach v from the direction
towards g, which is the direction dirv (Tvg ), at time 2 · maxT ∈sbtrs(g) kT kg +
3 · d(g, v ) = d(g, v ) + 2 · kTvg kv , whereupon
a. the count signal at v memorises the direction dirv (Tvg ) and,
b. for each leaf g~ ∈ max vrtcsv (Tvg ) and each direction d ∈ dir(v ) r
{dirv (Tvg )}, a maybe-marked slowed-down find-midpoint signal
with origin g and reflection vertex g~ is sent from v in direction d.
Altogether, on the timeline, for the trees of sbtrs(v ) r {T̂ v } in nondecreasing order with respect to the radius and at the same time for
trees with the same radius, the signals reach v and are sent from v. For
those trees whose radius is less than the second greatest radius among
the trees of sbtrs(v ), which is maxT ∈sbtrs(v ) kT kv , the aforementioned
maybe-marked signals that are sent from v are unmarked (because the
memory of the count signal, after it is updated, does neither contain the
directions of dirv (sbtrs(v )) nor the direction dirv (T̂ v )). And, for the
trees of sbtrs(v ), the aforementioned maybe-marked signals that are

76

g

v0

v

Figure 6.6: Schematic representation of the set-up of the inductive step of the
proof of lemma 6.27. The possible existence of subtrees of vertices
and their radii is hinted at by dashed triangles of various sizes.

sent from v are marked (because the count signal, after it is updated,
has the memory dir(v ) r {dirv (T̂ v )}). Note that, if Tvg ∈ sbtrs(v ), then
Wg,v r {v} = {g}, and otherwise, Wg,v r {v} = ∅. In conclusion, at time
d(g, v ) + 2 · maxT ∈sbtrs(v ) kT kv , what is to be proven holds.
Inductive Step (see figure 6.6). Let v ∈ Ug such that nv ≥ 2 and such
that what is to be proven holds for each vertex v 0 ∈ Ug with nv0 < nv ,
which is the inductive hypothesis.
First, for each tree T ∈ sbtrs(v ) r {Tvg , T̂ v }, the same as in the base
case happens.
Secondly, as in the base case, at time d(g, v ) + 2 · kTvg kv , for each leaf
v~ ∈ max vrtcsv (Tvg ), an unmarked reflected find-midpoint signal with
origin v and reflection vertex v~ reaches v from direction dirv (Tvg ).
Thirdly, let v 0 be the neighbour of v in Tvg . Then, v 0 ∈ Vg,v r{g} ⊆ Ug
and nv0 < nv . According to the inductive hypothesis, at time d(g, v 0 ) +
2 · maxT 0 ∈sbtrs(v0 ) kT 0 kv0 ,
a. for each tree T 0 ∈ sbtrs(v 0 ) r {Tvg0 } and each leaf v~0 ∈ max vrtcsv0 (T 0 ),
a marked slowed-down find-midpoint signal with origin v 0 and reflection vertex v~0 is sent from v 0 towards v, and,
b. for each vertex w0 ∈ Wg,v0 r {v 0 }, each tree T 0 ∈ sbtrs(w0 ) r
{Twg0 }, each leaf w~0 ∈ max vrtcsw0 (T 0 ), a marked slowed-down
find-midpoint signal with origin w0 and reflection vertex w~0 is
sent from v 0 towards v.
The marked signals reach v from from direction dirv (Tvg ) at time d(g, v 0 ) +
2 · maxT 0 ∈sbtrs(v0 ) kT 0 kv0 + 3 · d(v 0 , v ) = d(g, v ) + 2 · kTvg kv , whereupon
a. the count signal at v memorises the direction dirv (Tvg ) and,
b. for each vertex w ∈ Wg,v0 , each tree T ∈ sbtrs(w ) r {Twg }, each
leaf w~ ∈ max vrtcsw (T ), and each direction d ∈ dir(v ) r {dirv (Tvg )},
a maybe-marked slowed-down find-midpoint signal with origin w
and reflection vertex w~ is sent from v in direction d.
Note that, if Tvg ∈ sbtrs(v ), then Wg,v r {v} = Wg,v0 , and otherwise,
Wg,v r {v} = ∅. With that it follows verbatim as in the base case, that
what is to be proven holds.


77

That midpoints of maximum-weight direction-preserving paths are
recognised as such is shown in
Theorem 6.28. Let p̂ be a maximum-weight direction-preserving path
in G, let v̂ be the vertex on p̂ that is nearest to g, let v̂1 and v̂2 be the
two ends of p̂ such that d(v̂, v̂1 ) ≤ d(v̂, v̂2 ), and let m̂ be the midpoint
of p̂. At time r + d/2, at the midpoint m̂,
a. if d(v̂, v̂1 ) = d(v̂, v̂2 ), two marked reflected find-midpoint signals
with origin v̂ and reflection vertices v̂1 and v̂2 collide, and
b. otherwise, a marked slowed-down find-midpoint signal with origin
v̂ and reflection vertex v̂1 collides with a marked reflected findmidpoint signal with origin v̂ and reflection vertex v̂2 .

Proof Sketch. From a broad perspective and ignoring boundary
cases the following happens in the given order (see figure 6.7d). At time
0, an initiate signal is sent from g towards v̂. At time d(g, v̂ ), this signal
reaches v̂, whereupon find-midpoint signals with origin v̂ are sent from v̂
in all directions. At time d(g, v̂ ) + kTv̂g kv̂ , the slowest but unmarked reflected find-midpoint signal with origin v̂ returns to v̂ from the direction
towards g. At time d(g, v̂ ) + 2 · d(v̂, v̂1 ), the slowest and marked reflected find-midpoint signal with origin v̂ returns to v̂ from the direction towards v̂1 , whereupon a marked slowed-down find-midpoint signal with
origin v̂ is sent towards v̂2 . At time d(g, v̂ ) + 2 · d(v̂, v̂1 ) + 3 · d(v̂, m̂) =
d(g, m̂) + 2 · d(v̂1 , m̂) = r + d/2, this signal reaches m̂. And, at the
same time, which is equal to d(g, v̂ ) + d(v̂, v̂2 ) + d(v̂2 , m̂), the slowest and marked reflected find-midpoint signal with origin v̂ that is on
its way to return to v̂ from the direction towards v̂2 reaches m̂. The
two marked signals collide at m̂ recognising it as the midpoint of a
maximum-weight path.
The slowest reflected find-midpoint signal with origin v̂ that returns
to v̂ from the direction towards g is unmarked, because it reaches the
leaf it is reflected at later than the initiate signal and is never marked
in the first place. The slowest reflected find-midpoint signal with origin
v̂ that returns to v̂ from the direction towards v̂1 is marked, because
it reaches the leaf v̂1 alongside initiate signals and at each vertex on
its way back, it is the penultimate marked signal to return (this is
essentially lemma 6.21). For the same reason, the signal from the direction towards v̂2 is marked when it reaches m̂. And, the slowed-down
find-midpoint signal with origin v̂ that reaches m̂ from the direction
towards v̂ is marked, because at each vertex it reaches on its way, it is
the penultimate marked signal to do so (this is essentially lemma 6.27).
Note that, for each vertex u on the path from g to m̂ except for g,
the direction towards g is added to the memory of the count signal at
u, because a marked slowed-down find-midpoint signal whose origin is
not u reaches u from that direction, and the other directions are added,
because marked reflected find-midpoint signals with origin u reach it

78

from those directions; for all other vertices, the latter is the reason the
directions are added.

Proof. Let v1 and v2 be the neighbours of m̂ on p̂ such that d(v1 , v̂1 ) <
d(v2 , v̂1 ) (or, equivalently, d(v1 , v̂2 ) > d(v2 , v̂2 )).
First, let d(v̂, v̂1 ) = d(v̂, v̂2 ) (see figures 6.7a and 6.7c). Then, v̂ = m̂,
and, for each index i ∈ {1, 2}, we have vi 6= g (because, if g lies on p̂,
then g = v̂ = m̂ 6= vi , and otherwise, g does not lie on p̂ but vi
does), and, vi is either a leaf or an element of Vg (because max sbtrs(vi )
consists of the tree of sbtrs(vi ) that contains v̂j , where j ∈ {1, 2} r {i},
and this tree, namely T̂vi , contains g). Hence, according to lemma 6.17
or lemma 6.21, for each index i ∈ {1, 2}, at time d(g, vi ) + 2 · d(vi , v̂i ),
a marked reflected find-midpoint signal with origin m̂ and reflection
vertex v̂i is sent from vi towards m̂, and at time d(g, m̂) + 2 · d(m̂, v̂i ) =
r + d/2, it reaches m̂, where it collides with the other signal.
Secondly, let d(v̂, v̂1 ) 6= d(v̂, v̂2 ) (see figures 6.7b and 6.7d). Furthermore, let Xg be the union of the set of leaves and the set Vg . Then,
v̂ 6= m̂, and either v1 = g = v̂ ∈ Xg or v1 ∈ Ug , and v2 ∈ Xg (because
otherwise, there would be a direction-preserving path with more weight
than p̂, which contradicts that p̂ has maximum-weight).
According to lemma 6.17 or lemma 6.21, at time d(g, v2 ) + 2 · d(v2 , v̂2 ),
a marked reflected find-midpoint signal with origin v̂ and reflection vertex v̂2 is sent from v2 towards m̂, and at time d(g, v2 ) + 2 · d(v2 , v̂2 ) +
d(v2 , m̂) = r + d/2 it reaches m̂.
If v1 = g = v̂ ∈ Xg , then, according to lemma 6.17 or lemma 6.21, at
time 2 · d(v̂, v̂1 ) (which is 0 in the case that v1 is a leaf, because in this
case v1 = v̂ = v̂1 ), a marked slowed-down find-midpoint signal with
origin v̂ and reflection vertex v̂1 is sent from v̂ towards m̂, and at time
2 · d(v̂, v̂1 ) + d(v̂, m̂) = r + d/2, it reaches m̂.
Otherwise, we have v̂ ∈ Wg,v1 r {v1 } (because, for each vertex v ∈
Vv̂,v1 r{v̂}, the set max sbtrs(v ) consists of the tree of sbtrs(v ) that
contains v̂2 , the tree Tvg contains v̂1 , and due to the maximality of p̂,
except for T̂v , there can be no tree of sbtrs(v ) with a greater radius than
Tvg ), and hence, according to lemma 6.27, at time d(g, v1 ) + 2 · d(v1 , v̂1 ),
a marked slowed-down find-midpoint signal with origin v̂ and reflection
vertex v̂1 is sent from v1 towards m̂, and at time d(g, v1 ) + 2 · d(v1 , v̂1 ) +
d(v1 , m̂) = r + d/2, it reaches m̂.
In either case, at time r + d/2, at the midpoint m̂, a marked sloweddown find-midpoint signal with origin v̂ and reflection vertex v̂1 collides
with a marked reflected find-midpoint signal with origin v̂ and reflection
vertex v̂2 .

Remark 6.29. On the other hand, for each direction-preserving path
that does not have maximum-weight, whenever its midpoint is found,
one of the signals is unmarked and hence the midpoint is not falsely

79

T̂ v2

T̂ v1
v1 g

v̂1

v2

v̂2

m̂

(a) g = v̂ = m̂

T̂ v2

T̂ v1

g

v̂1

v1

v2

v̂2

m̂

(b) g = v̂ 6= m̂

v̂1

g

v̂
m̂

v1
v2

v̂2
(c) g 6= v̂ = m̂

v̂1

g

v̂
v1
m̂

v2

v̂2
(d) g 6= v̂ 6= m̂

Figure 6.7: Schematic representation of the set-up of the proof of theorem 6.28. Vertices are depicted
as dots, points that may or may not be vertices are depicted as circles, paths that may
consist of more than one edge are drawn dotted, and paths that consist of precisely one
edge are drawn solid.

80

thought to be one of a maximum-weight path. The interested reader
may prove that for herself.

6.3 Thaw Signals Traverse Midpoints and Thaw Synchronisation of
Edges Just in Time
The inverse of a path is its traversal from target to source as given in
Definition 6.30. Let p = (v0 , e1 , v1 , . . . , en , vn ) be a path in G. The
path inv(p) = (vn , en , . . . , v1 , e1 , v0 ) is called inverse of p.


inverse inv(p) of p

Remark 6.31. The inverse of an empty path is the empty path itself.


Remark 6.32. The weight and the midpoint of the inverse of a path
is the same as the weight and the midpoint of the path itself.

An undirected path does not know which of its ends is its source and
which is its target and it can be represented as in
Definition 6.33. Let ↔ be the equivalence relation on P given by
p ↔ inv(p). Each equivalence class [p]↔ ∈ P /↔ is called undirected
path and the non-negative real number ω ([p]↔ ) = ω (p) is called weight
of [p]↔ .

Remark 6.34. The equivalence class of an empty path is the singleton
set that consists of the empty path.


equivalence
relation ↔ on P
undirected path
[p]↔
weight ω ([p]↔ ) of
[p]↔

For each path p, the set(s) of paths with the same source (or target),
less weight, and midpoints on the continuum representation of p are
named in
Definition 6.35. For each direction-preserving path p ∈ P , let
Σp = {p0 ∈ P | σ (p0 ) = σ (p), ω (p0 ) < ω (p), and mp0 ∈ im p}

set Σp

and let
Tp = {p0 ∈ P | τ (p0 ) = τ (p), ω (p0 ) < ω (p), and mp0 ∈ im p}. 
Remark 6.36. Note that Tp = inv(Σinv(p) ).

set Tp


Remark 6.37. Let p be a direction-preserving path of G. For each path
p0 ∈ Σp ∪ Tp , we have d(mp , mp0 ) = ω (p)/2 − ω (p0 )/2.

The set of undirected direction-preserving paths can be turned into
a graph by having an edge from an undirected direction-preserving

81

path to each such path that has one end in common with the path,
has less weight than the path, and has the greatest weight among the
paths with the former two properties. The edges can be weighted by
the distance of the midpoints of the undirected paths. The graph and
its edge-weighting are introduced in
Definition 6.38. Let VT = P /↔, let
ET = {([p]↔ , [p0 ]↔ ) ∈ VT × VT | p0 ∈ arg max ω (p00 )},
p00 ∈Σp ∪Tp

and let
ωT : ET → R≥0 ,

([p]↔ , [p0 ]↔ ) 7→ d(mp , mp0 ).
edge-weighted
directed acyclic
graph GT

The triple GT = (VT , ET , ωT ) is an edge-weighted directed acyclic graph.


Remark 6.39. For each maximum-weight direction-preserving path p̂
in G, the in-degree of [p̂]↔ in GT is 0, because there are only edges to
equivalence classes of less-weight paths.

Remark 6.40. For each edge ([p]↔ , [p0 ]↔ ) of GT , we have ωT ([p]↔ ,
[p0 ]↔ ) = ω (p)/2 − ω (p0 )/2.

Remark 6.41. There is a bijection between the vertices of VT and
the set of all midpoint signals that are created by the signal machine
S. The reason is that each midpoint signal memorises two words of
directions in a set, one that leads from its position to one end of the
path it designates the midpoint of and the other to the other end;
because these words are stored in a set, the midpoint signal does not
differentiate between source and target of its path.
Each maximum-weight vertex of GT is a maximum-weight undirected
direction-preserving path in G and is, under suitable identifications
and definitions, a longest undirected direction-preserving path in the
continuum representation M of G. And, each minimum-weight vertex
of GT is one of weight 0, is an undirected empty path in G, and is, under
suitable identifications, an empty path in G and in M , and a vertex in
G and in M .
For each path pT in GT that starts in a maximum-weight vertex and
ends in a minimum-weight vertex, in the time evolution of the signal
machine S, there is a thaw signal that traverses the midpoint signals
represented by the vertices on the path in the order they occur on the
path such that the time the thaw signal takes to get from the vertex vT
on the path to the next vertex vT0 on the path is precisely the weight of
the edge (vT , vT0 ), in particular, the time the thaw signal takes to reach
the end of its path is the weight of pT .

82

To show that the synchronisation of all edges is thawed and finishes
at the same time, we have to show that, for each edge, there is a thaw
signal that collides with the midpoint signal of the edge and reaches the
end of its path at one end of the edge, and that all thaw signals reach
the ends of their paths at the same time. The former is equivalent to
showing that, for each edge e ∈ E with the two ends v0 and v1 , there is
a maximum-weight direction-preserving path p in G such that there is
a path in GT from [p]↔ to [(v0 , e, v1 )]↔ . And the latter is equivalent to
showing that the weights of all paths from maximum-weight vertices
to minimum-weight vertices in GT are the same. See corollary 6.46.
For each non-empty direction-preserving path p in G, the midpoint of
p is found at time max{d(g, σ (p)), d(g, τ (p))} + ω (p)/2 (see lemma 6.4)
and, for each maximum-weight direction-preserving path p̂ in G, the
midpoint of p̂ is found at time r + d/2 (see lemma 6.6). If the thaw
signals that emanate from the midpoints of maximum-weight directionpreserving paths at the time r + d/2 reach the ends of their paths after
the time span d/2, then synchronisation finishes at the optimal time
r + d. The condition is equivalent to showing that the weights of all
paths from maximum-weight vertices to minimum-weight vertices in GT
are equal to d/2. See corollary 6.46.

The thaw signals that spread from the midpoint signal of a path p
eventually collide with the midpoint signals of all paths that have the
same source or target as p, less weight, and whose midpoints lie on p.
This is what is essentially shown in
Lemma 6.42. Let p be a path in G and let p0 ∈ Σp ∪ Tp . There is a path
from [p]↔ to [p0 ]↔ in GT .

Proof. case 1: p0 ∈ Σp . If p0 ∈ arg maxp00 ∈Σp ω (p00 ), then ([p]↔ ,
[p0 ]↔ ) ∈ ET and the path consisting of this edge is one from [p]↔
to [p0 ]↔ . Otherwise, there is a q ∈ arg maxp00 ∈Σp ω (p00 ) such that
ω (p0 ) < ω (q ). Then, ([p]↔ , [q ]↔ ) ∈ ET . And, because {p0 , q} ⊆
Σp , we have σ (p0 ) = σ (p) = σ (q ). Thus, because q (ω (q )/2) =
mq ∈ im p, the paths q and p are direction-preserving, and the
multigraph G is a tree, we have q [0,ω (q )/2] = p[0,ω (q )/2] and,
analogously, we have p0 [0,ω (p0 )/2] = p[0,ω (p0 )/2] . Hence, because
ω ( p0 ) < ω ( q ) ,
mp0 = p0 (ω (p0 )/2) = p(ω (p0 )/2) = q (ω (p0 )/2) ∈ im q.
Therefore, p0 ∈ Σq . Now, if p0 ∈ arg maxp00 ∈Σq ω (p00 ), then ([q ]↔ ,
[p0 ]↔ ) ∈ ET , and the path consisting of the edges ([p]↔ , [q ]↔ ) and
([q ]↔ , [p0 ]↔ ) is a path from [p]↔ to [p0 ]↔ . Otherwise, because VT
is finite and ω (q ) > ω (p0 ), it follows by induction that there is a
path from [q ]↔ to [p0 ]↔ and therefore one from [p]↔ to [p0 ]↔ .

83

case 2: p0 ∈ Tp . Then, inv(p0 ) ∈ Σinv(p) . Hence, according to the
first case, there is a path from [inv(p)]↔ to [inv(p0 )]↔ . Therefore,
because [p]↔ = [inv(p)]↔ and [p0 ]↔ = [inv(p0 )]↔ , there is a path
from [p]↔ to [p0 ]↔ .

Each midpoint signal of a path eventually collides with a matching thaw signal that originated at the midpoint of a maximum-weight
direction-preserving path. This is what is essentially shown in
Lemma 6.43. Let p be a direction-preserving path in G. There is a
maximum-weight direction-preserving path p̂ in G such that there is a
path from [p̂]↔ to [p]↔ in GT .

Proof. If p is a maximum-weight path, then the path p̂ = p in G
and the empty path ([p]↔ ) in GT have the desired properties. From
now on, let p not be a maximum-weight path. Furthermore, let p̂ be
a maximum-weight path in G and let pd be the minimum-weight path
in G such that σ (pd ) lies on p and τ (pd ) lies on p̂. Then, there are
paths p1 and p2 in G such that p1 • p2 = p and τ (p1 ) = σ (pd ) as well
as τ (inv(p2 )) = σ (pd ). And, there are paths p̂1 and p̂2 in G such that
p̂1 • p̂2 = p̂ and τ (pd ) = σ (p̂2 ) as well as τ (pd ) = σ (inv(p̂1 )). Let
(

q1 =

p1 ,

if ω (p1 ) ≥ ω (p2 ),

inv(p2 ), otherwise,

let
(

q2 =

p2 ,

if ω (p1 ) ≥ ω (p2 ),

inv(p1 ), otherwise,

and let q = q1 • q2 . Furthermore, let
(

q̂1 =

p̂1 ,

if ω (p̂2 ) ≥ ω (p̂1 ),

inv(p̂2 ), otherwise,

let
(

q̂2 =

p̂2 ,

if ω (p̂2 ) ≥ ω (p̂1 ),

inv(p̂1 ), otherwise,

and let q̂ = q̂1 • q̂2 . Moreover, let p0 = q1 • pd • q̂2 . Then, q ∈ {p, inv(p)}
as well as q̂ ∈ {p̂, inv(p̂)}. And, ω (q1 ) ≥ ω (q2 ) as well as ω (q̂1 ) ≤ ω (q̂2 ).
And, τ (p0 ) = τ (q̂ ) as well as σ (q ) = σ (p0 ). And, because ω (q1 ) ≥ ω (q2 ),
we have mq ∈ im q1 ⊆ im p0 .
case 1: p0 is a maximum-weight path. Then, because p is not a maximumweight path, we have ω (q ) = ω (p) < ω (p0 ). Hence, because
σ (q ) = σ (p0 ) and mq ∈ im p0 , we have q ∈ Σp0 . In conclusion, according to lemma 6.42, there is a path from [p0 ]↔ to [p]↔ = [q ]↔ .

84

case 2: p0 is not a maximum-weight path. Then, ω (q1 • pd • q̂2 ) =
ω (p0 ) < ω (q̂ ) = ω (q̂1 • q̂2 ) and thus ω (q1 • pd ) < ω (q̂1 ), in particular, ω (q1 ) < ω (q̂1 ). Hence, because ω (q2 ) ≤ ω (q1 ) < ω (q̂1 ) ≤
ω (q̂2 ), we have ω (q ) = ω (q1 ) + ω (q2 ) < ω (q1 ) + ω (q̂2 ) ≤ ω (p0 ).
And, because ω (q1 • qd ) < ω (q̂1 ) ≤ ω (q̂2 ), we have mp0 ∈ im q̂2 ⊆
im q̂. And, recall that mq ∈ im p0 . Altogether, because τ (p0 ) =
τ (q̂ ) and σ (q ) = σ (p0 ), we have p0 ∈ Tq̂ and q ∈ Σp0 . Therefore,
according to lemma 6.42, there is a path from [p̂]↔ = [q̂ ]↔ to
[p0 ]↔ and there is a path from [p0 ]↔ to [q ]↔ = [p]↔ . In conclusion, there is a path from [p̂]↔ to [p]↔ .

The time it takes a thaw signal from the midpoint of a path to
collide with the midpoint signal of a matching path is given by half the
former path’s length minus half the latter path’s length. This is what
is essentially shown in
Lemma 6.44. For each path pT in GT , the weight of pT is equal to
ω (σ (pT ))/2 − ω (τ (pT ))/2.

Proof. We prove the statement by induction.
Base Case. Each empty path pT in GT has weight 0, has the same
source and target vertices, and ω (σ (pT ))/2 − ω (τ (pT ))/2 is equal to 0
as needed.
Inductive Step. Let pT = ([p0 ]↔ , [p1 ]↔ , . . . , [pn ]↔ ) be a non-empty path
in GT such that the weight of the subpath ([p1 ]↔ , . . . , [pn ]↔ ) is equal
to ω ([p1 ]↔ )/2 − ω ([pn ]↔ )/2. Then, according to remark 6.40, we have
ωT ([p0 ]↔ , [p1 ]↔ ) = d(mp0 , mp1 ) = ω (p0 )/2 − ω (p1 )/2 = ω ([p0 ]↔ )/2 −
ω ([p1 ]↔ )/2. Hence, the weight of the path pT is equal to ω ([p0 ]↔ )/2 −
ω ([p1 ]↔ )/2 + ω ([p1 ]↔ )/2 − ω ([pn ]↔ )/2 = ω ([p0 ]↔ )/2 − ω ([pn ]↔ )/2.


The time it takes a thaw signal from a maximum-weight directionpreserving path to collide with the midpoint signal of a matching path
is essentially given in
Corollary 6.45. For each maximum-weight direction-preserving path
p̂ in G such that there is a path from [p̂]↔ to [p]↔ in GT , the weight of
this path is d/2 − ω (p)/2.

Proof. This is a direct consequence of lemma 6.44 with the fact that
ω (p̂) = d.

The time it takes a thaw signal from a maximum-weight directionpreserving path to collide with the midpoint signal of an edge it thaws
and to reach the ends of the edge is essentially given in

85

Corollary 6.46. Let e be an edge of G, and let v0 and v1 be the two
ends of e. There is a maximum-weight direction-preserving path p̂ such
that there is a path from [p̂]↔ to [(v0 , e, v1 )]↔ and all such paths have
weight d/2 − ω (e)/2, and there are also paths from [p̂]↔ to [(v0 )]↔ and
to [(v1 )]↔ and all such paths have weight d/2.

Proof. This is a direct consequence of lemma 6.43 and corollary 6.45.


references
[Bal67]

Robert Balzer. ‘An 8-state minimal time solution to the
firing squad synchronization problem’. In: Information and
Control 10.1 (1967), pages 22–42 (cited on page 2).

[CD91]

Karel Culik II and Simant Dube. ‘An efficient solution of
the firing mob problem’. In: Theoretical Computer Science
91.1 (1991), pages 57–69 (cited on page 2).

[Dur05]

Jérôme Olivier Durand-Lose. ‘Abstract Geometrical Computation: Turing-Computing Ability and Undecidability’. In:
Lecture Notes in Computer Science 3526 (2005), pages 106–
116 (cited on page 3).

[Dur08]

Jérôme Olivier Durand-Lose. ‘The signal point of view: from
cellular automata to signal machines’. In: Proceedings of
the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008), Uzès, France, April 21-25,
2008. Edited by Bruno Durand. MCCME Publishing House,
Moscow, 2008, pages 238–249 (cited on page 29).

[Ger87]

Hein D. Gerken. ‘Über Synchronisationsprobleme bei Zellularautomaten’. German. Diplomarbeit. Braunschweig: Technische Universität Baunschweig, 1987 (cited on page 2).

[Got62]

Eiichi Goto. ‘A minimal time solution of the firing squad
problem’. In: Dittoed course notes for Applied Mathematics. Harvard University 298 (1962), pages 52–59 (cited on
page 2).

[Gre83]

John J. Grefenstette. ‘Network Structure and the Firing
Squad Synchronization problem’. In: Computer and System
Sciences 26.1 (1983), pages 139–152 (cited on pages 2, 3).

[Kob77]

Kojiro Kobayashi. ‘The firing squad synchronization problem for two-dimensional arrays’. In: Information and Control 34.3 (1977), pages 177–197 (cited on page 2).

86

[Kob78a]

Kojiro Kobayashi. ‘On the minimal firing time of the firing
squad synchronization problem for polyautomata networks’.
In: Theoretical Computer Science 7.2 (1978), pages 149–167
(cited on page 2).

[Kob78b]

Kojiro Kobayashi. ‘The firing squad synchronization problem for a class of polyautomata networks’. In: Computer
and System Sciences 17.3 (1978), pages 300–318 (cited on
page 2).

[Maz87]

Jacques Mazoyer. ‘A Six-state Minimal Time Solution to
the Firing Squad Synchronization Problem’. In: Theoretical Computer Science 50.2 (1987), pages 183–238 (cited
on pages 2, 3, 60).

[Moo64]

Edward Forrest Moore. Sequential machines. Selected papers. Computer Science and Information Processing. AddisonWesley, 1964, pages 213–214 (cited on page 1).

[RFH72]

P. Rosenstiehl, J. R. Fiksel and A. Holliger. ‘Intelligent
graphs. Networks of finite automata capable of solving graph
problems’. In: Graph Theory and Computing. Edited by
Ronald C. Read. Academic Press, 1972, pages 219–265 (cited
on page 2).

[Rók00]

Zsuzsanna Róka. ‘The firing squad synchronization problem
on Cayley graphs’. In: Theoretical Computer Science 244.1
(2000), pages 243–256 (cited on page 2).

[Rom76]

Francesco Romani. ‘Cellular automata synchronization’. In:
Information Sciences 10.2 (1976), pages 299–318 (cited on
page 2).

[San94]

Peter Sanders. ‘Massively Parallel Search for TransitionTables of Polyautomata’. In: Parcella ’94. Proceedings of
the Vi. International Workshop on Parallel Processing by
Cellular Automata and Arrays. Volume 81. Mathematical
Research. Potsdam, Germany: Akademie, 1994, pages 99–
108 (cited on page 2).

[UYY09]

Hiroshi Umeo, Jean-Baptiste Yunes and Takuya Yamawaki.
‘A Simple Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays’. In: CSSim
’09. Proceedings of the First International Conference on
Computational Intelligence, Modelling and Simulation. Brno,
TBD, Czech Republic: IEEE, 2009, pages 120–125 (cited
on page 2).

[Wac16]

Simon Wacker. ‘Cellular Automata on Group Sets and the
Uniform Curtis-Hedlund-Lyndon Theorem’. In: Cellular Automata and Discrete Complex Systems. Proceedings of the
22nd IFIP WG 1.5 International Workshop, AUTOMATA

87

2016. Edited by Matthew Cook and Turlough Neary. Lecture Notes in Computer Science. Zürich, Switzerland: Springer
International Publishing, 2016, pages 185–198 (cited on
page 4).
[Wac17]

Simon Wacker. Right Amenability And Growth Of Finitely
Right Generated Left Group Sets. 2017. arXiv: 1701.02108
[]. Unpublished (cited on page 4).

[Wak66]

Abraham Waksman. ‘An optimum solution to the firing
squad synchronization problem’. In: Information and Control 9.1 (1966), pages 66–78 (cited on page 2).

88

