# A Trainable Sequence Learner that Learns and Recognizes Two-Input Sequence
Patterns
††thanks: This report was produced in collaboration with the Institute of
Neuroinformatics (University of Zurich and ETH Zurich)

Jan Hohenheim  University of Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>Tommaso Stecconi  IBM Research GmbH
Zurich Research Laboratory
Work carried out at University of Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>Zhaoyu Devon Liu  CUHK BME
Chinese University of Hong Kong
Hong Kong, China
<EMAIL_ADDRESS>Pietro Palopoli  D-ITET
ETH Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

We present two designs for an analog circuit that can learn to detect a
temporal sequence of two inputs. The training phase is done by feeding the
circuit with the desired sequence and, after the training is completed, each
time the trained sequence is encountered again the circuit will emit a signal
of correct recognition. Sequences are in the order of tens of nanoseconds. The
first design can reset the trained sequence on runtime but assumes very strict
timing of the inputs. The second design can only be trained once but is
lenient in the input’s timing.

###### Index Terms:

sequence, learning, analog, design, circuit, coincidence detector

##  I Introduction

Sequence pattern recognition is both central to how our brain works and
important for many modern AI applications such as speech recognition, speaker
identification, automatic medical diagnosis or general classification. Since
the human brain performs pattern learning and recognition with extreme energy
efficiency, parallelism, and relatively good speed, the need to replicate
these advantages in silica becomes apparent.

Some similar works already exist. Liu et al.[1] designed a multi-terminal
transistor that can behave as a sequence detector by tuning the time delay
between pulses fed into the transistor terminals. However, this system cannot
train itself using certain input sequences like our brain.

As a starting point, we present an idea of how a simple sequence pattern
learning and recognition chip could look like and provide two possible
implementation schematics.

##  II Learning Algorithm

Inputs are expected to be pulses coming from two different sources that arrive
in some regular interval, determined by the design used. We will call them
_Signal A_ (or just A) and _Signal B_ (or just B). They are instantly delayed
by the same default amount of time. The goal is to make them overlap in time
(learning phase) so that later the correct recognition can occur. This is done
by treating A as a _reference_ and shifting B’s delay up or down to make it
coincide with A inside the circuit.

Figure 1: Overview of the shared logic behind the circuits

To do so, It is necessary to analyze the extent of the delay between the
inputs, which is done by using a _coincidence detector_ inspired by the
Jeffress model of sound localization [2]. This model works by letting the
inputs move through a series of delaying nodes from opposite sides. They will
meet at a node determined by their temporal offset. If they meet in the middle
it means that they came in simultaneously. Since our inputs are assumed to
always come with some offset, a meeting in the middle must mean that we
successfully tweaked B’s delay so that the training is finished.

Before this is the case, the inputs will meet at another node, indicating how
off from our goal we are. E.g. if we wish to detect the sequence “AB”, B will
come in after A, so the signals will meet on one of the nodes on the right in
figure 1. meaning that we must aim to _decrease_ B’s delay. This task is
carried out by a _delay adjustment unit_ specific to the design in question.
In any case, the delay modified is a row of 8 _tunable delay_[3] units. Their
delay is inversely proportional to a shared bias voltage.

##  III Sequence Learner Designs

###  III-A Design A

Figure 2: A simplified view of the circuit’s schematic. For clarity’s sake,
only the connections coming from the coincidence detector nodes in the middle
and one to the right of the middle are included. In the full view, all nodes
have equivalent connections

####  III-A1 Usage

Main inputs

$V_{\rm{in1}}$ and $V_{\rm{in2}}$

Auxiliary inputs

$V_{\rm{reset}}$ to reset the learned sequence

Constant inputs

$V_{\rm{delay}}$ at 1.18 V

Main outputs

$V_{\rm{out}}$ for the detection

Auxiliary outputs

$V_{\rm{training}}$ to tell a user that we are currently in training mode

Pulse length

10 - 12 ns

Pulse delay

either 10 - 11 ns (so right after each other) or 20 - 21 ns

Pattern delay

at least 15 ns

Pattern delay is defined as the amount of time that needs to pass after a
sequence finished until another one can be detected.

####  III-A2 Working principles

The first version of the sequence learner uses the common design elements
introduced above and SR latches as delay adjustment units (figure 2).

Two pulses with a default delay are fed into two tunable delay lines. The
signals are labeled as a reference signal and a trained signal, where the
reference signal has a constant delay (figure 4) while the trained signal will
have its delay shifted (figure 3).

Figure 3: A trained tunable delay unit. For simplicity, only the connections
from the first subunit are included. If this SR latch is the only one active,
the delay was successfully reduced. Figure 4: The constant delay for the
reference signal takes the input after it went through three tunable delay
subunits.

In this design, the tunable delay line has a constant bias of 1.18 V, which
makes every subelement have a delay of 5 ns, where one subelement consists of
two tunable delay units. The delay shifting is not done by changing this bias
(see the design B for that), but by reading the signal at different points
along the delay line. This is done by ANDing the signals with SR latches
(figure 3). Only one of them is on at any time, ensuring that only one delay
is selected. The outputs of all ANDs are ORd together to get the active
signal. The reference signal instead gets its constant delay by always picking
up the signal after the third subunit (figure 4).

The latches determining the delay for the train signal get set by the
coincidence detector. Its output is a NAND between every pair of nodes, so an
output of 0 means that a coincidence was found111An earlier design kept the
analog nature of the coincidence detector by using a bump-antibump [4] instead
of NANDs. This led to multiple coincidences being detected at the same time,
which we tried to remedy using a hysteretic winner-takes-all [5]. All of this
ended up producing roughly the same results as just using digital NANDs, so we
use them now instead.. If this did not happen in the middle, the training is
either not finished or it is finished and we didn’t find the right sequence.
To differentiate between these, there is an SR latch controlling whether or
not we are in _training_ or in _active_ mode via its output $V_{\rm{active}}$.
Its inverse is $V_{\rm{training}}$ and it can be reset via $V_{\rm{reset}}$.
It is set when we detect the first coincidence in the middle of the detector.

To ensure we are only updating the trained delay while actually training, we
NOR the output of the coincidence detector with $V_{\rm{active}}$ (figure 5).
This output then is only $V_{\rm{dd}}$ when both $V_{\rm{active}}$ and the
coincidence detector’s output are 0. This output will both set the SR latch
that allows reading the correct delay and reset all other latches.

Figure 5: The diagram of the coincidence detector fed with delayed Train-
Signal and Reference-Signal. The ellipsis in the diagram indicates the same
way of connection as between point 1 and point 3.

###  III-B Design B

####  III-B1 Usage

Main inputs

$V_{\rm{in1}}$ , $V_{\rm{in2}}$

Constant inputs

$V_{\rm{default\ delay}}$ and $V_{\rm{clock}}$ (values described later)

Main outputs

$V_{\rm{out}}$ for the detection

Pulse length

10 - 15 ns

Pulse delay

10 - 50 ns

Pattern delay

at least 15 ns

####  III-B2 Working principles

The second version of the sequence learner extends this functionality to
flexible delays ranging between +- 50 ns (A with respect to B). Moreover, it
internally provides the analog voltages required to tune the delays of the
tunable delay element. To extend the range of detectable delays we modified
the coincidence detector block by including a pair of transmission gates
working in antiphase between each stage of the coincidence detector (see
figure 6).

Figure 6: The second version of the coincidence detector includes a sample and
hold system made of two transmission gates in series working in antiphase.

The transmission gates are controlled by a clock signal of period 10 ns,
introducing a hold time >5 ns. This solution improves the robustness of the
coincidence detection and allows to work with ranges of delays rather than
fixed ones.

The output of the coincidence detector can either activate a default delay of
60 ns, in case A and B are overlapped or 40 ns or 20 ns. In the latter two
cases, a delay control logic is activated to disconnect the default input
voltage of the tunable delay element of $\approx$ 700 mV. The delay of 40 ns
is given by an input voltage of $\approx$ 950 mV, which can be provided by an
NMOS in transdiode configuration, mirroring its gate voltage, as shown in
figure 7.

Figure 7: The schematic for the circuit that converts the 20 ns delay output
of the coincidence detector into the corresponding analog voltage driving the
tunable delay element.

This solution can be used to set even longer delays; however, $\sim$ 700 mV
correspond to a 60 ns delay and is already the threshold voltage for strong
inversion regime. Therefore, for longer delays the input N-FET of the tunable
delay must be biased in weak inversion, making the system highly sensitive to
PVT and mismatches.

We tested multiple sequence learning transient simulations, to evaluate the
correct functionality of the circuit. The system can adjust the correct delay
of 20 ns, for the range of delay 12 $\div$ 30 ns, and 40 ns for the range 32
$\div$ 50 ns, making the signals A and B overlap following the initial
training. Only the specific minor ranges of 10 $\div$ 12 ns and 30 $\div$ 32
ns don’t succeed, due to the signal distortion occurring in the tunable delay
element (a 10 ns long input pulse gets distorted into an 8 ns long delayed
output).
In figure 8 we show the transient simulation for a delay of B of 45 ns.

Figure 8: Transient simulation of the sequence learner, when B is delayed by
45 ns.

The other two main units implemented in this configuration include logic for
feeding the tunable delay with 1.8 V (as shown in figure 9) and logic to
deactivate the default voltage value in input to the tunable delay (which in
our case is $\approx$ 700 mV) - shown in figure 9. It is important to note
that the latter circuit has two branches. The main branch connects directly to
the tunable delay and provides 1.8 V . The second branch is used to deactivate
the detection of 20 ns delay. This solution has been adopted because when a 40
ns delay detection occurs, an additional undesired 20 ns delay detection
appears which must be suppressed.

Figure 9: Circuit schematics converting the 40 ns delay output of the
coincidence detector into the corresponding 1.8 V driving the tunable delay
element.

Figure 10: Circuit schematics used to deactivate the pre-training default
voltage in input to the tunable delay.

Figure 11: Single unit of tunable delay obtained from [2]. 8 of these units in
series build the tunable delay used in the sequence learner implementation.

##  IV Figures of Merit

###  IV-A Design A

Power consumption

static: negligible, dynamic: $241\ \mu W$

Operations

$1.3\times 10^{7}\ s^{-1}$

Area

$2.1\times 1.2\ mm$

An operation is defined as either training a sequence, detecting a sequence or
resetting the circuit. The reported operations assume that it is impractical
to let the inputs and outputs overlap. Since the output always comes with a
fixed delay of 65 ns after the last input, a careful setup can feed as many
inputs to the circuit as possible and let the inputs and outputs overlap,
resulting in about 2.5 times more operations ($3.1\times 10^{7}\ s^{-1}$).

The layout area was not prioritized at all and can massively be optimized
without changing the circuit design.

###  IV-B Design B

Power consumption

static: $55\ \mu W$, dynamic: $100\ \mu W$

Operations

$1.1\times 10^{7}\ s^{-1}$

Area

Not layouted

##  V Applications and Modifications

As is, the circuit can essentially just process a single bit: The incoming
sequence is either AB or BA. The presented implementation can however be
extended easily to support recognizing different delays between the signals.

This way, it could be used as a trainable directional detector for binaural
auditory systems working in extremely high frequencies, e.g. learning that a
mobile sound emitter is slightly to the left of the recording device and then
detecting whenever the sound emitter returns to that location. The first
design assumes pulse lengths and delays of just 10-20 ns. We can imagine this
being of use for industrial robots that need to detect the position of other
fast-moving machinery.

