Cycloids are particular Petri nets for modelling processes of actions and events, belonging to the fundaments 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.
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 trafic 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 trafic queue
when folded together. To give an example, Figure 1a) shows three such sequential circular
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
(, , , ) = (
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 < ≤ .
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 nonEuclidian 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 trafic item (the token in the left input-place) in both space and time 1With the condition ∙ ∩ = ∅ we follow Petri’s definition, but with no impacts in this article. direction. It is enabled by a gap or co-item (the token in the right input-place), which is enabling a next trafic 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 forward 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 trafic queues.
We assume that our model of a circular trafic 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
) = (
Definition 4. a) The net = (, , ) from Definition 3 (without explicitly giving the parame) is called the underlying net of the cycloid. It is a -net with |∙ | = |∙ | = 1 for all 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 ← the letter f and b, respectively. Note that the parameters are not visible in this representation, are labelled by 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 ) a degenerate cycloid when also the additional restriction > 0 for the area = 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 ︂(
± )︂ − ∓ a) (, , b) (, , − , + , − ) if > .
+ ) if > ,
Since constructions of cycloids may result in diferent 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 (, , , ): Proof. Let be = (, , ,
) with matrix A (Definition 3) and the vector →− := (, ) ∈ Z2.
By Theorem 2.1 with the matrix A1 = of 1 = 1(, , ± , ∓ ) we obtain 2The net is generated by the Automatic Net Layout of the RENEW tool.
3The algorithm is implemented under http://cycloids.de/home. (, , ,
+ useful.
holds. area and B = ⃗2 − ⃗1 = A ︂(
For proving the equivalence of two points in the Petri space the following procedure3 is Theorem 2.1 ([7]). Two points ⃗1, ⃗2 ∈ 1 are equivalent ⃗1 ≡ diference ⃗ := ⃗2 − ⃗1 the parameter vector (⃗) = 1 · B · ⃗ has integer values, where is the ⃗2 if and only if for the . Also, in analogy to Definition 3 we obtain ⃗1 ≡ ⃗2 ⇔ ∃ , ∈ Z : A1 · →− = A · →− + A · ︂( ± )︂ . Hence, the equivalence relations of and 1 are the same. ︂( ± )︂ 0
=
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
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 Figure 5 4
for the cycloids (
+ )︂ − 5The figure has been designed using the tool http://cycloids.adventas.de. 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 applications of the transformations given in Theorem 2.2 then they are called -reduction equivalent, denoted 1 ≃
2.
Lemma 1 ([5]). For any cycloid (, , , its fundamental parallelogram representation.
) there is a minimal cycle containing the origin in formal. = + + ︂{
⌊ ⌋( − )
−⌊ ⌋( − ) if >
if ≤
For the next Theorem from [5], we give a proof which follows the same concept, but is more Theorem 2.3 ([5]). The length of a minimal cycle of a cycloid (, , , ) is (, , , ) = The length of a minimal cycle of a degenerate cycloid with ≤ is also if > 0 and > 0. parallelogram and by Lemma 1 it is suficient to consider paths starting in the origin Proof. a) We first consider the case ≤ . With respect to paths and cycles in the fundamental . 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 ≥ when going steps in direction − ). More precisely, for any ≥ 0, ≥ 0 we have to prove 0 is not violated ) under the condition − ≥ 0. This follows from ≤ (, (, ︂( )︂ ) ≥ ) Again, since points (, ) with < 0 are not reachable, we obtain the condition b) For the alternative case we look at the cycloid (, , ,
length of this cycle is + + ⌊ ⌋ · ( − ) , which finishes the proof in this case. + · (− ) ≥ 0, which is ≤ . Hence, the maximal integer value for is = ⌊ ⌋. The ) (by interchanging and , as theorem. c) For the case of a degenerate cycloid we refer to [5]. 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 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).
6An elementary cycle is a cycle where all nodes are diferent. Theorem 2.4 ([10]). In a cycloid (, , ,
= (, ) and length of a backward-cycle is ′ = (, ) ) with area the length of a forward-cycle is . The cycloid contains (, ) backward cycle. disjoint forward-cycles and (,
) disjoint backward cycles. With respect to the standard initial marking (Definition 9) the number of tokens in a forward cycle is
(, ) and (, ) in a
For the cycloids (
A cycloid = (, , , consists of a number backward-cycles (called co-processes) of length = . forward-cycles (called processes) of length = . is called is co-regular if divides . Then it ) is regular if divides . It consists of a number
The cycloid (
) we define a cycloid system (, , , , 0) or Definition 9 ([5]). For a cycloid (, , , (, 0) by adding the standard initial marking: 0 = {→, {←, ∈ 1← |
∈ 1→ | + ≤ +
≤ 0 ∧ 0 ∧ ( + 1) + >
+ ( + 1) > 0} /≡ . |0 ∩ →| = and |0 ∩ ← | = .
Lemma 2 ([5]). Given a cycloid system (, , , , 0} /≡ ∪ 0) with standard initial marking 0 then
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 determine and . In this paper, however, we use Lemma 2, instead. := |{| |∙ ∩ 0| = 2 }| is the number of initially active transitions. They are used to Theorem 2.5 (Synthesis Theorem [5]). Cycloid systems with identical system parameters 0, , and are called -. Given a cycloid system (, , , , sentation (, , , 0) where the parameters 0, , and are known (but the parameters ′ = and for ′, ′ by some positive integer solution of the following formulas using these setare not). Then a - cycloid ( ′, ′, ′, ′) can be computed by ′ = 0, 0) in its net repretings of ′ and ′: a) case ′ > ′: ′ ′ = ′· − and ′ = 1′ ( − ′ · ′),
′− ′ b) case ′ < ′: ′ ′ = ′· ′−− ′ and ′ = 1′ ( − ′ · ′), c) case ′ = ′: ′ = ⌈ 2 ⌉ and ′ = ⌊ 2 ⌋.
These equations may result in diferent 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 ( + )⌋.
Following Theorem 2.2 we introduce two reduction rules for cycloids keeping them isomorphic.
reduction rules are defined:
For cycloids 1( 1, 1, 1, 1) and 2( 2, 2, 2, 2) the following conditional = . applied the cycloid system = (, , , ,
0) is called -reduced. If is -reduced and < If this rule cannot be applied the cycloid system (, , , , (resp. = ) then is called strongly -reduced (resp. weakly -reduced).
R2: 2 = 1, 2 = 1, 2 = 1 + 1 and 2 = 1 − 1 if 1 > 1. reduced and < (resp. = ) then is called strongly -reduced (resp. weakly -reduced).
0) is called -reduced. If is
In some cases for reduced cycloids the cycloid parameters and can be directly deduced from the parameters and and the properties and . cycle length , := − 1 · ( · − ) and := − 1 · ( − · ).
Theorem 3.1. Let be = (, , ,
) a cycloid with known values ̸= , area , minimal 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 obtain = + . With the formula for we have the equation ︂( )︂ = ︂( 1 1︂) (︂ )︂ 7The algorithm is implemented under http://cycloids.de/home. to compute the solution − 1 ︂( · − )︂ − · + = ︂( )︂ . If = in item b) then we make another step in the = 0 + . The case for > is similar.
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
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 = − 1 · ( − · ) = 2. Diferent to Theorem 3.1 the next result is not a special case of 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, · · · in (3, 3, 1, 8, 01) from Figure 6. A forward cycle of such a cycloid contains one of these , − 1,− ( − 1), for instance the transitions 0,0 = t1, 1,− 1 = t19, 2,− 2 = t10 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 ≤ < .
time, say ,− . tion 7) starting in the origin 0,0 contains one of the transitions {,− |0 ≤ < } for the first Let (, , , ) be a cycloid with = . A forward or backward cycle (Definia) 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 b) With respect to the backward cycle the backward inclination of the cycloid is defined by this in, − 1}. In this case, the path from 0,0 to ,− is called pseudo-co-process denoted by .
̃︀ dex ′ := ∈ {0, · · · and its length is denoted by ′.
Theorem 3.2. Let = (, , ,
̃︀ − . Moreover, ̃︀′ = + .
Proof. a) From the definition of we obtain
1 to Z2 ∋
︂( gives the solution = − )︂ (︂ ̃︀ ̃︀ − ︂)
1 = · ( + ) ︂(
︂) 0̃︀ ≡ ︂( (̃︀ − ) − ︂( )︂ − · )︂ · ̃︀ which is by Theorem 2.1 equivalent . The second row of this formula transition in question is computed by: of the form ,− as mentioned in Definition 11. However the condition − ) − · ) = ( − )· ( + ) = − with a solution = . Therefore , − is a transition · ( + ) <
may 0 ≤ 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 + . Using this result from the first row we obtain Z ∋ 1 ( ( + = = ︂( )︂ −
.
∧ | implies which is by Theorem ︂( ︂( Finally we conclude = − ⌊ ⌋ = . If is regular then = = 0. Applying the rule 2 from Definition 10 up to a -reduced cycloid, from ) be a cycloid with = . a) The forward inclination exists and has the values = process length (Definition 8). -reduced form (Definition 10) then = and if is regular then = 0 and ̃︀ = for the b) The backward inclination ′ exists and has the value ′ = 0 if is co-regular, else ′ = ̃︀ and = + . If is transition in question is computed by:
̃︀ of this formula gives the solution ′ =
+ . Using this result from the first row we obtain is a transition of the form ,− as mentioned in Definition 11. However the condition Z ∋ − 1 (( + )+ · ( + )) = − (+ )· ( + ) = − (+ ) with a solution = − . Therefore − , · ( + ) 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 arbitrary we obtain < and = = . b) Similar to case a) from the definition of ′ we obtain 2.1 equivalent to Z2 1
︂( ∋ − )︂ (︂
− )︂ ̃︀ ′ + ︂( 0 )︂ ′ ≡ ̃︀ ︂( )︂
− · ̃︀′ = 1 − ( + ) − · ̃︀′)︂ . The second row ︂( − ︂( and ′ = − − ⌊ − ⌋. Using ⌊− ⌋ = ︂( if ∈ Z we obtain for | (when is − ( − · ⌊ ⌋
) + = − . co-regular) ′ = − + · = 0. If | does not hold we obtain ′ = − − · (−⌊ ⌋− 1) =
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. cycloid morphism if
Given two cycloids 1 = 1( 1, 1, 1, 1) = (1, 1, 1) and 2 = (1→ ∩ 01) = 2→ ∩ 02 and (1← ∩ 01) = 2← ∩ 02. 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 cycloids.
Lemma 3. The cycloid (, , ,
) of Theorem 2.2 is cycloid isomorphic to the transformed 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. if they are -reduction equivalent (Definition 6): Theorem 4.1. Two cycloid systems 1 and 2 are cycloid isomorphic (Definition 12) if and only 1 ≃cyc 2 ⇔ 1 ≃ 2. 2: | (1→ ∩ 01)| = |2→ ∩ 02| = and | (1← ∩ 01)| = |2← ∩ 02| = .
Case a) ̸= : 1 and 2 have the same values of , and we compute , Proof. If 1 and 2 are cycloid isomorphic then they have the same values of and by Lemma 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) areas are identical. Using Theorem 3.2 ,
are computed and by -reduction we = : If 1 and 2 are cycloid isomorphic then inclinations are equal and their 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 and
= 5 since there are 5 marked backward places. Using the Synthesis Theorem 2.5 we (3, 3, 7, 2, 02) in Figure 6 both with = 2. From 3 = 2 we obtain
For the case calculate 5 = 5− 1 3 · (5 · 8 − 36) = 2 with a solution = 2 and = 15 · (36 − 3 · 2) = 6. = consider the cycloid systems 1 = (3, 3, 1, 8, 01) and 2 = = 2, 5, 8 and with = +
also = 7, 4, 1. All further such steps result in not positive values.
In this section we investigate cycloid nets without initial marking in order to find suitable
. Therefore we consider a transformation of the first two parameters.
Theorem 5.1. The following cycloids are cycloid isomorphic (Definition 12) to (, , , ): Proof. Let be = (, , , ) with matrix A (Definition 3), 1 = 1( ± , ∓ , , ) with and the vector →− := (, ) ∈ Z2. By Theorem 2.1 with respect to 1 we obtain: ⃗1 ≡ ⃗2 ⇔ ∃ →− ∈ Z2 : ⃗2 − ⃗1 = A1 · →− = . Hence, the equivalence relations of and 1 are the ︂( · + ( ± ) · )︂ − · + ( ± ) · =
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 an example for a transformation which does not preserve isomorphism, consider the cycloids
). Obviously they have the same area, but are not isomorphic in
general. For instance the cycloids (
2 and 4, respectively. To prepare an algorithm for computing the
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.
Lemma 4. For a cycloid (, , , gram extends from the origin 0,0 up to ,0 where = ⌈ (, ) ⌉ − 1.
) the interval of the -axis within the fundamental paralleloProof. The condition for a transition , 0 to lie within the fundamental parallelogram is by Theorem 2.6: =
A or A = ︂( · ⌊ · ⌋ + · ⌊ · ⌋
︂) − · ⌊ · ⌋ + · ⌊ · ⌋ ⌊ 1 ( · − gives A
or <
⌈ (, ) ⌉ − 1. ⌊ · ⌋ = 0 which satisfies also the second row. The overall condition is therefore < ∧ < (, ) . The largest integer satisfying this condition is = ⌈ (, ) − 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 ,
0 + )⌋ = ⌊ 1 (0 · + · )⌋ = ⌊ · ⌋. This ︂( 0)︂ . From the first row we obtain ⌊ · ⌋ = 0 and 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 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 ⃗ = (, ) = (
Hence we obtain ⃗ =
+ (
reduction rule is defined:
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:
− ) + (
− ). Similar to Definition 10 a reduction rule is defined
For cycloids 1( 1, 1, 1, 1) and 2( 2, 2, 2, 2) the following conditional R3: 2 = 1 + 1, 2 = 1 − 1, 2 = 1 and 2 = 1 if 1 > 1. 1 ≃ 2, if the transformations of both, Theorem 5.1 and Theorem 2.2, are used. 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 Theorem 5.2. For a cycloid-net 1 (where the parameters , , , cycloid 2 = ( 2, 2, 2, 2) can be computed which is cycloid isomorphic to 1. The parameters are not known) a -reduced -equivalent to 2, is represented by cut points of forward and 3, 3 of each cycloid, which is backward cycles of in the graph of 1.
Proof. Let be 1 = (, , ,
) a cycloid and 0, 0
, 1, 1
, 2, 2 , · · ·
nition 7) starting in 0, 0 = 0,0. By Lemma 5 the second element is 1, 1 = , 1− . Since
a backward cycle
(Defi1
− ≤
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 diferent meeting
points of the backward an forward cycle, both started in 0,0 (for instance 10,− 1 and 10,− 2 in
the cycloid (
2 and 2 are computed in a similar way, since the input transition of the backward input place of 0,0 is 2, 2− 1, which is proved by by Theorem 2.1 again: 1 · 2
2 ︂( 2 − 2)︂ (︂ 2)︂ · 2 = 1 · (︂ 2 · 2 − 2 · 2 )︂
2 · 2 + 2 · 2 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 (
Having found all -reduced cycloid 2 we now show how to find the -equivalent cycloids 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 from 2,0 on the backward cycle. This is proved by the equivalence: ︂( 2
︂) · 2 ≡ ︂( 2 − · 2)︂ .
0 By Theorem 2.1 we obtain 1 · B · ( 1 · ︂( 2 · · 2 − 2 · · 2 )︂ 2 · · 2 + 2 · · 2 = ︂( 2
︂) · 2 − = ∈ Z2. The subset of these intersection points with 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 2we went to the
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 -equivalent versions of the cycloid. 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 = (
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 (
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. are cycloid-isomorphic by Lemma 3 and Theorem 5.1.
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
The theory of cycloids is extended by the technique of reduction. It allows for easier computation 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.