Vol-3170/paper6
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3170/paper6 |
| wikidataid | Q117351502→Q117351502 |
| title | On Reduction of Cycloids |
| pdfUrl | https://ceur-ws.org/Vol-3170/paper6.pdf |
| dblpUrl | https://dblp.org/rec/conf/apn/ValkM22 |
| volume | Vol-3170→Vol-3170 |
| session | → |
On Reduction of Cycloids
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