By altering the system a bit, one could in principle extend the operating
range to support signals in the millisecond range, which would make it
compatible with signals seen in biology. This comes closer to the original
usage of the Jeffres model embedded within the circuits. This way, a circuit
might be trained to detect each time a studied animal population visits a
certain spot in conditions where a camera setup is not feasible, e.g. small
mice in tall grass.

Another possible usage is to keep the circuit as a binary recognition machine
that converts a signal coming from two sources into a single binary output. A
sequence learner trained on “AB” would then convert the sequence “ABABBAAB” to
“1101”. In this interpretation, we reach a rate of 10 Mbit s-1. It is however
not clear when such a thing would be useful.

The input range can also be extended to include any number of signals by
adding nodes “perpendicular” to the coincidence detector. This could be used
as a generic pattern detector. For example, every input could represent an
individual letter and the sequence learner could recognize entire words.

Furthermore, detecting signals with a time-scale of nano-seconds is essential
in some fields. R.Kamrla et. al[6] introduced the concept of ’delayed
coincidence’ and used ’delayed coincidence circuit’ to distinguish between
single photon spectra and pair electrons excited by a single photon. Anita et
al.[7] introduced an anti-coincidence circuit with a refractory period to
reduce the noise when detecting gamma-rays released by boron neutron. By
implementing our circuit, it is possible to achieve the functions above.

## Acknowledgment

Our thanks to Prof. Shih-Chii Liu for her guidance and help during the long
brainstorming sessions that went into the design of these circuits; Prof. Tobi
for his advice and suggestions along the way; and the teaching assistants,
classmates for their patient help and companionship in the course Neuromorphic
Engineering by Institute of Neuroinformatics.

All four authors contributed equally to this paper.

## References

  * [1] R. Liu, Y. He, S. Jiang, L. Wang, and Q. Wan, “Synaptic plasticity modulation and coincidence detection emulated in multi-terminal neuromorphic transistors,” Organic Electronics, vol. 92, p. 106125, 2021.
  * [2] L. A. Jeffress, “A place theory of sound localization,” J. Comp. Physiol. Psychol., vol. 41, pp. 35–39, Feb. 1948.
  * [3] I. Lee, D. Sylvester, and D. Blaauw, “A Constant Energy-Per-Cycle Ring Oscillator Over a Wide Frequency Range for Wireless Sensor Nodes,” IEEE J. Solid-State Circuits, vol. 51, pp. 697–711, Feb. 2016.
  * [4] T. Delbruck, “’Bump’ circuits for computing similarity and dissimilarity of analog voltages,” in IJCNN-91-Seattle International Joint Conference on Neural Networks, vol. i, pp. 475–479vol.1, IEEE, July 1991.
  * [5] G. Indiveri, “A Current-Mode Hysteretic Winner-take-all Network, with Excitatory and Inhibitory Coupling,” Analog Integr. Circuits Signal Process., vol. 28, pp. 279–291, Sept. 2001.
  * [6] R. Kamrla, W. Widdra, C.-T. Chiang, and F. Schumann, “Electron pair emission from surfaces: Some general experimental considerations,” Journal of Electron Spectroscopy and Related Phenomena, vol. 257, p. 147185, 2022.
  * [7] A. Caracciolo, L. Buonanno, D. Di Vita, I. D’Adda, A. Chacon, M. Kielly, M. Carminati, M. Safavi-Naeini, and C. Fiorini, “Benedicte (boron neutron capture): a versatile gamma-ray detection module for boron neutron capture therapy,” IEEE Transactions on Radiation and Plasma Medical Sciences, pp. 1–1, 2022.


A Cartesian graph-decomposition theorem based on a vertex-removing synchronised graph product

label2]Antoon H. Boode

[label2]Robotics Research Group,
InHolland University of Applied Science
The Netherlands

Recently, we have introduced and modified two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes.
This vertex-removing synchronised product (VRSP), is based on modifications of the well-known Cartesian product and is closely related to the synchronised product due to Wöhrle and Thomas.
Here, we introduce a new graph-decomposition theorem based on the VRSP that provides a Cartesian decomposition of graphs.

Vertex-Removing Synchronised Graph Product
Product Graph
Graph Decomposition
Synchronising Processes

Mathematics Subject Classification : 05C76, 05C51, 05C20, 94C15

§ INTRODUCTION

Recently, we have introduced [7] and modified [4] two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes, in particular in the field of robotics.
More on the background, definitions and applications can be found in two conference contributions [6, 8], three journal papers [4, 7, 9], on ArXiv [3] and the thesis of the author [5].
We repeat some of the background, definitions and theorems here for convenience, and present the decomposition theorem that we state and prove in Section <ref>.

The decomposition of graphs is well known in the literature.
For example, a decomposition can be based on the partition of a graph into edge disjoint subgraphs.
In our case, the decomposition is based on the contraction of a subset of the vertices of the graph, in such a manner that if $V'\subset V(G)$ is contracted giving $G'$ and $V''\subset V(G)$ is contracted giving $G''$ we have that the vertex-removing synchronised product (VRSP) of $G'$ and $G''$ is isomorphic to $G$.
In this contribution, we have a series of contractions of $G$ where each contraction replaces a set of vertices by one vertex (and the deletion of the arcs with both ends in the contracted set) giving a graph $G'$ and another series of contractions where each contraction replaces a set of vertices by one vertex (and the deletion of the arcs with both ends in the contracted set) giving a graph $G''$ such that $G$ is isomorphic to the VRSP of $G'$ and $G''$.

The rest of the paper is organised as follows.
In the next two sections, we first recall the formal graph definitions (in Section <ref>).
Then, we state and prove (in Section <ref>) the decomposition theorem.

§ TERMINOLOGY AND NOTATION

In order to avoid duplication we refer the interested reader to [7] or [3] for background, definitions and more details.
Furthermore, we use the textbook of Bondy and Murty [2] for terminology and notation we have not specified here, or in [7] or in [3].
For convenience, we repeat a few definitions that are especially important for this note.

