=Paper=
{{Paper
|id=Vol-3170/paper6
|storemode=property
|title=On Reduction of Cycloids
|pdfUrl=https://ceur-ws.org/Vol-3170/paper6.pdf
|volume=Vol-3170
|authors=Rรผdiger Valk,Daniel Moldt
|dblpUrl=https://dblp.org/rec/conf/apn/ValkM22
}}
==On Reduction of Cycloids==
https://ceur-ws.org/Vol-3170/paper6.pdf
On Reduction of Cycloids
Rรผdiger Valk1 , Daniel Moldt2
1
University of Hamburg, Department of Informatics, Hamburg, Germany
2
University of Hamburg, Department of Informatics, Hamburg, Germany
Abstract
Cycloids are particular Petri nets for modelling processes of actions and events, belonging to the funda-
ments of Petriโs general systems theory. Defined by four parameters they provide an algebraic formalism
to describe strongly synchronized sequential processes. To further investigate their structure, reduction
systems of cycloids are studied. They allow for new synthesis approaches by deducing the parameters
from the net structure.
Keywords
Structure of Petri Nets, Cycloids, Reduction, Cycloid Isomorphism, Cycloid Algebra, Synthesis,
1. Introduction
Cycloids have been introduced by C.A. Petri in [1] in the section on physical spaces, using as
examples firemen carrying the buckets with water to extinguish a fire, the shift from Galilei to
Lorentz transformation and the representation of elementary logical gates like Quine-transfers.
Besides the far-sighted work of Petri we got insight in his concepts of cycloids by numerous
seminars he hold at the University of Hamburg [2]. Based on formal descriptions of cycloids in
[3] and [4] a more elaborate formalization is given in [5], where the most important contribution
is a Synthesis Theorem computing the parameters of a cycloid from its pure graphical properties
like number of nodes and minimal cycle length. Semantical extensions to include more elaborate
features of traffic systems have been presented in [6]. The Synthesis Theorem [5] allows for a
procedure to calculate from the Petri net parameters ๐0 , ๐, ๐ด and ๐๐ฆ๐ of a cycloid the parameters
๐ผ, ๐ฝ, ๐พ and ๐ฟ of a cycloid system ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) with the same net parameters. However,
the solution was not unique, but all solutions were isomorphic with respect to particular
transformation operations. In this paper we formulate these transformations as reduction rules
and consider their reduced forms. It is proved that two cycloid systems are cycloid isomorphic if
they are reducible from each other. This follows from the cycloid isomorphism of their reduced
equivalents and shows the Synthesis Theorem to be complete in the case of cycloid isomorphic
cycloids.
To give an application for the theory, as presented in this article, consider a distributed system
of a finite number of circular and sequential processes. The processes are synchronized by
uni-directional one-bit channels in such a way that they behave like a circular traffic queue
when folded together. To give an example, Figure 1a) shows three such sequential circular
PNSEโ22, International Workshop on Petri Nets and Software Engineering, Bergen, Norway, 2022
" ruediger.valk@uni-hamburg.de (R. Valk); daniel.moldt@uni-hamburg.de (D. Moldt)
ยฉ 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org)
99
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 1: Three sequential processes synchronized by single-bit channels,
processes, each of length 7. In the initial state the control is in position 1, 3 and 5, respectively.
The synchronization, realized by the connecting channels, should be such as the three processes
would be folded together. This means, that the controls of ๐๐๐๐0 and ๐๐๐๐1 can make only
one step until the next process makes a step itself, while the control of ๐๐๐๐2 can make two
steps until ๐๐๐๐0 makes a step. Following [7] this behaviour is realized by the cycloid of Figure
1b) modelling the three processes by the transition sequences ๐๐๐๐0 = [t1 t2 ยท ยท ยท t7], as well
as ๐๐๐๐1 = [t8 t9 ยท ยท ยท t14] and ๐๐๐๐2 = [ t15 t16 ยท ยท ยท t21]. The channels are represented
by the safe places connecting these processes. By this example the power of the presented
theory is shown, since the rather complex net is unambiguously determined by the parameters
๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) = ๐(4, 3, 3, 3). A next question could be, how to change the cycloid when the
parameters of ๐ฝ = 3 processes of process length ๐ = 7 should be changed to a different value,
say the double ๐ = 14. As will be explained below, the theory returns even three cycloids,
namely ๐1 (4, 3, 10, 3), ๐2 (4, 3, 6, 6) and ๐3 (4, 3, 2, 9). However, we will prove in this article
that these three solutions are isomorphic and are related by a reduction calculus. The flexibilty
of the model is also shown by the following additional example. By doubling in ๐(4, 3, 3, 3)
the value of ๐ฝ we obtain the cycloid ๐(4, 6, 3, 3), which models a distributed system of three
circular sequential processes, each of length ๐ = 10. However, different to the examples above,
each process contains two control tokens. Translated to the distributed model, in the initial
100
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
state each of the three sequential processes contains two items, particularly ๐๐๐๐0 in positions
0 and 5 in the circular queue of length 10, ๐๐๐๐1 in positions 1 and 6 and ๐๐๐๐2 in positions 3
and 8. The present article is part of a general project to investigate all such features of cycloids
to make them available for Software Engineering.
We recall some standard notations for set theoretical relations. If ๐
โ ๐ดร๐ต is a relation
and ๐ โ ๐ด then ๐
[๐ ] := {๐ | โ๐ข โ ๐ : (๐ข, ๐) โ ๐
} is the image of ๐ and ๐
[๐] stands for
๐
[{๐}]. ๐
โ1 is the inverse relation and ๐
+ is the transitive closure of ๐
if ๐ด = ๐ต. Also, if
๐
โ ๐ดร๐ด is an equivalence relation then [[๐]]๐
is the equivalence class of the quotient ๐ด/๐
containing ๐. Furthermore N+ , Z and R denote the sets of positive integer, integer and real
numbers, respectively. For integers: ๐|๐ if ๐ is a factor of ๐. The ๐๐๐๐ข๐๐-function is used in
the form ๐ ๐๐๐ ๐ = ๐ โ ๐ ยท โ ๐๐ โ, which also holds for negative integers ๐ โ Z. In particular,
โ๐ ๐๐๐ ๐ = ๐ โ ๐ for 0 < ๐ โค ๐.
2. Petri Space and Cycloids
We define (Petri) nets as they will be used in this article.
Definition 1 ([5]). As usual, a net ๐ฉ = (๐, ๐, ๐น ) is defined by non-empty, disjoint sets ๐ of
places and ๐ of transitions, connected by a flow relation ๐น โ (๐ ร ๐ ) โช (๐ ร ๐) and ๐ := ๐ โช ๐ .
โ โ
A transition ๐ก โ ๐ is active or enabled in a marking ๐ โ ๐ if ๐ก โ ๐ โง ๐ก โฉ ๐ = โ
1 . In this
๐ก โ โ โ โ
case we obtain ๐ โ ๐ โฒ if ๐ โฒ = ๐ โ ๐กโช๐ก , where ๐ฅ := ๐น โ1 [๐ฅ], ๐ฅ := ๐น [๐ฅ] denotes the input
*
and output elements of an element ๐ฅ โ ๐, respectively. โ is the reflexive and transitive closure
of โ. A net together with an initial marking ๐0 โ ๐ is called a net system (๐ฉ, ๐0 ). Given
two net systems ๐ฉ1 = (๐1 , ๐1 , ๐น1 , ๐01 ) and ๐ฉ2 = (๐2 , ๐2 , ๐น2 , ๐02 ) a mapping ๐ : ๐1 โ ๐2
(๐๐ = ๐๐ โช ๐๐ ) is a net morphism ([8]) if ๐ (๐น1 โฉ (๐1 ร ๐1 )) โ (๐น2 โฉ (๐2 ร ๐2 )) โช ๐๐ and
๐ (๐น1 โฉ (๐1 ร ๐1 )) โ (๐น2 โฉ (๐2 ร ๐2 )) โช ๐๐ and ๐ (๐01 ) = ๐02 . It is an isomorphism if it is
bijective and the inverse mapping ๐ โ1 is also a net morphism. ๐ฉ1 โ ๐ฉ2 denotes isomorphic nets.
Omitting the initial states the definitions apply also to nets.
Petri started with an event-oriented version of the Minkowski space which is called Petri
space now. Contrary to the Minkowski space, the Petri space is independent of an embedding
into Z ร Z. It is therefore suitable for the modelling in transformed coordinates as in non-
Euclidian space models. However, the reader will wonder that we will apply linear algebra, for
instance using equations of lines. This is done only to determine the relative position of points.
It can be understood by first topologically transforming and embedding the space into R ร R,
calculating the position and then transforming back into the Petri space. Distances, however,
are not computed with respect to the Euclidean metric, but by counting steps in the grid of the
Petri space, like Manhattan distance or taxicab geometry.
For instance, the transitions of the Petri space might model the moving of items in time and
space in an unlimited way. To be concrete a coordination system is introduced with arbitrary
origin (see Figure 2 a). The occurrence of transition ๐ก1,0 in this figure, for instance, can be
interpreted as a step of a traffic item (the token in the left input-place) in both space and time
1 โ
With the condition ๐ก โฉ ๐ = โ
we follow Petriโs definition, but with no impacts in this article.
101
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 2: a) Petri space, b) circular traffic queue and c) time orthoid.
direction. It is enabled by a gap or co-item (the token in the right input-place), which is enabling
a next traffic item after occurrence of ๐ก2,0 . By the following definition the places obtain their
names by their input transitions (see Figure 3 a).
Definition 2 ([5]). A ๐ ๐๐ก๐๐ ๐ ๐๐๐๐ is defined by the net ๐ซ๐ฎ 1 := (๐1 , ๐1 , ๐น1 ) where
๐1 = ๐1โ โช ๐1โ , ๐1โ = {๐ โ ๐,๐ | ๐, ๐ โ Z} , ๐1โ = {๐ โ โ โฉ
๐,๐ | ๐, ๐ โ Z} , ๐1
๐1โ = โ
, ๐1 = {๐ก๐,๐ | ๐, ๐ โ Z} , ๐น1 = {(๐ก๐,๐ , ๐ โ โ
๐,๐ ) | ๐, ๐ โ Z} โช {(๐ ๐,๐ , ๐ก๐+1,๐ ) | ๐, ๐ โ Z} โช
{(๐ก๐,๐ , ๐ ๐,๐ ) | ๐, ๐ โ Z} โช {(๐ ๐,๐ , ๐ก๐,๐+1 ) | ๐, ๐ โ Z} (cutout in Figure 3 a). ๐1โ is the set of for-
โ โ
โ
ward places and ๐1โ the set of backward places. โ๐ก๐,๐ := ๐ โ ๐โ1,๐ is the forward input place of
โ โ โ
๐ก๐,๐ and in the same way ๐ก๐,๐ := ๐ ๐,๐โ1 , ๐ก๐,๐ := ๐ ๐,๐ and ๐ก๐,๐ := ๐ โ
โ โ โ โ โ
๐,๐ (Figure 3 a).
In two steps, by a twofold folding with respect to time and space, Petri defined the cyclic
structure of a cycloid. One of these steps is a folding ๐ with respect to space with ๐ (๐, ๐) = ๐ (๐ +
๐ผ, ๐ โ ๐ฝ), fusing all points (๐, ๐) of the Petri space with (๐ + ๐ผ, ๐ โ ๐ฝ) where ๐, ๐ โ Z, ๐ผ, ๐ฝ โ N+
([1], page 37). While Petri gave a general motivation, oriented in physical spaces, we interpret
the choice of ๐ผ and ๐ฝ by our model of traffic queues.
We assume that our model of a circular traffic queues has six slots containing two items ๐0
and ๐1 as shown in Figure 2 b). These are modelled in Figure 2 a) by the tokens in the forward
input places of ๐ก1,0 and ๐ก3,โ1 . The four co-items are represented by the tokens in the backward
input places of ๐ก1,0 , ๐ก2,0 and ๐ก3,โ1 , ๐ก4,โ1 . By the occurrence of ๐ก1,0 and ๐ก2,0 the first item can
102
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 3: a) Petri space, b) Fundamental parallelogram of ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) = ๐(4, 2, 2, 3).
make two steps, as well as the second item by the transitions ๐ก3,โ1 and ๐ก4,โ1 , respectively. Then
๐1 has reached the end of the queue and has to wait until the first item is leaving its position.
Hence, we have to introduce a precedence restriction between the transitions ๐ก1,0 and ๐ก5,โ1 .
This is done by fusing the transitions ๐ก5,โ1 and the left-hand follower ๐ก1,1 of ๐ก1,0 . To determinate
๐ผ and ๐ฝ we set (5, โ1) = (1 + ๐ผ, 1 โ ๐ฝ) which gives ๐ผ = 4 and ๐ฝ = 2. By the equivalence
relation ๐ก๐,๐ โก ๐ก๐+4,๐โ2 we obtain the structure in Figure 2 c). The resulting still infinite net
is called a time orthoid ([1], page 37), as it extends infinitely in temporal future and past. The
second step is a folding with ๐ (๐, ๐) = ๐ (๐ + ๐พ, ๐ + ๐ฟ) with ๐พ, ๐ฟ โ N+ reducing the system to
a cyclic structure also in time direction. As shown in [7] an equivalent cycloid for the traffic
queue of Figure 2 b) has the parameters (๐ผ, ๐ฝ, ๐พ, ๐ฟ) = (4, 2, 2, 2). To keep the example more
general, in Figure 3 b) the values (๐ผ, ๐ฝ, ๐พ, ๐ฟ) = (4, 2, 2, 3) are chosen. In this representation of
a cycloid, called fundamental parallelogram, the squares of the transitions as well as the circles
of the places are omitted. All transitions with coordinates within the parallelogram belong to
the cycloid including those on the lines between ๐, ๐ and ๐, ๐ , but excluding those of the
points ๐, ๐
, ๐ and those on the dotted edges between them. All parallelograms of the same
shape, as indicated by dotted lines outside the fundamental parallelogram are fused with it.
Definition 3 ([5]). A cycloid is a net ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) = (๐, ๐, ๐น ), defined by parameters
๐ผ, ๐ฝ, ๐พ, ๐ฟ โ N+ , by a quotient [8] of the Petri space ๐ซ๐ฎ 1 := (๐1 , ๐1 , ๐น1 ) with respect to the
equivalence relation โก โ ๐1 ร ๐1 with ๐1 = ๐1 โช ๐1 , โก[๐1โ ] โ ๐1โ , โก[๐1โ ] โ ๐1โ , โก[๐1 ] โ
๐1 , ๐ฅ๐,๐ โก ๐ฅ๐+๐๐ผ+๐๐พ, ๐โ๐๐ฝ+๐๐ฟ for all ๐, ๐, ๐, ๐ โ Z , ๐ = ๐1 /โก , (๏ธ[[๐ฅ]]โก ๐น )๏ธ[[๐ฆ]]โก โ
๐ผ ๐พ
โ ๐ฅโฒ โ [[๐ฅ]]โก โ ๐ฆ โฒ โ [[๐ฆ]]โก : ๐ฅโฒ ๐น1 ๐ฆ โฒ for all ๐ฅ, ๐ฆ โ ๐1 . The matrix A = is called
โ๐ฝ ๐ฟ
103
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
the matrix of the cycloid. Petri denoted the number |๐ | of transitions as the area ๐ด of the cycloid
and proved in [1] its value to |๐ | = ๐ด = ๐ผ๐ฟ + ๐ฝ๐พ which equals the determinant ๐ด = ๐๐๐ก(A).
The embedding of a cycloid in the Petri space is called fundamental parallelogram (see Figure 3
b).
Definition 4. a) The net ๐ฉ = (๐, ๐, ๐น ) from Definition 3 (without explicitly giving the parame-
โ โ
ters ๐ผ, ๐ฝ, ๐พ, ๐ฟ) is called the underlying net of the cycloid. It is a ๐ -net with | ๐ | = |๐ | = 1 for all
places ๐ โ ๐.
b) When the distinction between forward places ๐ โ and backward places ๐ โ is kept we denote it
as the cycloid net of the cycloid and represent it by ๐ฉ = (๐ โ , ๐ โ , ๐, ๐น ).
To give an example, Figure 8 shows a graphical representation of the cycloid net of the cycloid
system ๐(5, 3, 2, 6, ๐0 )2 . The forward places ๐ โ and the backward places ๐ โ are labelled by
the letter f and b, respectively. Note that the parameters are not visible in this representation,
but will be deducible by the results of Sections 4 and 5. Also degenerate cycloids have been
introduced by C.A. Petri [9] (page 46) and their properties are studied in [5]. In this article they
are used within proofs only.
Definition 5 ([5]). If in Definition 3 at least one of the parameters ๐ผ, ๐ฝ, ๐พ, ๐ฟ is zero we call
๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) a degenerate cycloid when also the additional restriction ๐ด > 0 for the area ๐ด =
๐ผ๐ฟ + ๐ฝ๐พ holds.
For proving the equivalence of two points in the Petri space the following procedure3 is
useful.
Theorem 2.1 ([7]). Two points โ๐ฅ1 , โ๐ฅ2 โ ๐1 are equivalent โ๐ฅ1 โก โ๐ฅ2 if and only if for the
difference โ๐ฃ := ๐ฅโ2 โ ๐ฅโ1 the parameter vector ๐(๐ฃโ ) = ๐ด1 ยท B ยท โ๐ฃ has integer values, where ๐ด is the
(๏ธ )๏ธ
๐ฟ โ๐พ
area and B = . Also, in analogy to Definition 3 we obtain โ๐ฅ1 โก โ๐ฅ2 โ โ ๐, ๐ โ Z :
๐ฝ ๐ผ
(๏ธ )๏ธ
๐
๐ฅโ2 โ ๐ฅโ1 = A .
๐
Since constructions of cycloids may result in different but isomorphic forms the following
theorem is important. We give here a proof using the cycloid algebra from Theorem 2.1, which
was not yet known when the article [5] had been published.
Theorem 2.2 ([5]). The following cycloids are net isomorphic (Definition 1) to ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ):
a) ๐(๐ผ, ๐ฝ, ๐พ โ ๐ผ, ๐ฟ + ๐ฝ) if ๐พ > ๐ผ,
b) ๐(๐ผ, ๐ฝ, ๐พ + ๐ผ, ๐ฟ โ ๐ฝ) if ๐ฟ > ๐ฝ.
Proof. Let be ๐ = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) with matrix โโ
(๏ธ A (Definition
)๏ธ 3) and the vector ๐๐ := (๐, ๐) โ Z .
2
๐ผ ๐พยฑ๐ผ
By Theorem 2.1 with the matrix A1 = of ๐1 = ๐1 (๐ผ, ๐ฝ, ๐พ ยฑ ๐ผ, ๐ฟ โ ๐ฝ) we obtain
โ๐ฝ ๐ฟ โ ๐ฝ
2
The net is generated by the Automatic Net Layout of the RENEW tool.
3
The algorithm is implemented under http://cycloids.de/home.
104
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
โโ โโ 0 ยฑ๐ผ โโ โโ ยฑ๐ ยท ๐ผ โโ ยฑ๐
A1 ยท ๐๐ = A ยท ๐๐ + ยท ๐๐ = A ยท ๐๐ + = A ยท ๐๐ + A ยท =
0 โ๐ฝ โ๐ ยท ๐ฝ 0
(๏ธ )๏ธ
๐ยฑ๐
Aยท . Hence, the equivalence relations of ๐ and ๐1 are the same.
๐
In plane geometry, a shear mapping is a linear map that displaces each point in a fixed
direction, by an amount proportional to its signed distance from the line that is parallel to that
direction and goes through the origin4 . For (๏ธa cycloid
)๏ธ ๐(๐ผ, )๏ธ ๐ฟ) the corners
(๏ธ ๐ฝ, ๐พ, (๏ธ of
)๏ธ its fundamental
(๏ธ )๏ธ
0 ๐ผ ๐ผ+๐พ ๐พ
parallelogram have the coordinates ๐ = ,๐ = ,๐
= and ๐ = .
0 โ๐ฝ ๐ฟโ๐ฝ ๐ฟ
Comparing them with the corners ๐โฒ , ๐ โฒ , ๐
โฒ , ๐โฒ of the transformed
(๏ธ )๏ธ cycloid ๐(๐ผ, ๐ฝ, ๐พ + ๐ผ, ๐ฟ โ ๐ฝ)
๐พ + ๐ผ
of Theorem 2.2 b) we observe ๐โฒ = ๐, ๐ โฒ = ๐, ๐โฒ = = ๐
and the lines ๐, ๐
and
๐ฟโ๐ฝ
๐โฒ , ๐
โฒ are the same. Therefore the second is a shearing of the first one. This is shown in Figure5 4
for the cycloids ๐(2, 3, 2, 8), ๐(2, 3, 4, 5) and ๐(2, 3, 6, 2). When applying the equivalences of
Figure 4: A shearing from ๐(2, 3, 2, 8) to ๐(2, 3, 6, 2).
4
https://en.wikipedia.org/wiki/Shear_mapping
5
The figure has been designed using the tool http://cycloids.adventas.de.
105
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Theorem 2.2 the parameters ๐พ and ๐ฟ are changed which leads to the following definition of
๐พ๐ฟ-reduction equivalence.
Definition 6. If a cycloid or cycloid system ๐1 can be obtained from a cycloid ๐2 by iterated appli-
cations of the transformations given in Theorem 2.2 then they are called ๐พ๐ฟ-reduction equivalent,
denoted ๐1 โ๐พ๐ฟ ๐2 .
Lemma 1 ([5]). For any cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) there is a minimal cycle containing the origin ๐ in
its fundamental parallelogram representation.
For the next Theorem from [5], we give a proof which follows the same concept, but is more
formal.
Theorem 2.3 ([5]).
{๏ธ The length of a minimal cycle of a cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) is ๐๐ฆ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) =
โ ๐ฝ๐ฟ โ(๐ผ โ ๐ฝ) if ๐ผ โค ๐ฝ
๐๐ฆ๐ = ๐พ + ๐ฟ + ๐พ
โโ ๐ผ โ(๐ผ โ ๐ฝ) if ๐ผ > ๐ฝ
The length of a minimal cycle of a degenerate cycloid with ๐ผ โค ๐ฝ is also ๐๐ฆ๐ if ๐ผ > 0 and ๐ฝ > 0.
Proof. a) We first consider the case ๐ผ โค ๐ฝ. With respect to paths and cycles in the fundamental
parallelogram and by Lemma 1 it is sufficient to consider paths starting in the origin ๐. Such
a cycle of the cycloid corresponds to a path(๏ธfrom )๏ธ ๐ to(๏ธan equivalent
)๏ธ point โ๐ฅ in the Petri
๐พ ๐ผ
space. Each such point has the form โ๐ฅ = ๐ ยท +๐ยท for ๐, ๐ โ N. The case ๐ = 0
๐ฟ โ๐ฝ
is to be excluded since no point (๐, ๐) with ๐ < 0 is reachable from ๐ in the Petri space.
Since a cycle of minimal(๏ธlength )๏ธ is searched,
(๏ธ )๏ธ also the cases ๐ > 1 are excluded. Therefore we
๐พ ๐ผ
consider the points โ๐ฅ = +๐ยท for ๐ โ N. Next we prove that increasing the value
๐ฟ โ๐ฝ
of ๐ does not increase the distance to the origin (while the condition ๐ โฅ 0 is not violated
when(๏ธgoing)๏ธ ๐ฝ steps(๏ธin )๏ธdirection
(๏ธ )๏ธโ๐). More precisely, for any ๐ โฅ 0, ๐ โฅ 0 we have to prove
๐ ๐ ๐ผ
๐(๐, ) โฅ ๐(๐, + ) under the condition ๐ โ ๐ฝ โฅ 0. This follows from ๐ผ โค ๐ฝ
๐ ๐ โ๐ฝ
(๏ธ )๏ธ
๐
by 0 โฅ ๐ผ โ ๐ฝ โ ๐ + ๐ โฅ ๐ + ๐ผ + ๐ โ ๐ฝ โ |๐ + ๐| โฅ |๐ + ๐ผ| + |๐ โ ๐ฝ| โ ๐(๐, )โฅ
๐
(๏ธ )๏ธ
๐+๐ผ
๐(๐, ) Again, since points (๐, ๐) with ๐ < 0 are not reachable, we obtain the condition
๐โ๐ฝ
๐ฟ + ๐ ยท (โ๐ฝ) โฅ 0, which is ๐ โค ๐ฝ๐ฟ . Hence, the maximal integer value for ๐ is ๐ = โ ๐ฝ๐ฟ โ. The
length of this cycle is ๐พ + ๐ฟ + โ ๐ฝ๐ฟ โ ยท (๐ผ โ ๐ฝ) , which finishes the proof in this case.
b) For the alternative case we look at the cycloid ๐(๐ฝ, ๐ผ, ๐ฟ, ๐พ) (by interchanging ๐ผ and ๐ฝ, as
well as ๐พ and ๐ฟ), which is net isomorphic [5] and therefore has a minimal cycle of the same
length, hence ๐๐ฆ๐ = ๐พ + ๐ฟ + โ ๐ผ๐พ โ ยท (๐ฝ โ ๐ผ) in the case ๐ผ > ๐ฝ. Both cases together verify the
theorem.
c) For the case of a degenerate cycloid we refer to [5].
Definition 7 ([10]). A forward-cycle of a cycloid is an elementary6 cycle containing only forward
places of ๐1โ . A backward-cycle of a cycloid is an elementary cycle containing only backward
places of ๐1โ (Definition 2).
6
An elementary cycle is a cycle where all nodes are different.
106
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Theorem 2.4 ([10]). In a cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) with area ๐ด the length of a forward-cycle is
๐ด
๐ = ๐๐๐(๐ฝ,๐ฟ) and length of a backward-cycle is ๐โฒ = ๐๐๐(๐ผ,๐พ)
๐ด
. The cycloid contains ๐๐๐(๐ฝ, ๐ฟ)
disjoint forward-cycles and ๐๐๐(๐ผ, ๐พ) disjoint backward cycles. With respect to the standard ini-
๐ฝ ๐ผ
tial marking (Definition 9) the number of tokens in a forward cycle is ๐๐๐(๐ฝ,๐ฟ) and ๐๐๐(๐ผ,๐พ) in a
backward cycle.
For the cycloids ๐(4, 3, 3, 3) and ๐(4, 6, 3, 3) from the introduction we obtain ๐ = 7 and
๐ = 10, respectively. The number of tokens in a forward-cycle of ๐(4, 6, 3, 3) is ๐๐๐(6,3)
6
= 2.
An important class of cycloids has the property to represent a number of sequential processes
of the same length. Such a cycloid is called regular.
Definition 8. A cycloid ๐ = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) is regular if ๐ฝ divides ๐ฟ. It consists of a number ๐ฝ
forward-cycles (called processes) of length ๐ = ๐ด
๐ฝ . ๐ is called is co-regular if ๐ผ divides ๐พ. Then it
consists of a number ๐ผ backward-cycles (called co-processes) of length ๐ = ๐ด ๐ผ.
The cycloid ๐(4, 3, 3, 3) from the introduction is regular, whereas and ๐(4, 6, 3, 3) is not.
For the computation of the parameters ๐พ and ๐ฟ for given values of ๐ผ, ๐ฝ and ๐ we implicitly
presume regular cycloids which leads to the equation ๐ = ๐ด ๐ฝ = ๐ฝ ยท ๐ฟ + ๐พ or ๐พ = โ ๐ฝ ยท ๐ฟ + ๐.
๐ผ ๐ผ
For the values ๐ผ = 4, ๐ฝ = 3, ๐ = 14, as given in the example of the introduction, the equation
๐พ = โ 34 ยท ๐ฟ + 14 has three solutions for the pair (๐พ, ๐ฟ), namely (10, 3), (6, 6) and (2, 9), since
only positive integer values are consistent. In different examples there is only one solution or
even none (for instance with (๐ผ, ๐ฝ, ๐) = (5, 11, 4)).
Definition 9 ([5]). For a cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) we define a cycloid system ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) or
๐(๐ฉ, ๐0 ) by adding the standard initial marking:
๐0 = {๐ โ โ
๐,๐ โ ๐1 | ๐ฝ๐ + ๐ผ๐ โค 0 โง ๐ฝ(๐ + 1) + ๐ผ๐ > 0} /โก โช
โ โ
{๐ ๐,๐ โ ๐1 | ๐ฝ๐ + ๐ผ๐ โค 0 โง ๐ฝ๐ + ๐ผ(๐ + 1) > 0} /โก .
Lemma 2 ([5]). Given a cycloid system ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) with standard initial marking ๐0 then
|๐0 โฉ ๐ โ | = ๐ฝ and |๐0 โฉ ๐ โ | = ๐ผ.
See Figure 5 for an example. The following Synthesis Theorem allows for a cycloid system,
given as a net without the parameters ๐ผ, ๐ฝ, ๐พ, ๐ฟ, to compute these parameters. It does not
necessarily give a unique result, but for ๐ผ ฬธ= ๐ฝ the resulting cycloids are isomorphic. In
โ
the theorem ๐0 := |{๐ก| | ๐ก โฉ ๐0 | โฅ 1 }| is the number of initially marked transitions and
โ
๐๐ := |{๐ก| | ๐ก โฉ ๐0 | = 2 }| is the number of initially active transitions. They are used to
determine ๐ผ and ๐ฝ. In this paper, however, we use Lemma 2, instead.
Theorem 2.5 (Synthesis Theorem [5]). Cycloid systems with identical system parameters ๐0 , ๐๐ ,
๐ด and ๐๐ฆ๐ are called ๐-๐๐๐ข๐๐ฃ๐๐๐๐๐ก. Given a cycloid system ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) in its net repre-
sentation (๐, ๐, ๐น, ๐0 ) where the parameters ๐0 , ๐๐ , ๐ด and ๐๐ฆ๐ are known (but the parameters
๐ผ, ๐ฝ, ๐พ, ๐ฟ are not). Then a ๐-๐๐๐ข๐๐ฃ๐๐๐๐๐ก cycloid ๐(๐ผโฒ , ๐ฝ โฒ , ๐พ โฒ , ๐ฟ โฒ ) can be computed by ๐ผโฒ = ๐0 ,
๐ฝ โฒ = ๐๐ and for ๐พ โฒ , ๐ฟ โฒ by some positive integer solution of the following formulas using these set-
tings of ๐ผโฒ and ๐ฝ โฒ :
โฒ
a) case ๐ผโฒ > ๐ฝ โฒ : ๐พ โฒ ๐๐๐ ๐ผโฒ = ๐ผ ๐ผยท๐๐ฆ๐โ๐ด
โฒ โ๐ฝ โฒ and ๐ฟ โฒ = ๐ผ1โฒ (๐ด โ ๐ฝ โฒ ยท ๐พ โฒ ),
โฒ
b) case ๐ผโฒ < ๐ฝ โฒ : ๐ฟ โฒ ๐๐๐ ๐ฝ โฒ = ๐ฝ ๐ฝยท๐๐ฆ๐โ๐ด
โฒ โ๐ผโฒ and ๐พ โฒ = ๐ฝ1โฒ (๐ด โ ๐ผโฒ ยท ๐ฟ โฒ ),
107
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
c) case ๐ผโฒ = ๐ฝ โฒ : ๐พ โฒ = โ ๐๐ฆ๐ โฒ ๐๐ฆ๐
2 โ and ๐ฟ = โ 2 โ.
These equations may result in different cycloid parameters, however the cycloids are isomorphic
in the cases a) and b) as in Theorem 2.2. If the distinction between ๐ โ and ๐ โ is known Lemma
2 can be used in place of ๐0 and ๐๐ .
When working with cycloids it is sometimes important to find for a transition outside
the fundamental parallelogram the equivalent element inside. In general, by enumerating
all elements of the fundamental parallelogram (using Theorem 7 in [11]) and applying the
equivalence test from Theorem 2.1 a runtime is obtained, which already fails for small cycloids.
The following theorem allows for a better algorithm7 , which is linear with respect to the cycloid
parameters.
Theorem 2.6 ([10]). For any element โ๐ข = (๐ข, ๐ฃ) of the Petri(๏ธ space
)๏ธ the (unique) equivalent
๐
element within the fundamental parallelogram is โ๐ฅ = โ๐ข โ A where ๐ = โ ๐ด1 (๐ข๐ฟ โ ๐ฃ๐พ)โ
๐
and ๐ = โ ๐ด1 (๐ฃ๐ผ + ๐ข๐ฝ)โ.
3. Reduction of Cycloid systems
Following Theorem 2.2 we introduce two reduction rules for cycloids keeping them isomorphic.
Definition 10. For cycloids ๐1 (๐ผ1 , ๐ฝ1 , ๐พ1 , ๐ฟ1 ) and ๐2 (๐ผ2 , ๐ฝ2 , ๐พ2 , ๐ฟ2 ) the following conditional
reduction rules are defined:
R1: ๐ผ2 = ๐ผ1 , ๐ฝ2 = ๐ฝ1 , ๐พ2 = ๐พ1 โ ๐ผ1 and ๐ฟ2 = ๐ฟ1 + ๐ฝ1 if ๐พ1 > ๐ผ1 . If this rule cannot be
applied the cycloid system ๐ = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) is called ๐พ-reduced. If ๐ is ๐พ-reduced and ๐พ < ๐ผ
(resp. ๐พ = ๐ผ) then ๐ is called strongly ๐พ-reduced (resp. weakly ๐พ-reduced).
R2: ๐ผ2 = ๐ผ1 , ๐ฝ2 = ๐ฝ1 , ๐พ2 = ๐พ1 + ๐ผ1 and ๐ฟ2 = ๐ฟ1 โ ๐ฝ1 if ๐ฟ1 > ๐ฝ1 .
If this rule cannot be applied the cycloid system ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ, ๐0 ) is called ๐ฟ-reduced. If ๐ is ๐ฟ-
reduced and ๐ฟ < ๐ฝ (resp. ๐ฟ = ๐ฝ) then ๐ is called strongly ๐ฟ-reduced (resp. weakly ๐ฟ-reduced).
In some cases for reduced cycloids the cycloid parameters ๐พ and ๐ฟ can be directly deduced
from the parameters ๐ผ and ๐ฝ and the properties ๐๐ฆ๐ and ๐ด.
Theorem 3.1. Let be ๐ = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) a cycloid with known values ๐ผ ฬธ= ๐ฝ, area ๐ด, minimal
1 1
cycle length ๐๐ฆ๐, ๐ := ๐ผโ๐ฝ ยท (๐ผ ยท ๐๐ฆ๐ โ ๐ด) and ๐ := ๐ผโ๐ฝ ยท (๐ด โ ๐ฝ ยท ๐๐ฆ๐).
a) If ๐ is strongly ๐ฟ-reduced and ๐ผ โค ๐ฝ or strongly ๐พ-reduced and ๐ผ > ๐ฝ then ๐พ = ๐ and
๐ฟ =๐.
b) If ๐ is weakly ๐ฟ-reduced and ๐ผ โค ๐ฝ then ๐พ = ๐ โ ๐ผ and ๐ฟ = ๐ฝ.
c) If ๐ is weakly ๐พ-reduced and ๐ผ > ๐ฝ then ๐พ = ๐ผ and ๐ฟ = ๐ โ ๐ฝ.
Proof. Since in item a) of the theorem we have โ ๐ผ๐พ โ = 0 or โ ๐ฝ๐ฟ โ = 0 by Theorem 2.3 we ob-
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐๐ฆ๐ 1 1 ๐พ
tain ๐๐ฆ๐ = ๐พ + ๐ฟ. With the formula for ๐ด we have the equation =
๐ด ๐ฝ ๐ผ ๐ฟ
7
The algorithm is implemented under http://cycloids.de/home.
108
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 5: The cycloid system ๐(2, 3, 6, 2, ๐0 )
(๏ธ )๏ธ (๏ธ )๏ธโ1 (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐พ 1 1 ๐๐ฆ๐ ๐ผ โ1 ๐๐ฆ๐
to compute the solution = = ๐ผโ๐ฝ 1
=
๐ฟ ๐ฝ ๐ผ ๐ด โ๐ฝ 1 ๐ด
(๏ธ )๏ธ (๏ธ )๏ธ
๐ผ ยท ๐๐ฆ๐ โ ๐ด ๐
1
๐ผโ๐ฝ โ๐ฝ ยท ๐๐ฆ๐ + ๐ด = . If ๐ฝ = ๐ฟ in item b) then we make another step in the ๐ฟ-
๐
reduction and obtain a degenerate cycloid with ๐ฟ = 0. Then again โ ๐ฝ๐ฟ โ = 0 and we proceed
as before. By reversing the reduction from the degenerate cycloid it follows ๐พ = ๐ โ ๐ผ and
๐ฟ = 0 + ๐ฝ. The case for ๐ผ > ๐ฝ is similar.
To give an example, for the strongly ๐ฟ-reduced cycloid system ๐(2, 3, 6, 2, ๐0 ) of Figure 5
with ๐๐ฆ๐ = 8 and ๐ด = 22, we obtain ๐พ = ๐ผโ๐ฝ 1
ยท (๐ผ ยท ๐๐ฆ๐ โ ๐ด) = 6 and
๐ฟ = ๐ผโ๐ฝ ยท (๐ด โ ๐ฝ ยท ๐๐ฆ๐) = 2. Different to Theorem 3.1 the next result is not a special case of
1
Theorem 2.2, which does not work in the case of ๐ผ = ๐ฝ. To distinguish cycloids also in this case
we introduce the notion of an inclination. In this case a cycloid has transitions with coordinates
๐ก0,0 , ๐ก1,โ1 , ยท ยท ยท , ๐ก๐ผโ1,โ(๐ผโ1) , for instance the transitions ๐ก0,0 = t1, ๐ก1,โ1 = t19, ๐ก2,โ2 = t10
in ๐(3, 3, 1, 8, ๐01 ) from Figure 6. A forward cycle of such a cycloid contains one of these
transition repeatedly. The inclination is the index of the first such transition. If the cycloid is
regular (Definition 8), i.e. ๐ฝ divides ๐ฟ then this transition is ๐ก0,0 and the inclination is ๐๐๐ = 0.
The values of ๐๐๐ are bounded by 0 โค ๐๐๐ < ๐ผ.
Definition 11. Let ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) be a cycloid with ๐ผ = ๐ฝ. A forward or backward cycle (Defini-
tion 7) starting in the origin ๐ก0,0 contains one of the transitions {๐ก๐,โ๐ |0 โค ๐ < ๐ผ} for the first
time, say ๐ก๐,โ๐ .
109
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
a) With respect to the forward cycle the forward inclination of the cycloid is defined by this index
๐๐๐ := ๐ โ {0, ยท ยท ยท , ๐ผ โ 1}. The path from ๐ก0,0 to ๐ก๐,โ๐ is called pseudo-process and its length is
denoted by ๐.
ฬ๏ธ
b) With respect to the backward cycle the backward inclination of the cycloid is defined by this in-
dex ๐๐๐โฒ := ๐ โ {0, ยท ยท ยท , ๐ผโ1}. In this case, the path from ๐ก0,0 to ๐ก๐,โ๐ is called pseudo-co-process
and its length is denoted by ๐ฬ๏ธโฒ .
Theorem 3.2. Let ๐ = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) be a cycloid with ๐ผ = ๐ฝ.
a) The forward inclination ๐๐๐ exists and has the values ๐๐๐ = ๐ฟ ๐๐๐ ๐ผ and ๐ฬ๏ธ = ๐พ + ๐ฟ. If ๐ is
๐ฟ-reduced form (Definition 10) then ๐๐๐ = ๐ฟ and if ๐ is regular then ๐๐๐ = 0 and ๐ฬ๏ธ = ๐ for the
process length ๐ (Definition 8).
b) The backward inclination ๐๐๐โฒ exists and has the value ๐๐๐โฒ = 0 if ๐ is co-regular, else ๐๐๐โฒ =
๐ผ โ ๐พ ๐๐๐ ๐ผ. Moreover, ๐ฬ๏ธโฒ = ๐พ + ๐ฟ.
(๏ธ )๏ธ (๏ธ )๏ธ
๐ฬ๏ธ ๐
Proof. a) From the definition of ๐๐๐ we obtain โก which is by Theorem 2.1 equivalent
0 โ๐
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ฟ โ๐พ ๐ฬ๏ธ โ ๐ ๐ โ ๐) โ ๐ ยท ๐พ
๐ฟ(ฬ๏ธ
to Z2 โ ๐ด1 1
= ๐ผยท(๐พ+๐ฟ) . The second row of this formula
๐ผ ๐ผ ๐ ๐ผ ยท ๐ฬ๏ธ
gives the solution ๐ฬ๏ธ = ๐พ + ๐ฟ. Using this result from the first row we obtain Z โ ๐ด1 (๐ฟ(๐พ +
๐ฟ โ ๐) โ ๐ ยท ๐พ) = (๐ฟโ๐)ยท(๐พ+๐ฟ)
๐ผยท(๐พ+๐ฟ) = ๐ฟโ๐๐ผ with a solution ๐ = ๐ฟ. Therefore ๐ก๐ฟ,โ๐ฟ is a transition
of the form ๐ก๐,โ๐ as mentioned in Definition 11. However the condition 0 โค ๐ < ๐ผ may
not be fulfilled as the transition may lie outside the fundamental parallelogram. To find the
(unique) equivalent transition inside the fundamental parallelogram we apply Theorem 2.6.
๐ฟยท(๐พ+๐ฟ)
With (๐ข, ๐ฃ) = (๐ฟ, โ๐ฟ) and ๐ด = ๐ผ ยท (๐พ + ๐ฟ) we obtain ๐ = โ ๐ด1 (๐ข ยท ๐ฟ โ ๐ฃ ยท ๐พ)โ = โ ๐ผยท(๐พ+๐ฟ) โ = โ ๐ผ๐ฟ โ
and ๐ = โ ๐ด1 (๐ฃ ยท ๐ผ + ๐ข ยท ๐ฝ)โ = โ ๐ด1 (โ๐ฟ ยท ๐ผ + ๐ฟ ยท ๐ผ)โ = 0. Using the parameters ๐ and ๐ the
transition
(๏ธ )๏ธ (๏ธ in question)๏ธ (๏ธ is)๏ธcomputed
(๏ธ )๏ธby:(๏ธ
๐ฟ โ ๐ผโ ๐ผ๐ฟ โ
)๏ธ (๏ธ ๐ฟ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ข ๐ผ ๐พ ๐ ๐ฟ ๐ผ ๐พ โ๐ผโ ๐๐๐
โ = โ = = .
๐ฃ โ๐ผ ๐ฟ ๐ โ๐ฟ โ๐ผ ๐ฟ 0 โ๐ฟ + ๐ผโ ๐ผ๐ฟ โ โ๐๐๐
Finally we conclude ๐๐๐ = ๐ฟ โ ๐ผโ ๐ผ๐ฟ โ = ๐ฟ ๐๐๐ ๐ผ. If ๐ is regular then ๐ผ = ๐ฝ โง ๐ฝ|๐ฟ implies
๐๐๐ = ๐ฟ ๐๐๐ ๐ผ = 0. Applying the rule ๐
2 from Definition 10 up to a ๐ฟ-reduced cycloid, from
arbitrary ๐ฟ we obtain ๐ฟ < ๐ผ and ๐๐๐ = ๐ฟ ๐๐๐ ๐ผ = ๐ฟ. (๏ธ )๏ธ (๏ธ )๏ธ
0 ๐
b) Similar to case a) from the definition of ๐๐๐ we obtain โฒ โก
โฒ which is by Theorem
๐ฬ๏ธ โ๐
โ๐(๐พ + ๐ฟ) โ ๐พ ยท ๐ฬ๏ธโฒ
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ฟ โ๐พ โ๐
2.1 equivalent to Z โ ๐ด2 1
= ๐ด 1
. The second row
๐ผ ๐ผ ๐ฬ๏ธโฒ + ๐ ๐ผ ยท ๐ฬ๏ธโฒ
of this formula gives the solution ๐ฬ๏ธโฒ = ๐พ + ๐ฟ. Using this result from the first row we obtain
โ(๐+๐พ)ยท(๐พ+๐ฟ)
Z โ โ1 ๐ด (๐(๐พ +๐ฟ)+๐พ ยท(๐พ +๐ฟ)) = ๐ผยท(๐พ+๐ฟ) = โ(๐+๐พ) ๐ผ with a solution ๐ = โ๐พ. Therefore ๐กโ๐พ,๐พ
is a transition of the form ๐ก๐,โ๐ as mentioned in Definition 11. However the condition 0 โค ๐ < ๐ผ
may not be fulfilled as the transition may lie outside the fundamental parallelogram. To find the
(unique) equivalent transition inside the fundamental parallelogram we apply Theorem 2.6. With
(๐ข, ๐ฃ) = (โ๐พ, ๐พ) and ๐ด = ๐ผ ยท (๐พ + ๐ฟ) we obtain ๐ = โ ๐ด1 (๐ข ยท ๐ฟ โ ๐ฃ ยท ๐พ)โ = โ โ๐พยท(๐พ+๐ฟ) โ๐พ
๐ผยท(๐พ+๐ฟ) โ = โ ๐ผ โ
and ๐ = โ ๐ด1 (๐ฃ ยท ๐ผ + ๐ข ยท ๐ฝ)โ = โ ๐ด1 (๐พ ยท ๐ผ โ ๐พ ยท ๐ผ)โ = 0. Using the parameters ๐ and ๐ the
transition in question is computed by:
110
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
โ๐พ โ ๐ผโ โ๐พ
)๏ธ (๏ธ โ๐พ )๏ธ
๐๐๐โฒ
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ข ๐ผ ๐พ ๐ โ๐พ ๐ผ ๐พ โ๐ผโ ๐ผ โ
โ = โ = =
๐ฃ โ๐ผ ๐ฟ ๐ ๐พ โ๐ผ ๐ฟ 0 ๐พ + ๐ผโ โ๐พ
๐ผ โ
โ๐๐๐โฒ
{๏ธ
โโ๐ฅโ if ๐ฅ โ Z
and ๐๐๐โฒ = โ๐พ โ ๐ผโ โ๐พ ๐ผ โ. Using โโ๐ฅโ = we obtain for ๐ผ| ๐พ (when ๐ is
โโ๐ฅโ โ 1 if ๐ฅ โ /Z
co-regular) ๐๐๐โฒ = โ๐พ +๐ผยท ๐ผ๐พ = 0. If ๐ผ| ๐พ does not hold we obtain ๐๐๐โฒ = โ๐พ โ๐ผยท(โโ ๐ผ๐พ โโ1) =
โ(๐พ โ ๐ผ ยท โ ๐ผ๐พ โ) + ๐ผ = ๐ผ โ ๐พ ๐๐๐ ๐ผ.
4. Cycloid Isomorphisms and Reduction Equivalence
A net isomorphism between two cycloids (Definition 1) does not necessarily preserve forward
or backward places. To preserve these properties we define the notion of a cycloid isomorphism.
Definition 12. Given two cycloids ๐1 = ๐1 (๐ผ1 , ๐ฝ1 , ๐พ1 , ๐ฟ1 ) = (๐1 , ๐1 , ๐น1 ) and ๐2 =
๐2 (๐ผ2 , ๐ฝ2 , ๐พ2 , ๐ฟ2 ) = (๐2 , ๐2 , ๐น2 ) a mapping ๐ : ๐1 โ ๐2 (๐๐ = ๐๐ โช ๐๐ , ๐๐ = ๐๐โ โช ๐๐โ ) is a
cycloid morphism if
๐ (๐น1 โฉ (๐1โ ร ๐1 )) โ (๐น2 โฉ (๐2โ ร ๐2 )) โช ๐๐ and
๐ (๐น1 โฉ (๐1โ ร ๐1 )) โ (๐น2 โฉ (๐2โ ร ๐2 )) โช ๐๐ and
๐ (๐น1 โฉ (๐1 ร ๐1โ )) โ (๐น2 โฉ (๐2 ร ๐2โ )) โช ๐๐ and
๐ (๐น1 โฉ (๐1 ร ๐1โ )) โ (๐น2 โฉ (๐2 ร ๐2โ )) โช ๐๐.
๐ is an isomorphism if ๐ is a bijection and the inverse ๐ โ1 is a also a morphism Then, ๐1 and ๐2
are called cycloid isomorphic denoted ๐1 โcyc ๐2 . If ๐1 and ๐2 are cycloid systems with initial
markings ๐01 and ๐02 , respectively, then the definition of a cycloid isomorphism is extended by
๐ (๐1โ โฉ ๐01 ) = ๐2โ โฉ ๐02 and ๐ (๐1โ โฉ ๐01 ) = ๐2โ โฉ ๐02 .
Lemma 3. The cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) of Theorem 2.2 is cycloid isomorphic to the transformed
cycloids.
Proof. In the proof of Theorem 2.2 only properties of the Petri space are used. Therefore it
proves that these transformations are invariant with respect to cycloid isomorphism.
Theorem 4.1. Two cycloid systems ๐1 and ๐2 are cycloid isomorphic (Definition 12) if and only
if they are ๐พ๐ฟ-reduction equivalent (Definition 6):
๐1 โcyc ๐2 โ ๐1 โ๐พ๐ฟ ๐2 .
Proof. If ๐1 and ๐2 are cycloid isomorphic then they have the same values of ๐ผ and ๐ฝ by Lemma
2: |๐ (๐1โ โฉ ๐01 )| = |๐2โ โฉ ๐02 | = ๐ฝ and |๐ (๐1โ โฉ ๐01 )| = |๐2โ โฉ ๐02 | = ๐ผ.
Case a) ๐ผ ฬธ= ๐ฝ: ๐1 and ๐2 have the same values of ๐ด, ๐๐ฆ๐ and we compute ๐พ, ๐ฟ by Theorem 2.5.
As proved in [5], all solutions are ๐พ๐ฟ-equivalent. A unique value is obtained by the ๐พ-reduced
equivalent in the case ๐ผ โค ๐ฝ and the ๐ฟ-reduced equivalent in the case ๐ผ > ๐ฝ.
Case b) ๐ผ = ๐ฝ: If ๐1 and ๐2 are cycloid isomorphic then inclinations ๐๐๐ are equal and their
areas ๐ด are identical. Using Theorem 3.2 ๐ฟ, ๐พ are computed ๐๐๐๐ข๐๐ ๐ผ and by ๐ผ-reduction we
obtain a unique result.
Conversely, if ๐1 and ๐2 are reduction equivalent, by Lemma 3 they are cycloid isomorphic.
To illustrate the case ๐ผ ฬธ= ๐ฝ in the proof of the theorem consider the cycloid net system
๐(5, 3, 2, 6, ๐0 ) of Figure 8. We find ๐ฝ = 3 since ๐ โ = {s1f, s24f, s36f} has three elements
111
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
and ๐ผ = 5 since there are 5 marked backward places. Using the Synthesis Theorem 2.5 we
calculate ๐พ ๐๐๐ 5 = 5โ3 1
ยท (5 ยท 8 โ 36) = 2 with a solution ๐พ = 2 and ๐ฟ = 15 ยท (36 โ 3 ยท 2) = 6.
For the case ๐ผ = ๐ฝ consider the cycloid systems ๐1 = ๐(3, 3, 1, 8, ๐01 ) and ๐2 =
๐(3, 3, 7, 2, ๐02 ) in Figure 6 both with ๐๐๐ = 2. From ๐ฟ ๐๐๐ 3 = 2 we obtain ๐ฟ = 2, 5, 8
and with ๐ด = ๐ผ๐ฟ + ๐ฝ๐พ also ๐พ = 7, 4, 1. All further such steps result in not positive values.
Figure 6: Cycloid systems with ๐ผ = ๐ฝ for illustrating Theorem 4.1.
5. Reduction of Cycloids without initial marking
In this section we investigate cycloid nets without initial marking in order to find suitable
parameters ๐ผ, ๐ฝ, ๐พ, ๐ฟ. Therefore we consider a transformation of the first two parameters.
Theorem 5.1. The following cycloids are cycloid isomorphic (Definition 12) to ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ):
a) ๐(๐ผ + ๐พ, ๐ฝ โ ๐ฟ, ๐พ, ๐ฟ) if ๐ฝ > ๐ฟ,
b) ๐(๐ผ โ ๐พ, ๐ฝ + ๐ฟ, ๐พ, ๐ฟ) if ๐ผ > ๐พ.
Proof. Let be (๏ธ ๐ฟ) with matrix A (Definition 3), ๐1 = ๐1 (๐ผ ยฑ ๐พ, ๐ฝ โ ๐ฟ, ๐พ, ๐ฟ) with
๐ = ๐(๐ผ, ๐ฝ, ๐พ, )๏ธ
๐ผยฑ๐พ ๐พ
matrix A1 = and the vector โโ := (๐, ๐) โ Z2 . By Theorem 2.1 with respect
๐๐
โ(๐ฝ โ ๐ฟ) ๐ฟ
112
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
(๏ธ )๏ธ
โโ โโ ๐ ยท ๐ผ + (๐ ยฑ ๐) ยท ๐พ
to ๐1 we obtain: โ๐ฅ1 โก โ๐ฅ2 โ โ ๐๐ โ Z : ๐ฅโ2 โ ๐ฅโ1 = A1 ยท ๐๐ =
2 =
โ๐ ยท ๐ฝ + (๐ ยฑ ๐) ยท ๐ฟ
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ผ ๐พ ๐ ๐
= Aยท . Hence, the equivalence relations of ๐ and ๐1 are the
โ๐ฝ ๐ฟ ๐ยฑ๐ ๐ยฑ๐
same.
Similar to Theorem 2.2 the transformations of Theorem 5.1 correspond to a shearing. While
the invariant edge of the fundamental parallelogram is the edge between ๐ and ๐ it is called
๐-๐-shearing to distinguish it from the shearing of Figure 4, which is a ๐-๐ -shearing by the
use of this terminology. An example of such a ๐-๐-shearing is given in Figure 7. To give
Figure 7: A ๐-๐-shearing with ๐(2, 3, 6, 2) to ๐(8, 1, 6, 2).
an example for a transformation which does not preserve isomorphism, consider the cycloids
๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) and ๐(๐พ, ๐ฟ, ๐ผ, ๐ฝ). Obviously they have the same area, but are not isomorphic in
general. For instance the cycloids ๐(3, 1, 1, 1) and ๐(1, 1, 3, 1) have the same area ๐ด = 4, but
different minimal cycle length 2 and 4, respectively. To prepare an algorithm for computing the
parameters ๐ผ, ๐ฝ, ๐พ, ๐ฟ of a cycloid net as in Figure 8, now ignoring the initial marking, we give a
formula for the interval of the ๐-axis belonging to the fundamental parallelogram.
113
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 8: A cycloid net of the cycloid system ๐(5, 3, 2, 6, ๐0 ).
Lemma 4. For a cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) the interval of the ๐-axis within the fundamental parallelo-
๐ด
gram extends from the origin ๐ก0,0 up to ๐ก๐๐๐๐ฅ ,0 where ๐๐๐๐ฅ = โ ๐๐๐ฅ(๐ฝ,๐ฟ) โ โ 1.
Proof. The condition
(๏ธ )๏ธ for(๏ธa )๏ธ transition(๏ธ ๐ก)๏ธ๐,0 to lie(๏ธwithin
)๏ธ the
(๏ธ fundamental
)๏ธ parallelogram is by
๐ ๐ ๐ ๐ 0
Theorem 2.6: = โA or A = with ๐ = โ ๐ด1 (๐ข๐ฟ โ ๐ฃ๐พ)โ =
0 0 ๐ ๐ 0
โ ๐ด1 (๐ ยท ๐ฟ โ 0 ยท ๐พ)โ = โ ๐ยท๐ฟ
๐ด โ and ๐ = โ ๐ด
1
(๐ฃ๐ผ + ๐ข๐ฝ)โ = โ ๐ด1 (0 ยท ๐ผ + ๐ ยท ๐ฝ)โ = โ ๐ยท๐ฝ ๐ด โ. This
๐ผ ยท โ ๐ยท๐ฟ ๐ยท๐ฝ
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ โ + ๐พ ยท โ โ 0
gives A = ๐ด ๐ด = . From the first row we obtain โ ๐ยท๐ฟ
๐ด โ = 0 and
๐ โ๐ฝ ยท โ ๐ยท๐ฟ
๐ด โ + ๐ฟ ยท โ ๐ยท๐ฝ
๐ด โ 0
โ ๐ยท๐ฝ
๐ด โ = 0 which satisfies also the second row. The overall condition is therefore ๐ < ๐ฟ โง ๐ < ๐ฝ
๐ด ๐ด
or ๐ < ๐๐๐ฅ(๐ฝ,๐ฟ)
๐ด
. The largest integer satisfying this condition is ๐๐๐๐ฅ = โ ๐๐๐ฅ(๐ฝ,๐ฟ) ๐ด
โ 1โ =
๐ด
โ ๐๐๐ฅ(๐ฝ,๐ฟ) โ โ 1.
A more geometric way to obtain this result starts with the observation that ๐๐๐๐ฅ is the largest
integer value on the ๐-axis before the intersection of the ๐-axis with the lines containing ๐, ๐
114
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
or ๐, ๐
of the fundamental parallelogram. The line containing ๐ and ๐
is given by the equation
๐ = โ ๐ผ๐ฝ (๐ โ ๐พ) + ๐ฟ (see [5]). Setting ๐ = 0 gives ๐ = ๐ด๐ฝ . The line containing ๐ and ๐
is given
by the equation ๐ = ๐พ (๐ โ ๐ผ) โ ๐ฝ. Again, setting ๐ = 0 gives ๐ = ๐ด๐ฟ . Therefore we obtain
๐ฟ
the overall condition ๐ < ๐ด๐ฟ โง ๐ < ๐ด ๐ฝ and proceed as in the proof before. For the cycloid
๐(4, 2, 2, 3) of Figure 3 b) we obtain ๐ด = 16 and ๐๐๐๐ฅ = โ ๐๐๐ฅ(2,3)
16
โ1โ = โ 16 13
3 โ1โ = โ 3 โ = 5.
As can be seen in the figure, the ๐-axis overlaps with the fundamental parallelogram in the
transitions from ๐ก0,0 to ๐ก5,0 . The values of ๐๐๐๐ฅ for the cycloids of Figure 7 are 7 and 10.
โ
Lemma 5. For a cycloid ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) the output transition of ๐กโ
0,0 is ๐ก๐ผ,1โ๐ฝ .
โ
Proof. For any cycloid the output transition ๐ก0,1 of ๐กโ 0,0 is not contained in the fundamental
parallelogram. Again, we calculate(๏ธthe)๏ธequivalent โ๐ฅ of ๐ก0,1 within the fundamental parallelogram
๐
using Theorem 2.6: โ๐ฅ = โ๐ข โ A where โ๐ข = (๐ข, ๐ฃ) = (0, 1) and ๐ = โ ๐ด1 (๐ข๐ฟ โ ๐ฃ๐พ)โ =
๐
โ ๐ด1 (0 ยท ๐ฟ โ 1 ยท ๐พ)โ = โ โ๐พ โ = โ1 and ๐ = โ ๐ด1 (๐ฃ๐ผ + ๐ข๐ฝ)โ = โ ๐ด1 (1 ยท ๐ผ + 0 ยท ๐ฝ)โ = โ ๐ด ๐ผ
โ = 0.
(๏ธ๐ด )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
0 ๐ผ ๐พ โ1 0 โ๐ผ ๐ผ
Hence we obtain โ๐ฅ = โ = โ = .
1 โ๐ฝ ๐ฟ 0 1 ๐ฝ 1โ๐ฝ
Also, this result is obtained in a more geometric way as follows. The position of the output
โ
transition of ๐กโ
0,0 in the fundamental parallelogram is one step from ๐ in direction of the ๐-axis:
๐ + (0, 1) = (๐ผ, โ๐ฝ) + (0, 1) = (๐ผ, 1 โ ๐ฝ). Similar to Definition 10 a reduction rule is defined
using Theorem 5.1.
Definition 13. For cycloids ๐1 (๐ผ1 , ๐ฝ1 , ๐พ1 , ๐ฟ1 ) and ๐2 (๐ผ2 , ๐ฝ2 , ๐พ2 , ๐ฟ2 ) the following conditional
reduction rule is defined:
R3: ๐ผ2 = ๐ผ1 + ๐พ1 , ๐ฝ2 = ๐ฝ1 โ ๐ฟ1 , ๐พ2 = ๐พ1 and ๐ฟ2 = ๐ฟ1 if ๐ฝ1 > ๐ฟ1 .
If this rule cannot be applied the cycloid is said to be ๐ฝ-reduced. If a cycloid ๐1 can be obtained
from a cycloid ๐2 by iterated applications of the transformations in Theorem 5.1 they are called
๐ผ๐ฝ-reduction equivalent, denoted ๐1 โ๐ผ๐ฝ ๐2 . They are called reduction equivalent, denoted
๐1 โ๐๐๐ ๐2 , if the transformations of both, Theorem 5.1 and Theorem 2.2, are used.
Theorem 5.2. For a cycloid-net ๐1 (where the parameters ๐ผ, ๐ฝ, ๐พ, ๐ฟ are not known) a ๐ฝ-reduced
cycloid ๐2 = ๐(๐ผ2 , ๐ฝ2 , ๐พ2 , ๐ฟ2 ) can be computed which is cycloid isomorphic to ๐1 . The parameters
๐ผ3 , ๐ฝ3 of each cycloid, which is ๐ผ๐ฝ-equivalent to ๐2 , is represented by cut points of forward and
backward cycles of in the graph of ๐1 .
Proof. Let be ๐1 = ๐(๐ผ, ๐ฝ, ๐พ, ๐ฟ) a cycloid and ๐ก๐0 ,๐0 , ๐ก๐1 ,๐1 , ๐ก๐2 ,๐2 , ยท ยท ยท a backward cycle (Defi-
nition 7) starting in ๐ก๐0 ,๐0 = ๐ก0,0 . By Lemma 5 the second element is ๐ก๐1 ,๐1 = ๐ก๐ผ,1โ๐ฝ . Since
1 โ ๐ฝ โค 0 then follow elements ๐ก๐ผ,2โ๐ฝ , ๐ก๐ผ,3โ๐ฝ , ยท ยท ยท until the ๐-axis in the Petri space is reached
in a transition ๐ก๐ผ,๐๐ with ๐๐ = 0 and ๐ = ๐ฝ. The ๐-axis in the Petri space, however, is folded
to the forward cycle in the fundamental parallelogram and there may be different meeting
points of the backward an forward cycle, both started in ๐ก0,0 (for instance ๐ก10,โ1 and ๐ก10,โ2 in
the cycloid ๐(10, 3, 2, 2) of Figure 9). We make the choice to select the transition ๐ก๐๐ ,๐๐ of the
backward cycle meeting the forward cycle with minimal ๐ (๐ก10,โ2 in the cycloid ๐(10, 3, 2, 2)
of Figure 9). Thus we obtain ๐ฝ2 = ๐ and ๐ผ2 = ๐ (๐ฝ2 = 1 in ๐(10, 3, 2, 2) and ๐ผ2 = 12 since the
115
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
Figure 9: Fundamental parallelograms of ๐(10, 3, 2, 2) and ๐(12, 1, 2, 2).
initial section of the forward cycle is ๐ก0,0 , ๐ก1,0 , ยท ยท ยท , ๐ก8,0 , ๐ก7,โ2 , ๐ก8,โ2 , ๐ก9,โ2 , ๐ก10,โ2 having length
12 without counting ๐ก0,0 and the ๐ฝ-reduced cycloid ๐(12, 1, 2, 2) is obtained.).
๐พ2 and ๐ฟ2 are computed in a similar way, since (๏ธ the)๏ธinput(๏ธtransition
)๏ธ of the backward input
๐พ2 0
place of ๐ก0,0 is ๐ก๐พ2 ,๐ฟ2 โ1 , which is proved by โก by Theorem 2.1 again: ๐ด1 ยท
๐ฟ2 โ 1 โ1
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ (๏ธ )๏ธ
๐ฟ2 โ๐พ2 ๐พ2 ๐ฟ2 ยท ๐พ2 โ ๐พ2 ยท ๐ฟ2 0
ยท =๐ดยท 1
= โ Z2 .
๐ฝ2 ๐ผ2 ๐ฟ2 ๐ฝ2 ยท ๐พ2 + ๐ผ2 ยท ๐ฟ2 1
In ๐1 we use the forward cycle from ๐ก0,0 again. Then we look for the first transition ๐ก๐,0 on this
forward cycle, when going from ๐ก0,0 backwards on the backward cycle of length ๐ (not counting
๐ก0,0 ). Then ๐พ2 = ๐ and ๐ + 1 = ๐ฟ2 .
If the cycloid ๐2 is ๐ฝ-reduced (๐ฝ โค ๐ฟ) then in the construction of ๐ผ2 and ๐ฝ2 above, the meeting
point ๐ก๐๐ ,๐๐ is on the ๐-axis within the fundamental parallelogram. This holds if ๐๐๐๐ฅ โฅ ๐ผ
which is proved as follows: using ๐ฝยท๐พ ๐ฝยท๐พ
๐ฟ > 0 โ โ๐ผ + ๐ฟ โ โฅ ๐ผ + 1 and Lemma 4 we deduce
๐ผยท๐ฟ+๐ฝยท๐พ ๐ฝยท๐พ
๐ด
๐๐๐๐ฅ = โ ๐๐๐ฅ(๐ฝ,๐ฟ) โ โ 1 = โ ๐ฟ โ โ 1 = โ๐ผ + ๐ฟ โ โ 1 โฅ ๐ผ + 1 โ 1. (See the ๐ฝ-reduced
equivalent ๐(12, 1, 2, 2) of ๐(10, 3, 2, 2) in Figure 9.)
Having found all ๐ฝ-reduced cycloid ๐2 we now show how to find the ๐ผ๐ฝ-equivalent cycloids
116
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
from the graph of the cycloid net of ๐1 . To this end we prove that within the fundamental
parallelogram for any ๐ โ N by going ๐ ยท ๐พ2 steps backwards on the forward cycle from ๐ก๐ผ2 ,0 the
transition ๐ก๐ผ2 โ๐ยท๐พ2 ,0 on the ๐-axis is equivalent to the transition ๐ก๐ผ2 ,๐ยท๐ฟ(๏ธ2 going)๏ธ๐ยท๐ฟ(๏ธ
2 steps forward )๏ธ
๐ผ2 ๐ผ2 โ ๐ ยท ๐พ2
from ๐ก๐ผ2 ,0 on the backward cycle. This is proved by the equivalence: โก .
๐ยท๐ฟ 0
(๏ธ )๏ธ (๏ธ )๏ธ (๏ธ 2 )๏ธ (๏ธ )๏ธ
๐ผ2 ๐ผ2 โ ๐ ยท ๐พ2 ๐ฟ โ๐พ2 ๐ ยท ๐พ2
By Theorem 2.1 we obtain ๐ด1 ยท B ยท ( โ ) = ๐ด1 ยท 2 ยท =
๐ ยท ๐ฟ2 0 ๐ฝ2 ๐ผ2 ๐ ยท ๐ฟ2
(๏ธ )๏ธ (๏ธ )๏ธ
๐ฟ2 ยท ๐ ยท ๐พ2 โ ๐พ2 ยท ๐ ยท ๐ฟ2 0
1
๐ด ยท ๐ฝ ยท๐ยท๐พ +๐ผ ยท๐ยท๐ฟ = โ Z2 . The subset of these intersection points with
2 2 2 2 ๐
๐ผ2 โ๐ยท๐พ2 > 0 correspond to the first two parameters in the cycloids ๐(๐ผ2 โ๐ยท๐พ2 , ๐ฝ2 +๐ยท๐ฟ2 , ๐พ2 , ๐ฟ2 )
with ๐ผ2 โ ๐ ยท ๐พ2 > 0 which are ๐ฝ-equivalent to the ๐ฝ-reduced form ๐2 (๐ผ2 , ๐ผ2 , ๐พ2 , ๐ฟ2 ). Observe
that starting from the ๐ฝ-reduced cycloid ๐2 we went to the ๐ผ๐ฝ-equivalent versions of the cycloid.
In this proof we started with the origin ๐ก0,0 of the fundamental parallelogram. If this transition
is not known in the cycloid net, by the symmetry of the cycloid, a randomly selected transition
can be chosen instead.
As example for the procedure, as described in the proof of Theorem 5.2, consider the randomly
selected transition ๐ก๐0 ,๐0 = t7 in the cycloid net of Figure 8 (ignoring the initial marking). Then
by following the forward places we construct the forward cycle of length ๐ = 12 starting in this
transition: t7 t8 t9 t10 t11 t12 t1 t2 t3 t4 t5 t6. The backward cycle t7 t32 t22 t12 t25 . . . t17
of length ๐โฒ = 36 also starting in t7 is meeting the forward cycle for the first time in t12. The
length of the section from t7 to t12 is ๐ผ2 = 5 in the forward cycle and ๐ฝ2 = 3 in the backward
cycle (by not counting the initial element t7 in both cases). To compute ๐พ2 and ๐ฟ2 , starting
again in ๐ก7 we are going backwards on the backward cycle t7 t17 t27 t2 t24 t34 t9 of length
๐ฟ2 = 6 where the forward cycle is met. The length of the latter from t7 to t9 is ๐พ = 2 (without
counting t7 in both cases). From the intersection points we select one where the section of the
forward cycle is minimal, i.e. not ๐ก2 in the example. In summary, have calculated the ๐ฝ-reduced
cycloid ๐2 = ๐(5, 3, 2, 6).
Next we attach the count labels of the path sections to the reached transitions. Above, for
the transition t12 the label is [5, 3] corresponding to ๐(5, 3, 2, 6). Going from t12 a number of
๐พ = 2 steps backwards on the forward cycle and ๐ฟ = 6 steps forwards on the backwards cycle
we reach transition t10 with label [3, 9], corresponding to ๐(3, 9, 2, 6). Doing the same again
we come to t8 with label [1, 15], corresponding to ๐(1, 15, 2, 6). A further such step leads to
negative values. In this way, from the net we have deduced all ๐ผ๐ฝ-equivalent cycloids of the
๐ฝ-reduced cycloid ๐2 = ๐(5, 3, 2, 6).
Corollary 1. Two cycloids ๐๐ = ๐๐ (๐ผ๐ , ๐ฝ๐ , ๐พ๐ , ๐ฟ๐ ), ๐ โ {1, 2} are cycloid isomorphic (Definition
12) if and only if they are reduction equivalent (Definition 13): ๐1 โcyc ๐2 โ ๐1 โ๐๐๐ ๐2 .
Proof. If ๐1 and ๐2 are cycloid isomorphic by Theorem 5.2 the cycloids ๐1โฒ and ๐2โฒ are constructed
which are ๐ฝ-reduced and cycloid isomorphic to both cycloids. They have the same values of ๐ผ
and ๐ฝ. If ๐ผ ฬธ= ๐ฝ we compute the ๐พ or ๐ฟ-reduced equivalent to obtain the same values for ๐พ and
๐ฟ by Theorem 3.1. If ๐ผ = ๐ฝ Theorem 11 is used, instead. Conversely, if ๐1 โ๐๐๐ ๐2 then they
are cycloid-isomorphic by Lemma 3 and Theorem 5.1.
117
Rรผdiger Valk et al. CEUR Workshop Proceedings 99โ118
6. Conclusion
The theory of cycloids is extended by the technique of reduction. It allows for easier compu-
tation of properties like the minimal length of cycles and the cycloid parameters ๐ผ, ๐ฝ, ๐พ and
๐ฟ. Reductions can be used to prove cycloid isomorphism which considerably improves the
complexity of the problem of testing for cycloid isomorphism. As a byproduct new insights in
structural properties of cycloids are gained.
References
[1] C. A. Petri, Nets, Time and Space, Theoretical Computer Science (153) (1996) 3โ48.
doi:10.1016/0304-3975(95)00116-6.
[2] R. Valk, On the Two Worlds of Carl Adam Petriโs Nets, in: W. Reisig, G. Rozenberg
(Eds.), Carl Adam Petri: Ideas, Personality, Impact, Springer, Cham, 2019, pp. 37โ44.
doi:10.1007/978-3-319-96154-5.
[3] O. Kummer, M.-O. Stehr, Petriโs Axioms of Concurrency - a Selection of Recent Results,
in: Application and Theory of Petri Nets 1997, volume 1248 of Lecture Notes in Computer
Science, Springer-Verlag, Berlin, 1997, pp. 195 โ 214. doi:10.1007/3-540-63139-9_37.
[4] U. Fenske, Petris Zykloide und รberlegungen zur Verallgemeinerung, Diploma Thesis,
Dep. of Informatics, Univ. Hamburg, 2008.
[5] R. Valk, Formal Properties of Petriโs Cycloid Systems, Fundamenta Informaticae 169 (2019)
85โ121. doi:10.3233/FI-2019-1840.
[6] B. Jessen, D. Moldt, Some Simple Extensions of Petriโs Cycloids, in: M. Kรถhler-Bussmeier,
E. Kindler, H. Rรถlke (Eds.), PNSE 2020 Petri Nets and Software Engineering, CEUR Work-
shop Proceedings, http://ceur-ws.org/Vol-2651/paper13.pdf, 2020, pp. 194โ212.
[7] R. Valk, Circular Traffic Queues and Petriโs Cycloids, in: Application and Theory of Petri
Nets and Concurrency, volume 12152 of Lecture Notes in Computer Science, Springer-Verlag,
Cham, 2020, pp. 176 โ 195. doi:10.1007/978-3-030-51831-8.
[8] E. Smith, W. Reisig, The semantics of a net is a net โ an exercise in general net theory, in:
K. Voss, J. Genrich, G. Rozenberg (Eds.), Concurrency and Nets, Springer-Verlag, Berlin,
1987, pp. 461โ479. doi:10.1007/978-3-642-72822-8_29.
[9] C. A. Petri, R. Valk, On the Physical Basics of Information Flow - Results obtained in cooper-
ation Konrad Zuse, 2008. URL: https://www2.informatik.uni-hamburg.de/TGI/mitarbeiter/
profs/petri/Xian_Petri_Valk.pdf.
[10] R. Valk, Deciphering the Co-car Anomaly of Circular Traffic Queues using Petri Nets,
in: Application and Theory of Petri Nets and Concurrency, volume 12734 of Lecture
Notes in Computer Science, Springer-Verlag, Cham, 2021, pp. 443 โ 462. doi:10.1007/
978-3-030-76983-3.
[11] R. Valk, On the Structure of Cycloids Indroduced by Carl Adam Petri, in: Application and
Theory of Petri Nets and Concurrency, volume 10877 of Lecture Notes in Computer Science,
Springer-Verlag, Cham, 2018, pp. 294 โ 314. doi:10.1007/978-3-319-91268-4_15.
118