Let $G$ be an edge-labelled acyclic directed multigraph with a vertex set $V$, an arc set $A$, a set of label pairs $L$ and two mappings.
The first mapping $\mu: A\rightarrow V\times V$ is an incidence function that identifies the tail and head of each arc $a\in A$.
In particular, $\mu(a)=(u,v)$ means that the arc $a$ is directed from $u\in V$ to $v\in V$, where $tail(a)=u$ and $head(a)=v$. We also call $u$ and $v$ the ends of $a$.
The second mapping $\lambda :A\rightarrow L$ assigns a label pair $\lambda(a)=(\ell(a),t(a))$ to each arc $a\in A$, where $\ell(a)$ is a string representing the (name of an) action and $t(a)$ is the weight of the arc $a$.

Let $X$ be a nonempty proper subset of $V(G)$.
By contracting $X$ we mean replacing $X$ by a new vertex $\tilde{x}$, deleting all arcs with both ends in $X$, replacing each arc $a\in A(G)$ with $\mu(a)=(u,v)$ for $u\in X$ and $v\in V(G)\backslash X$ by an arc $c$ with $\mu(c)=(\tilde{x},v)$ and $\lambda (c)=\lambda(a)$, and replacing each arc $b\in A(G)$ with $\mu(b)=(u,v)$ for $u\in V(G)\backslash X$ and $v\in X$ by an arc $d$ with $\mu(d)=(u,\tilde{x})$ and $\lambda (d)=\lambda(b)$. We denote the resulting graph as $G/X$, and say that $G/X$ is the contraction of $G$ with respect to $X$.

Informally, the vertex-removing synchronised product (VRSP), denoted by $\boxbackslash$, starts from the well-known Cartesian product, denoted by $\Box$, and is based on a reduction of the number of arcs and vertices due to the presence of synchronising arcs, i.e., arcs with the same label. This reduction is done in two steps: in the first step synchronising pairs of arcs from $G_1$ and $G_2$ are replaced by one (diagonal) arc, giving the intermediate product denoted by $\boxtimes$; in the second step, vertices (and the arcs with that vertex as a tail) are removed one by one if they have $level > 0$ in the Cartesian product but $level=0$ in what is left of the intermediate product.

An arc $a\in A(G_i)$ with label pair $\lambda(a)$ is a synchronising arc with respect to $G_j$, if and only if there exists an arc $b\in A(G_j)$ with label pair $\lambda(b)$ such that $\lambda(a)=\lambda(b)$.
Furthermore, an arc $a$ with label pair $\lambda(a)$ of $G_i\boxtimes G_j$ or $G_i\boxbackslash G_j$ is a synchronous arc, whenever there exist a pair of arcs $a_i\in A(G_i)$ and $a_j\in A(G_j)$ with $\lambda(a)=\lambda(a_i)=\lambda(a_j)$.
Analogously, an arc $a$ with label pair $\lambda(a)$ of $G_i\boxtimes G_j$ or $G_i\boxbackslash G_j$ is an asynchronous arc, whenever $\lambda(a)\notin L_i$ or $\lambda(a)\notin L_j$.

But, for this contribution, we consider the Cartesian part of the VRSP only.
This is due to the fact that the decomposed graphs do not contain synchronising arcs with respect to each other and therefore the VRSP is an analogue of the Cartesian product.

§ THE CARTESIAN GRAPH-DECOMPOSITION THEOREM.

We assume that the graphs we want to decompose are connected; if not, we can apply our decomposition results to the components separately.
We continue with an analogue of a result by Sabidussi, where it is stated that every connected graph of finite type has a unique prime factor decomposition with respect to Cartesian multiplication [11].
In our case, we have a special case of Sabidussi's connected graph, because our graphs are directed, acyclic and have labelled arcs.
For the Cartesian multiplication, it is sufficient if the graphs used for the multiplication do not share a label.

In Figure <ref>, we give a simple example of this decomposition.
On the left of Figure <ref>, we have the graph $G$ consisting of subgraphs $G'_1,\ldots, G'_3,G''_1,\ldots,G''_4$.
The vertex set of $G'_i$ is replaced by $\tilde{y}_i$ giving the graph  $G/V(G'_1)/\ldots/V(G'_3)$ (shown in the middle of Figure <ref>) and the vertex set of $G''_j$ is replaced by $\tilde{x}_j$ giving the graph  $G/V(G''_1)/\ldots/V(G''_4)$ (shown at the upper left of Figure <ref>).
The VRSP of $G/V(G'_1)/\ldots/V(G'_3)$ and $G/V(G''_1)/\ldots/V(G''_4)$ then gives the graph on the left of Figure <ref>, $G\cong G/V(G'_1)/\ldots/V(G'_3)\boxbackslash G/V(G''_1)/\ldots/V(G''_4)$.
Because there are no synchronising arcs in $G/V(G'_1)/\ldots/V(G'_3)$ with respect to $G/V(G''_1)/\ldots/V(G''_4)$, we have that the Cartesian product, the intermediate stage and the VRSP of these graphs are the same. Therefore, $G\cong G/V(G'_1)/\ldots/V(G'_3)\Box G/V(G''_1)/\ldots/V(G''_4)= G/V(G'_1)/\ldots/V(G'_3)\boxtimes$ $G/V(G''_1)/\ldots/V(G''_4)= G/V(G'_1)/\ldots/V(G'_3)\boxbackslash G/V(G''_1)/\ldots/V(G''_4)$.

[-Stealth[length=5mm, width=4mm],auto,node distance=2.5cm,
main node/.style=circle,fill=blue!10,draw, font=]
VertexStyle/.append style=
font=, shape = circle,inner sep = 2pt, outer sep = 0pt,minimum size = 20 pt,draw

LabelStyle/.append style=font =
at (+0.5+,3++3+) $G$;

at (+4.5+,+5.4+) $G'_1$;
at (+1.5+,+4.4+) $G''_1$;
at (+4.5+,+2.6+) $G'_2$;
at (+5.5+,+4.4+) $G''_2$;
at (+4.5+,-0.4+) $G'_3$;
at (+9.5+,+4.4+) $G''_3$;
at (+13.5+,+4.4+)$G''_4$;
at (+5.5+4,-1-2) $G/V(G''_1)/V(G''_2)/V(G''_3)/V(G''_4)$;
at (+0.5+1,-5-1) $G/V(G'_1)/V(G'_2)/V(G'_3)$;
at (+7.5+2.5,-3-2-1) $G/V(G'_1)/V(G'_2)/V(G'_3)\boxbackslash G/V(G''_1)/V(G''_2)/V(G''_3)/V(G''_4)$;
[x=+1.5, y=+0.0,L=u_1]u_2
[x=+1.5, y=-3.0,L=u_2]u_3
[x=+1.5, y=-6.0,L=u_3]u_4
[x=+5.5, y=+0.0,L=u_4]u_5
[x=+5.5, y=-3,L=u_5]u_6
[x=+5.5, y=-6,L=u_6]u_7
[x=+9.5, y=+0.0,L=u_7]u_8
[x=+9.5, y=-3.0,L=u_8]u_9
[x=+9.5, y=-6.0,L=u_9]u_10
[x=+13.5, y=+0,L=u_10]u_11
[x=+13.5, y=-3,L=u_11]u_12
[x=+13.5, y=-6,L=u_12]u_13

[label = a](u_2)(u_3)
[label = a](u_3)(u_4)
[label = a](u_5)(u_6)
[label = a](u_6)(u_7)
[label = a](u_8)(u_9)
[label = a](u_9)(u_10)
[label = a](u_11)(u_12)
[label = a](u_12)(u_13)
[label = b](u_2)(u_5)
[label = b](u_5)(u_8)
[label = c](u_8)(u_11)
[label = b](u_3)(u_6)
[label = b](u_6)(u_9)
[label = c](u_9)(u_12)
[label = b](u_4)(u_7)
[label = b](u_7)(u_10)
[label = c](u_10)(u_13)

[x=+1, y=+0.0,L=x̃_̃1̃]s_1
[x=+4, y=+0.0,L=x̃_̃2̃]s_2
[x=+7, y=+0.0,L=x̃_̃3̃]s_3
[x=+10, y=+0.0,L=x̃_̃4̃]s_4

[label = b](s_1)(s_2)
[label = b](s_2)(s_3)
[label = c](s_3)(s_4)

[x=+0, y=-3.0,L=ỹ_1]t_1
[x=+0, y=-6.0,L=ỹ_2]t_2
[x=+0, y=-9.0,L=ỹ_3]t_3

[label = a](t_1)(t_2)
[label = a](t_2)(t_3)

VertexStyle/.append style=
font=,shape = rounded rectangle,inner sep = 0pt, outer sep = 0pt,minimum size = 20 pt,draw

[x=+3.0, y=-0.0,L=(ỹ_1,x̃_1)]t_1s_1
[x=+6.0, y=-0.0,L=(ỹ_1,x̃_2)]t_1s_2
[x=+9.0, y=-0.0,L=(ỹ_1,x̃_3)]t_1s_3
[x=+12.0, y=-0.0,L=(ỹ_1,x̃_4)]t_1s_4
[x=+3.0, y=-0.0,L=(ỹ_2,x̃_1)]t_2s_1
[x=+6.0, y=-0.0,L=(ỹ_2,x̃_2)]t_2s_2
[x=+9.0, y=-0.0,L=(ỹ_2,x̃_3)]t_2s_3
[x=+12.0, y=-0.0,L=(ỹ_2,x̃_4)]t_2s_4
[x=+3.0, y=-0.0,L=(ỹ_3,x̃_1)]t_3s_1
[x=+6.0, y=-0.0,L=(ỹ_3,x̃_2)]t_3s_2
[x=+9.0, y=-0.0,L=(ỹ_3,x̃_3)]t_3s_3
[x=+12.0, y=-0.0,L=(ỹ_3,x̃_4)]t_3s_4

[label = b](t_1s_1)(t_1s_2)
[label = b](t_1s_2)(t_1s_3)
[label = c](t_1s_3)(t_1s_4)

[label = b](t_2s_1)(t_2s_2)
[label = b](t_2s_2)(t_2s_3)
[label = c](t_2s_3)(t_2s_4)

[label = b](t_3s_1)(t_3s_2)
[label = b](t_3s_2)(t_3s_3)
[label = c](t_3s_3)(t_3s_4)

[label = a](t_1s_1)(t_2s_1)
[label = a](t_1s_2)(t_2s_2)
[label = a](t_1s_3)(t_2s_3)
[label = a](t_1s_4)(t_2s_4)

[label = a](t_2s_1)(t_3s_1)
[label = a](t_2s_2)(t_3s_2)
[label = a](t_2s_3)(t_3s_3)
[label = a](t_2s_4)(t_3s_4)

[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-6.6) – (-0.5,-6.6) –  (-0.5,+0.0);
[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-6.6) – (-0.5,-6.6) –  (-0.5,+0.0);
[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-6.6) – (-0.5,-6.6) –  (-0.5,+0.0);
[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-6.6) – (-0.5,-6.6) –  (-0.5,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+13.0,+1.5) –(+13.0,) – (+2.8,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+13.0,+1.5) –(+13.0,) – (+2.8,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+13.0,+1.5) –(+13.0,) – (+2.8,+0.0);

Decomposition of $G$ giving $G\cong G/V(G'_1)/V(G'_2)/V(G'_3)\boxbackslash G/V(G''_1)/V(G''_2)/V(G''_3)/V(G''_4)$.

In general, we have the (repeated) contraction of a vertex set of a graph $G$ into the graphs $G'_i$, $G''_j$ such that $G'_i\boxbackslash G''_j\cong G$.
Then, the requirements for the (repeated) contraction of a vertex set of the graph $G$ are as follows: $G=\overundercup{i=1}{m}G'_i\cup \overundercup{j=1}{n}G''_j$, $G'_i\cong G'_j$, $G''_i\cong G''_j$, $G/V(G'_1)/\ldots/V(G'_m)\cong G''_i$, $G/V(G''_1)/\ldots/V(G''_n)\cong G'_i$, $V(G)=\overundercup{i=1}{m}V(G'_i)$, $V(G)=\overundercup{j=1}{n}V(G''_j)$,  $A(G)=\overundercup{j=1}{m}A(G'_i)\cup \overundercup{j=1}{n}A(G''_j)$, $L(G)=L(G'_i)\cup L(G''_j)$ and $L(G'_i)\cap L(G''_j)=\emptyset$.

This leads to theorem <ref>.
Note that the line of proof is similar to the line of proof of our contribution in [7].

Let $G$ be a graph. If $G=\overundercup{i=1}{m}G'_i\cup \overundercup{j=1}{n}G''_j$, $G'_i\cong G'_j$, $G''_i\cong G''_j$, $G/V(G'_1)/\ldots/V(G'_m)$ $\cong G''_i$, $G/V(G''_1)/\ldots/V(G''_n)\cong G'_i$, $V(G)=\overundercup{i=1}{m}V(G'_i)=\overundercup{j=1}{n}V(G''_j)$, and $L(G'_i)\cap L(G''_j)=\emptyset$.
Then $G\cong G/V(G'_1)/\ldots/V(G'_m)\boxbackslash G/V(G''_1)/\ldots/V(G''_n)$.

Let $G_1=G/V(G'_1)/\ldots/V(G'_m)$ and $G_2=G/V(G''_1)/\ldots$ $/V(G''_n)$.
It suffices to define a mapping $\phi: V(G)\rightarrow V(G_1\boxbackslash G_2)$ and to prove that $\phi$ is an isomorphism from $G$ to $G_1\boxbackslash G_2$.
Let $\tilde{x}_i$ and $\tilde{y}_j$ be the new vertices replacing the sets of vertices $V(G''_i)$ and $V(G'_j)$ when defining $G_2$ and $G_1$, respectively.
Consider the mapping $\phi:V(G)\rightarrow V(G_1\boxbackslash G_2)$ defined by $\phi(u)=(\tilde{y}_j,\tilde{x}_i)$ where $u\in G''_i\cap G'_j$.

$\phi$ is an injective map from $V(G)$ to $V(G_1\boxbackslash G_2)$.

Because $V(G)=\overundercup{i=1}{m}V(G'_i)=\overundercup{j=1}{n}V(G''_j)$, we have that for each vertex $u\in V(G)$ there exist subgraphs $G'_i$ and $G''_j$ such that $u\in G'_i\cap G''_j$.
Such a vertex $u$ is uniquely defined.
If there exist vertices $u,v\in G'_i\cap G''_j$ then because $G_1\cong G''_i$ and $G_2\cong G'_i$ we have $u=v$.
By contradiction, suppose $u\neq v$ then both $u$ and $v$ are replaced by $\tilde{x}_i$ in $G_2$ and by $\tilde{y}_j$ in $G_1$. But then, because $u,v\in G'_i$ it follows that $G_2\ncong G'_i$ and because $u,v\in G''_i$ it follows that $G_1\ncong G''_i$.
Now, the contraction of $G$ giving $G_1$ is an injective map from all $u\in G''_i$ to $\tilde{x}_i$, the contraction of $G$ giving $G_2$ is an injective map from all $u\in G'_j$ to $\tilde{y}_j$.
Then, by the definition of the Cartesian product, we have that $u$ is mapped on $(\tilde{y}_j,\tilde{x}_i)$ in $G_1\Box G_2$.
Because, all arcs $a$ of $G_1$ are not synchronizing arcs with respect to all arcs $b$ of $G_2$, there are no vertices removed from $G_1\boxtimes G_2$ and, therefore, $V(G_1\boxtimes G_2)=V(G_1\boxbackslash G_2)$.
Hence, the map $\phi$ is a injective map from $V(G)$ to $V(G_1\boxbackslash G_2)$.

$\phi$ is a surjective map from $V(G)$ to $V(G_1\boxbackslash G_2)$.

Furthermore, because $\overundercup{i=1}{m} V(G'_i)=V(G)$, we have $V(G_1)=\{\tilde{y}_1,\ldots,\tilde{y}_m\}$ and, similarly, because $\overundercup{i=1}{n} V(G''_i)=V(G)$, we have $V(G_2)=\{\tilde{x}_1,\ldots,\tilde{x}_n\}$, giving $|V(G)|=|V(G_1\Box G_2)|=m\cdot n$.
Because all arcs $a$ of $\overundercup{i=1}{m}G'_i$ are not synchronizing with respect to all arcs $b$ of $\overundercup{j=1}{n}G''_j$, due to the definition of the VRSP we have $|V(G)|=|V(G_1\Box G_2)|=|V(G_1\boxbackslash G_2)|=m\cdot n$.
Hence, we have $V(G_1\boxbackslash G_2)=\{(\tilde{y}_j,\tilde{x}_i)\mid i\in\{1,\ldots, m\},j\in \{1,\ldots, n\}$.
Therefore, there is a vertex $u\in V(G)$ for every vertex $(\tilde{y}_j,\tilde{x}_i) \in V(G_1\boxbackslash G_2)$ and the map $\phi$ is a surjective map from $V(G_1\boxbackslash G_2)$ to $V(G)$.

Due to Claim <ref> and Claim <ref>, we have that $\phi$ is a bijection from $V(G)$ to $V(G_1\boxbackslash G_2)$.
Because the vertices $(\tilde{y}_j,\tilde{x}_i), i=1,\ldots, m, j=1,\ldots,n,$ are the only vertices in $G/G_1\boxbackslash G/G_2$, it remains to show that $\phi$ preserves the arcs and their labels.
By definition of the Cartesian product we have that for each arc $a \in A(G_1)$ with $\mu(a)=(\tilde{y}_{j_{_1}},\tilde{y}_{j_{_2}})$, there is a set of arcs $\{a'\mid \mu(a')=((\tilde{y}_{j_{_1}},\tilde{x}_{i}),(\tilde{y}_{j_{_2}},\tilde{x}_{i})),\lambda(a)=\lambda(a'),\tilde{x}_i\in G_2\}\subseteq A(G_1\Box G_2)$.
Because this is true for all arcs $a$ of $G_1$ and all vertices $\tilde{x}_{i}$ of $G_2$, we have that each graph $G'_i$ induced by $(\tilde{y}_{j},\tilde{x}_{i}),\tilde{y}_{j}\in G_1$ is isomorphic to $G_1$, analogously, for all arcs $a$ of $G_2$ and all vertices $\tilde{y}_{j}$ of $G_1$, we have that each graph $G''_j$ induced by $(\tilde{y}_{j},\tilde{x}_{i}),\tilde{x}_{i}\in G_2$ is isomorphic to $G_2$.
Together with $G_1\cong G'_i$ and $G_2\cong G''_j$, we have that the map $\phi$ preserves the arcs and their labels and therefore $\phi$ is an isomorphism from $G$ to $G_1\boxbackslash G_2$.
Hence, $G\cong G_1\boxbackslash G_2$.
This completes the proof of Theorem <ref>.

In the following two figures, we will show that all requirements of Theorem <ref> are necessary to come to the conclusion that $\phi$ is an isomorphism from $G$ to $G_1\boxbackslash G_2$ and therefore $G\cong G_1\boxbackslash G_2$.
In Figure <ref>, we show that $G=\overundercup{i=1}{m}G'_i\cup \overundercup{j=1}{n}G''_j$ and $V(G)=\overundercup{i=1}{m}V(G'_i)=\overundercup{j=1}{n}V(G''_j)$ must not be violated.
In Figure <ref>, we show that $G'_i\cong G'_j$, $G''_i\cong G''_j$, $G/V(G'_1)/\ldots/V(G'_m)\cong G''_i$ and $G/V(G''_1)/\ldots/V(G''_n)\cong G'_i$, must not be violated.
For $L(G'_i)\cap L(G''_j)=\emptyset$, it is obvious that the decomposition will fail if there are synchronizing arcs in $G_1$ with respect to $G_2$.
Therefore, we do not show this in an example figure.

[-Stealth[length=5mm, width=4mm],midway ,auto,node distance=2.5cm,
main node/.style=circle,fill=blue!10,draw, font=]
VertexStyle/.append style=
font=, shape = circle,inner sep = 2pt, outer sep = 0pt,minimum size = 20 pt,draw

LabelStyle/.append style=font =
at (+0.5+,3++0+) $G$;
at (+1.5+,+1.4+) $G''_1$;
at (+4.5+,+2.6+) $G'_1$;
at (+4.5+,-0.4+) $G'_2$;
at (+4.5,-1-2) $G/V(G''_1)$;
at (+0.5+1,-5-1) $G/V(G'_1)/V(G'_2)$;
at (+8.5+1.5-6+3,-5.1-2-1) $G/V(G'_1)\boxbackslash G/V(G''_1)/V(G''_2)$;

[x=+1.5+, y=-3.0+,L=u_2]u_3
[x=+1.5+, y=-6.0+,L=u_3]u_4
[x=+5.5+, y=-3+,L=u_5]u_6
[x=+5.5+, y=-6+,L=u_6]u_7

[label = a](u_3)(u_4)
[label = a](u_6)(u_7)
[label = b](u_3)(u_6)
[label = b](u_4)(u_7)

[x=+1, y=+0.0,L=x̃_1]s_1
[x=+7, y=+0.0,L=u_5]s_3
[x=+4, y=+0.0,L=u_6]s_2

[label = b](s_1)(s_2)
[label = b,style=bend left=45,min distance=1cm](s_1)(s_3)
[label = a](s_3)(s_2)

[style=bend left=45,min distance=1cm](s_1)(s_3)

[x=+0, y=-3.0,L=ỹ_1]t_1
[x=+0, y=-6.0,L=ỹ_2]t_2

[label = a](t_1)(t_2)

VertexStyle/.append style=
font=,shape = rounded rectangle,inner sep = 0pt, outer sep = 0pt,minimum size = 20 pt,draw

[x=+3.0, y=-0.0,L=(ỹ_1,x̃_1)]t_1s_1
[x=+6.0, y=-0.0,L=(ỹ_1,u_6)]t_1s_2
[x=+9.0, y=-0.0,L=(ỹ_1,u_5)]t_1s_3

[x=+6.0, y=-0.0,L=(ỹ_2,u_6)]t_2s_2

[label = b](t_1s_1)(t_1s_2)
[label = a](t_1s_3)(t_2s_2)
[label = b,style=bend left=45,min distance=1cm](t_1s_1)(t_1s_3)

[style=bend left=45,min distance=1cm](t_1s_1)(t_1s_3)

[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-3.8) – (-0.5,-3.8) –  (-0.5,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+5.0,+1.5) –(+5.0,) – (+2.8,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+5.0,+1.5) –(+5.0,) – (+2.8,+0.0);

Decomposition of $G$ for which $G\neq \bigcup\limits_{i=1}^{2}G'_i\cup \bigcup\limits_{j=1}^{1}G''_j$ and $V(G)=\bigcup\limits_{i=1}^{2}V(G'_i)\neq\bigcup\limits_{j=1}^{1}V(G''_j)$ and, therefore, $G\ncong G/G'_1/G'_2\boxbackslash G/G''_1$.

[-Stealth[length=5mm, width=4mm],auto,node distance=2.5cm,decoration=
mark=at position 0.5 with >,
main node/.style=circle,fill=blue!10,draw, font=]
VertexStyle/.append style=
font=, shape = circle,inner sep = 2pt, outer sep = 0pt,minimum size = 20 pt,draw

LabelStyle/.append style=font =
at (+2.0+,3++) $G$;
at (+4.5+,+5.4-4+) $G'_1$;
at (+1.5+,+4.4-4+) $G''_1$;
at (+4.5+,+2.6-4+) $G'_2$;
at (+5.5+,+4.4-4+) $G''_2$;

at (+6.5,-1-2) $G/V(G''_1)/V(G''_2)$;
at (+1,-5-1) $G/V(G'_1)/V(G'_2)$;
at (+3.5+3,-3-2-1) $G/V(G'_1)/V(G'_2)\boxbackslash G/V(G''_1)/V(G''_2)$;

[x=+1.5+, y=+0.0+,L=u_1]u_2
[x=+1.5+, y=-3.0+,L=u_2]u_3
[x=+5.5+, y=+0.0+,L=u_4]u_5
[x=+5.5+, y=-3+,L=u_5]u_6

[label = a](u_2)(u_3)
[label = a](u_5)(u_6)
[label = b](u_2)(u_5)
[label = c](u_3)(u_6)

[x=+1, y=+0.0,L=x̃_̃1̃]s_1
[x=+4, y=+0.0,L=x̃_̃2̃]s_2

[label = b](s_1)(s_2)
[label = c,style=bend left=-45,min distance=1cm](s_1)(s_2)
[style=bend left=-45,min distance=1cm](s_1)(s_2)

[x=+0, y=-3.0,L=ỹ_1]t_1
[x=+0, y=-6.0,L=ỹ_2]t_2

[label = a](t_1)(t_2)

VertexStyle/.append style=
font=,shape = rounded rectangle,inner sep = 0pt, outer sep = 0pt,minimum size = 20 pt,draw

[x=+3.0, y=-0.0,L=(ỹ_1,x̃_1)]t_1s_1
[x=+6.0, y=-0.0,L=(ỹ_1,x̃_2)]t_1s_2

[x=+3.0, y=-0.0,L=(ỹ_2,x̃_1)]t_2s_1
[x=+6.0, y=-0.0,L=(ỹ_2,x̃_2)]t_2s_2

[label = b](t_1s_1)(t_1s_2)
[label = c,style=bend left=-45,min distance=1cm](t_1s_1)(t_1s_2)

[style=bend left=-45,min distance=1cm](t_1s_1)(t_1s_2)

[label = b](t_2s_1)(t_2s_2)
[label = c,style=bend left=-45,min distance=1cm](t_2s_1)(t_2s_2)
[style=bend left=-45,min distance=1cm](t_2s_1)(t_2s_2)

[label = a](t_1s_1)(t_2s_1)
[label = a](t_1s_2)(t_2s_2)

[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-3.6) – (-0.5,-3.6) –  (-0.5,+0.0);
[circle, -,dashed, very thick,rounded corners=18pt] (-0.5,+0.0)–(-0.5,+0.7) –(+1.0,+0.7) – (+1.0,-3.6) – (-0.5,-3.6) –  (-0.5,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+5.0,+1.5) –(+5.0,) – (+2.8,+0.0);

[circle, -,dashed, very thick,rounded corners=18pt] (+2.8,+0.0)–(-0.5,+0.0)–(-0.5,+1.5)–(+5.0,+1.5) –(+5.0,) – (+2.8,+0.0);

Decomposition of $G$ for which $G'_i\ncong G'_j$ and $G/V(G''_1)/\ldots/V(G''_n)\cong G'_i$.

[2]
J. A. Bondy and U. S. R. Murty.
Graph Theory.
Springer, Berlin (2008).

[3]
A. H. Boode.
A modification of two graph-decomposition theorems based on a vertex-removing synchronised graph product. arXiv: 2103.10808 (2022)

[4]
A. H. Boode.
Note on decompositions based on the vertex-removing synchronised graph product.
Electr. J. of Graph Theory and Appl.  10 (1)
(2022) 151–157.

[5]
A. H. Boode.
On the Automation of Periodic Hard Real-Time Processes: A Graph-Theoretical Approach. PhD thesis, University of Twente (2018). DOI: 10.3990/1.9789036545518

[6]
A. H. Boode and J. F. Broenink.
Performance of periodic real-time processes: a vertex-removing
synchronised graph product.
In Communicating Process Architectures 2014, Oxford, UK, 36th
WoTUG conference on concurrent and parallel programming, pages 119–138,
Bicester, August 2014. Open Channel Publishing Ltd.

[7]
A. H. Boode, and H. J. Broersma.
Decompositions of graphs based on a new graph product.
Discrete Applied Mathematics. 259 (2019) 31–40.

[8]
A. H. Boode, H. J. Broersma, and J. F. Broenink.
Improving the performance of periodic real-time processes: a graph
theoretical approach.
In Communicating Process Architectures 2013, Edinburgh, UK,
35th WoTUG conference on concurrent and parallel programming, pages 57–79,
Bicester, August 2013. Open Channel Publishing Ltd.

[9]
A. H. Boode, H. J. Broersma, and J. F. Broenink.
On a directed tree problem motivated by a newly introduced graph product.
Electr. J. of Graph Theory and Appl. 3 (2015) 162–181.

[11]
G. Sabidussi.
Graph multiplication.
Mathematische Zeitschrift 72 (1960) 446–457.

[12]
S. Wöhrle and W. Thomas.
Model checking synchronized products of infinite transition systems.
In in: Proc. 19th LICS, IEEE Comp. Soc, IEEE
Computer Society Press (2004) 2–11.