Decomposition of complex systems into smaller, independent modules is a fundamental approach for reducing complexity. The computation of structural invariants, a common method for verification, is aided by this modular reduction in complexity. However, while T-invariants can be combined from the module's local T-invariants and local P-invariants are preserved, synchronization between modules introduces new P-invariants. Current algorithms do not consider these modular structures of the P/T nets for the calculations of P-invariants. The incidence matrix of modular Petri nets, in which interactions between modules are restricted to only transitions, has a singly-bordered block diagonal (SBBD) structure. This structure may lead to speedups in reducing the matrix to row echelon form, the main challenge in the computation of invariants. In this paper, we examine the specific properties of modular nets that facilitate these speedups. We present an algorithm for the reduction through Gaussian elimination. Through its analysis, we find that module size, number of external transitions and synchronized firing groups, and number of linearly independent internal transitions highly influence the runtime of our algorithm. Our algorithm performs better than the naive Gaussian elimination for good modularized nets. The conditions leading to speed-ups naturally serve as formalizations of coupling and cohesion.
Design of complex and interacting systems was and still is a challenge. Modeling a system with specific perspectives is one way to address this. The divide-and-conquer principle has a long tradition in informatics, following far older sciences.
Parts of such decomposable systems are related in a specific way to specify the relationship. Parnas
names such parts modules (see [
Fettke and Reisig use the notion of modules as their basic modeling entities [
In [
Here we pick up the central ideas of modules to add some formal aspects to the models that can be created in the above contexts. One of the traditional concepts, invariants, are used to link modules. Calculation of invariants for very large Petri net models is dificult due to the algorithmic complexity resulting in long calculation times.
Based on the ideas of nets-within-nets [
The following sections show the related work of the abovementioned topic Section 2 and the formal background of the paper Section 3. Requirements for the paper are presented in Section 4. Then, our algorithm for reducing a modular net’s incidence matrix to row echelon form is given and explained in Section 5. In Section 6, an example run of the algorithm follows to give further illustration of its behavior, while the formal analysis is done in Section 7. Based on the findings in this analysis, we formally define notions of coupling and cohesion in Section 8 that naturally lead to formulating the modularization of P/T nets as the problem of permuting matrices into bordered block diagonal form. Then, we discuss our findings in Section 10 and conclude with Section 11.
By dividing complex systems into diferent parts that exhibit significant internal behavior in comparison
to the external interactions between each other, their subsequent analysis can be facilitated. Such a
modular approach is realized in the context of Petri nets in the form of formal models as modular nets.
In [
In [
In [
However, these papers only state in rough terms how the specifics of the modular structure actually aid in subsequent analysis. Especially, formal definitions of such measures of modularity could be of interest. The commonly used concepts of coupling and cohesion serve to describe the quality of modular systems and could also do so for modular nets.
In [
In [
Approaches to give specific measures of coupling and cohesion in accordance with this framework
include definitions based on information-theoretic principles [
In the context of Petri nets, formal measures were given in [
Gaussian Elimination is an algorithm for solving systems of linear equations [
The algorithm eliminates all leading leftmost non-zero entries in each row but one, by adding
multiples of the topmost row to the other rows, so that the given entry is zero. The rows are always
sorted so that the number of leading zeros in each row is increasing. By iterating through these steps
until there are no more than one leading non-zero entries per column, the matrix will be in row echelon
form [
A matrix is in row echelon form when all rows containing only zeros are at the bottom and every
leading non-zero entry is on the right of the leading non-zero entry of the row above. This implies that
all entries under a leading coeficient are zeros [
For a given × matrix , the number of leading non-zero entries in its row echelon form is
referred to as the rank of . It is denoted as rank() and always lies between 0 and min(, ). Notably,
rank() = rank(T) and rank() = 0 if and only if only consists of zeros [
A matrix is in doubly bordered block diagonal form if it resembles this form: ⎛11 ⎜ = ⎜⎜ ⎜ ⎝
22 1 2 ...
...
1 ⎞
2 ⎟
... ⎟⎟
⎠⎟
(1)
The blocks are matrices with the dimensions × . The border blocks and have a dimension
of × and × , respectively, where ideally should be significantly smaller than [
A singly bordered block diagonal matrix is a special arrangement of entries in a matrix: Algorithm 1 Gaussian Elimination to row echelon form ◁ Move to the next column ⎛11 = ⎜⎜ ⎝ 22 ...
1 ⎞
2 ⎟
... ⎠⎟
(2)
The blocks are matrices with the dimensions × . The border blocks have a dimension of
× , where ideally should be significantly smaller than [
Synchronous channels allow the linking of transitions which are part of the same net, or diferent
nets. A transition which is part of a synchronous channel can either be a Uplink or a Downlink. In
Renew synchronous channels are defined with inscriptions. These inscriptions are either :<Channel
Name>(<Parameters>) for Uplinks or <Net-reference>:<Channel Name>(<Parameters>) for
Downlinks, as can be seen in Figure 1. Using the net-reference a synchronous channel can access another net
with the same channel. Using the parameters variables can be passed through the channel. A transition
can have multiple Downlinks, but only one Uplink [
The basic idea behind the various diferent models for describing modular P/T nets [
The formal model serving as the basis for this paper will be the Ptc-system net [
The P/T-net modules ∈ themselves are P/T nets with a designated set of external transitions , which are each assigned a channel from and potential assignments for variables . Further, they allow variables to be used as arc weights. The synchronization rules are multisets over and allow multisets of external transitions to fire if their channels sum to any such synchronization rule. At the same time, the variable assignment functions and ensure that all relevant variables are assigned a valid value. A multiset of external transitions that is allowed to fire in this way is called a synchronized ifring group , and the set of all firing groups is called .
In figure 2, a simple example for a Ptc-system net is given in Renew. It consists of a producer and a consumer that are connected by a shared storage. All three are each a module in the Ptcsystem net, whose synchronization rules are expressed by the transitions t2 and t3. The variable assignments are performed implicitly by the synchronous channels in Renew. The synchronization rule {produce, store} allows the firing group {tp1, ts0} to fire while assigning a value of 3. Similarly, {retrieve, consume} allows {ts1, tc1} to fire while assigning a value of 2.
The change a synchronized firing group afects on specific places can then be expressed similarly to the arc weight function, leading to ̃︁ : ( × ) ∪ ( × ) → N 0. ̃︁(, ) describes how the marking of a place is decreased if a firing group fires, and ̃︁(, ) describes how it increases.
Together with the arc weight functions of all modules , aggregated into a single function ̃︁ with extended domain to include all places and transitions, the incidence matrix of a Ptc-system net can be succinctly described. To better diferentiate between internal and external components, the internal incidence matrix and the synchronized incidence matrix are introduced in addition to the global
The global incidence matrix can be formed with the internal incidence matrix and the synchronized incidence matrix . The resulting matrix is a singly bordered block diagonal matrix as described above. The rows and columns are sorted by the modules .
∆ =
⎜ 0 ︀( )︀ = ⎜⎜⎜ ...
⎛ 1 Definition 2. The synchronized incidence matrix considers the efects of synchronized transition sets. A synchronized incidence matrix exists for each module, in which the efects of the synchronized transition sets on the places of the modules are observed.
,pg = ∆() =
̃︁sync(, ) − ̃︁sync(, )
,pg = ∆() =
̃︁sync(, ) − ̃︁sync(, ),
for ∈
Definition 3. The global incidence matrix ∆ results from the efects of the transition and synchronized
transition sets from the PTC-System Net.
incidence matrix ∆ [
Definition 1. The internal incidence matrix results from the efect of the internal transitions. Each module has an internal incidence matrix, which is calculated independently from the other modules. The entries of the internal incidence matrices aren’t necessarily integers, because the external transition can include variables on their arc weights. These are only relevant if the whole net is considered.
As a foundation for discussing coupling and cohesion in modular systems we will use the formal
definitions given in [
Intuitively, the coupling of a module describes how many relationships exist between it and other modules. The coupling of a modular system describes how many relationships exist between all its modules. Formally, the coupling of a module or modular system is a function coupling() or coupling( ) characterized by the following properties: 1–23 (11) (15) (16) (17)
Cohesion is non-negative and normalized:
cohesion() ∈ [
The cohesion is 0 if the set of intra-module relationships in a module () or in a modular system () is empty:
= ∅ ⇒ cohesion() = 0, = ∅ ⇒ cohesion( ) = 0
Adding intra-module relationships does not decrease cohesion. Let ′ be a module that results from a module by adding intra-module relationships so that ⊆ ′ , and let ′ be a modular system that results from a modular system containing by replacing with ′. Then: coupling() ≥ 0, coupling( ) ≥ 0 (10)
The coupling is 0 if the set of inter-module relationships in a module () or in a modular system () is empty:
= ∅ ⇒ coupling() = 0, = ∅ ⇒ coupling( ) = 0
Adding inter-module relationships does not decrease coupling. Let ′ be a module that results from a module by adding inter-module relationships so that ⊆ ′ , and let ′ be a modular system that results from a modular system containing by replacing with ′. Then: coupling() ≤ coupling( ′), coupling( ) ≤ coupling( ′) (12)
Merging two modules together does not increase coupling. Let 1, 2 be two modules, let ′ be the union of 1 and 2, and let ′ be a modular system that results from a modular system containing 1, 2 by replacing both with ′. Then: coupling(1) + coupling(2) ≥ coupling( ′), coupling( ) ≥ coupling( ′) (13)
In the case of two unrelated modules being merged, the coupling remains unchanged. If there are no relationships between 1 and 2, then: coupling(1) + coupling(2) = coupling(′), coupling( ) = coupling( ′) (14)
Intuitively, the cohesion of a module describes how well the elements of the module are grouped together. The cohesion of a modular system acts as a comprehensive measure for the cohesion of all its modules. Formally, the cohesion of a module or modular system is a function cohesion() or cohesion( ) characterized by the following properties:
Coupling is non-negative: cohesion() ≤ cohesion( ′), cohesion( ) ≤ cohesion( ′)
Merging together unrelated modules does not increase cohesion. Let 1, 2 be two modules that have no relationships between them, i.e., 1 ∩ 2 = ∅, let ′ be the union of 1 and 2, and let ′ be a modular system that results from a modular system containing 1, 2 by replacing both with ′. Then: max(cohesion(1), cohesion(2)) ≥ cohesion( ′), cohesion( ) ≥ cohesion( ′)
Given the incidence matrix ∆
of a P/T net, the net’s T-invariants are solutions of the homogenous linear system ∆ = 0 and the P-invariants are solutions of ∆ is based on solving a linear system = 0.
T = 0. The computation of invariants
This is done through two steps. First, the matrix is reduced to row echelon form ̃︀. Then, the
reduced linear system ̃︀ = 0 is solved through backward substitution. Between these two steps, it is
the reduction to row echelon form that is more computationally expensive [
Further, for modular nets with synchronous channels, the net’s T-invariants can be combined from
local T-invariants through their coupling components [
In this section we describe an algorithm for reducing an incidence matrix ∆ T to row echelon form. We will first give an overview of the entire algorithm. Then, by dividing the algorithm into three phases, we will describe each part in more detail. Since we only consider the transposed incidence matrix, we will refer to the transpose matrices without the superscript T from this point forward, keeping notation simple. So, for example, instead of ∆ T, T, T, we will just call them ∆, , .
Reduction of the incidence matrix ∆
can be divided into two parts. Firstly, the reduction of its block diagonal part , where care is taken to ensure properties that aid in the following part. And secondly, reduction of the block border part , using the already reduced .
is in SBBD form: The modular Gaussian elimination, given in Algorithm 2, takes an incidence matrix ∆ consisting of an internal incidence matrix and a synchronized incidence matrix . As is a block diagonal matrix, ∆ (18) (19) ∆ = ⎛ 1 ⎜⎜ 0 2 0 . .
. · · · · · · . . .
. 0 0
⎞
As the blocks in are independent of each other, the main challenge in reducing ∆ is introduced by the interactions between modules contained in . First, this independence is completely utilized This is done by using rows from the just reduced to avoid interactions between modules. However, in general, such an isolated approach doesn’t sufice so that some entries in remain. Finally, these remaining entries are eliminated in Phase 3. This requires using rows from itself so that interactions between modules are unavoidable. As a last step, simple row permutations are performed so that a proper row echelon form is achieved.
Algorithm 2 Reduction of ∆ to row echelon form 2: Output: The matrix ∆ ̃i︀n row echelon form 3: procedure Modular Gaussian Elimination() 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: for all ∈ [1, ] do end for // Phase 1: Reduction of block diagonal matrix = diag( 1, 2, . . . , )
Transform to row echelon form ̃︀
Move leading entries to the main diagonal by swapping columns // Phase 2: Initial reduction of synchronization border for all ∈ [1, ] do for all ∈ [1, rank( ̃︀)] do
Use row of ̃︀ to eliminate all entries in column of forming ′ end for end for ︃(
)︃ ̃︀ ̃︀ // Phase 3: Final reduction of synchronization border Eliminate remaining entries in ′ transforming it to row echelon form ̃︀ Rearrange rows in
to get row echelon form ∆ ̃︀ 18: end procedure
Due to the block diagonal structure of , each of its blocks can be considered in isolation. We reduce each individual block into row echelon form through Gaussian. Then, the resulting matrix is transformed through column permutations to ensure that each leading entry lies along the main diagonal. We will call the thusly transformed matrix ̃︀.
The same column permutations are also performed on , keeping the columns between both parts of ∆ consistent. Since these permutations are a simple rearrangement of the columns of , we won’t introduce a specific designator and will keep referring to it as .
The permutations performed on each are illustrated by taking matrix in row echelon form as an example. The leading entries in rows 3 and 4 do not lie on the main diagonal but are located in columns 5 and 7, respectively. To achieve the desired structure, columns 3 and 5 are swapped, as well as columns 4 and 7. The resulting matrix ̃︀ now has all its leading entries along its main diagonal. Having reduced every block to ̃︀ in this way, we get the reduced ̃︀ as a block diagonal matrix →− with all individual reduced blocks along its diagonal: ̃︀=
̃︁1 ⎛ ⎜⎜ 0 ⎜⎜⎝ ...
0 0 ̃︁2 . .
. · · · 0 · · · . . . . . .
0
⎞ · · · 0 · · · . . . . . .
0
⎞ Note that ̃︀ is only almost in row echelon form as it may contain rows with all entries equal to zero not located at the bottom of the matrix. This is due to the zero rows of a diagonal block being located higher than the entries of the following blocks. The following matrix illustrates this for the case = 2 with two 3 × 2 submatrices: These zero rows could be permuted to the bottom of the block diagonal matrix to achieve a proper row echelon form. This form is, in a sense, equivalent to row echelon form with respect to simple row permutations. Therefore, this form of reduction sufices to continue with the subsequent phase.
After the reduction of , the incidence matrix ∆ has been transformed to: (23) (24) While the blocks were entirely independent of each other, the same does not apply to , which relates to the synchronization between modules. However, by using ̃︀ for eliminating entries in , the corresponding row additions only afect the columns of module . In this way, independence between modules can be further exploited.
Due to the construction of ̃︀, all its leading entries lie along its main diagonal and the rest of the main diagonal is filled with zeros. Therefore, the number of these entries is equal to the rank of the matrix rank( ̃︀). Each corresponding row allows elimination of all entries in located in the same column as the leading entry. Through these eliminations, is transformed into ′ in which the first rank( ̃︀) columns’ entries are all equal to zero.
︂( ̃︀
︂) = ⎜
⎞ ⎛
* * * * * ⎜ ⎜0 * * * * ⎟ ⎜⎜0 0 * * * ⎟⎟
⎟ ⎜ ⎜0 0 0 0 0⎟ ⎜0 0 0 0 0⎟ ⎜* * * * * ⎟⎟ ⎜ ⎜ ⎝* * * * * ⎠⎟ ⎟ ⎟ ︂( ̃︀
︂) ′ = ⎜
⎞ ⎛
* * * * * ⎜ ⎜0 * * * * ⎟ ⎜⎜0 0 * * * ⎟⎟
⎟ ⎜
In the context of modular P/T nets, this process can be further simplified. The rows in are the efects of the synchronized firing groups, which result from the combined efects of the participating external transitions. If the entry for a specific column has been eliminated for each external transition, meaning that it is then equal to 0, any way of combining such transitions will always yield an efect with that specific entry also being equal to 0. Therefore, it sufices to reduce just these external transitions for each module.
If the elimination in Phase 2 is done on the external transitions instead of the synchronized firing groups, in which all variables already have a unique value assigned to them, the question arises how to handle variables. One approach would be to just leave them as is and to perform the elimination steps through symbolic computations. However, such computations are inherently more expensive than numerical computations and, further, could make additional entries depend on the specific value of the variable.
Indicating against the unconstrained use of variables is the fact that all external transitions of a module can be replaced by a single transition if assigning negative values is permissible. This is illustrated in Figure 3, where assignments of and with 1 and 3, 2 and 1, and 1 and 0 allow emulating each of the three replaced transitions. It would then be unreasonable to expect that a problem of any size could be reduced to just a constant size.
However, due to only partial reductions being performed in Phase 2, variables can be efectively hidden from the numerical computations being performed. If a variable of a module is located in one of the last || − rank( ̃︀) columns, i.e., a column whose entries won’t be eliminated in Phase 2, then the symbolic value of its entry at the end of the phase will be equal to the variable itself plus some numerical value. As such, the variable can simply be treated as 0 during computations, and only in the instantiation of the synchronized firing groups for Phase 3 will the variable be assigned its value. The computed numerical value then simply serves as an ofset in this assignment.
In the case that ̃︀ has rank lower than its number of columns, some entries in remain, as exemplified in Equation (24). These entries require rows in itself to be used for elimination. However, such rows are not contained to any specific module but instead include nonzero entries in columns belonging to modules that participate in the synchronized firing group represented by that row.
Without presupposing anything about anything about the specific external transitions and participation of modules in synchronizations, all entries not yet eliminated could potentially be a nonzero entry. As such, each block ′ consists of some initial zero columns followed by the remaining columns filled with arbitrary entries. The following matrix exemplifies this structure for ′: ⎛* * ⎜* * ︀) = ⎜⎜* * ′ = (︀ 1′ 2′ 3′ · · · ′ ⎜ ⎝* * * * 0 0 * 0 0 * 0 0 * 0 0 * 0 0 * ′ is then reduced to row echelon form by Gaussian elimination, transforming it into ̃︀ . Every row of ̃︀ that was used to eliminate entries in the rows below it will contain entries that can’t be further eliminated. When considering ∆ in its entirety, it is therefore not yet in row echelon form. However, by either swapping these rows with zero rows of the ̃︀ , which columns its leading entry belongs to, or by inserting it below ̃︀if no such zero row exists, full row echelon form of ∆ is achieved.
As an example to illustrate how the algorithm works, we will consider the modular net in Figure 4. It consists of 4 modules that are synchronized by two synchronization rules, resulting in 4 possible synchronized firing groups. The net’s modular structure results in the following incidence matrix ∆: The dashed lines indicate the individual modules, with vertical lines separating the places and horizontal lines separating the internal transitions. The solid line divides ∆ into the internal incidence matrix in the upper half and the synchronized incidence matrix in the lower half.
The modules are arranged in natural reading order. For example, the first block contains the internal incidence matrix 1 of the upper left module. It consists of the efect of its internal transition t1 as the ifrst row and the efect of t2 as the second row. Notably, the third module doesn’t contain any internal transitions so that its internal incidence matrix is empty.
The first and second rows in both result from the synchronization rule {, , }. Multiple external transitions inscribed with the channel existing, one in the upper right and the other in the lower left module, lead to a choice in synchronization. Consequently, two diferent synchronized firing groups 1 0 0 0 0 0 0 0 1 0 0 ︃( ︃( 0 2 0 0 0 0 0 0 0 1–23 (27) (28) (29) (30) (31) similarly based on the choice regarding channel .
In Phase 1 of the algorithm, each individual block is reduced: are possible. In the first row, the transition from the upper right module is chosen, and in the second row, the transition from the lower left. The third and fourth rows, resulting from {, , , }, behave 1 = ︂( 2 − 2 1 doing this for every synchronized firing group, it sufices to do so for every external transition, as the
Then, in Phase 2, each reduced ̃︀ is used to eliminate entries in the corresponding . Instead of former are composed of the latter.
︂( ̃︁1︂)
1 →− inserted in ̃:︀ partially reduced ′. Finally, ′ is reduced to ̃︀in Phase 3: Together, ̃︀ and ̃︀ are then almost in row echelon form so that the rows of ̃︀ simply have to be As can be seen, due to (̃︁1) = 2 being smaller than |1| = 3, a row with a nonzero entry in the third column remains in ̃︀ , requiring insertion. At the same time, ̃︁1 having more columns than rows means that there is space below it in regard to the row echelon form. This space, then, allows the row from ̃︀to be inserted as the third row.
With (̃︁2) = 1 < |2| = 2, the same applies, resulting in the second row of ̃︀ being inserted below ̃︁2. In this case, a zero row has to be swapped to the bottom of the entire matrix in return.
While (̃︁3) = 0 < |3| = 1 implies that there is a third row in ̃︀ to be expected, this row happened to be eliminated in the process of reducing ′ to ̃︀ . This fact also means that an invariant exists in the whole modular net. Specifically, backward substitution yields the following P-invariant: ︀( 1 −
In this section, we will shortly justify that Algorithm 2 works and terminates correctly. Then, we will analyse the runtime of each of the algorithm’s phases before giving a combined overview. 1–23
The Algorithm 2 works mostly like normal Gaussian elimination by using elementary row operations. It deviates by changing the order in which entries are eliminated and by performing column permutations in Phase 1.
The change in order results from performing operations in the outlined phases instead of simply going row by row. However, this order serves to describe the algorithm more clearly and to ensure constraints on the row permutations performed. These constraints do not limit the correctness of the elimination, as they do not prevent the choice of pivot elements if no other alternatives exist. Such a choice is just postponed to Phase 3.
Using column permutation is unproblematic, as it does not interfere with the row permutations necessary for selecting pivot elements. Further, they correspond to changing the order of variables in the linear system. When subsequently solving the linear system, the column permutations simply have to be performed in reverse order on the solution vectors to get the correct arrangements of variables.
Overall, therefore, the correctness and termination of Algorithm 2 follow directly from that of the Gaussian elimination.
When only considering the internal elements of the individual modules, it is to be expected that computations involving the entire modular net can be reduced to addressing each module individually. Just that is what we find for the reduction of the block diagonal matrix to row echelon form. Each block is reduced separately so that the runtime of reducing doesn’t depend on the modular net’s size as a whole but on the individual sizes of its modules.
Since the algorithm doesn’t depend on the specific method used for reducing each to row echelon
form, we simply assume it to be an arbitrary runtime (||, ||) depending on the corresponding
module’s number of places and transitions. In the simplest case, this would be Gaussian elimination
with (||, ||) = ︀( max(||, ||) min(||, ||)2)︀ [
Even though the sum of maximum terms can be higher than the maximum of the entire net, i.e., ∑︀=1 max(||, ||) ≥ max(| |, | |) , in terms of time complexity, the more influential minimum terms are lower, i.e., ∑︀
=1 min(||, ||) ≤ min(| |, | |) . It follows then that modules that deviate strongly from being square matrices are beneficial for the block diagonal matrix reduction. In the following, it is therefore justified to assume = || = || and let = 1 + 2 + · · · + . Expressing the runtime as a polynomial with ≥ 2 leads to the following inequality:
∑︁ = ⎝ =1 ⎛︃( ∑︁|| =1 )︃ 1 ⎞ ⎠ = (‖(1, 2, · · · , )‖) ≤ (‖( 1, 2, · · · , )‖1) = ︃( ∑︁|| =1 )︃
= (34)
The inequality follows from the relations between diferent -norms, where ‖‖ ≤ ‖‖ for all
1 ≤ ≤ < ∞ [
However, in terms of asymptotic runtime, the size of the largest module dominates. This leads to the ifrst condition for good modularization, requiring modules to all be of roughly the same size so that ≈ /. In that case, the overall runtime simplifies to: ︃(
)︃ ∑︁ ≈ ( ) = ︁( (1−) )︁ =1 Consequently, if the number of modules grows with the overall size of the system, a better asymptotic runtime is achieved. For naive Gaussian elimination, where = 3, this translates to an improvement by a factor of 12 . The realistic best case is achieved if the modules are of constant size so that ∈ (). Irrespective of the actual algorithm used as a subroutine, the block diagonal matrix would then be reduced to row echelon form in time ().
Beyond these runtime improvements, it is notable that the reduction of the individual blocks is fully parallelizable and that modules with the same incidence matrix only require the reduction to be computed once instead of for each of those modules.
adding a multiple of a row with || − number of operations in the order of In total, the reduction of to ′ involves the elimination of all entries in the first rank( ̃︀) columns in for each . And for each column, the number of entries to be eliminated is equal to the number of rows in , which is equal to ||. Each elimination of an entry in using the -th row from ̃︀ involves entries. Consequently, the reduction in its entirety requires a ︃( ∑︁ rank( ̃︀)|||| =1 ∑︁ rank( ̃︀)|||| )︃ )︃ (35) (36) (37) (38) (39)
However, because each elimination step only afects the entries in , its rows contain duplicate entries if external transitions participate in more than just one synchronization each. Therefore, instead of ||, the efective number of rows becomes | | and the runtime is reduced to
In both cases, the runtime depends on the size of the modules by way of the number of their respective matrix. For modules of roughly the same size (|| ≈ | |/), the runtime simplifies to: places. Note that rank( ̃︀) also depends on this notion of size as it can only take on values from 1 to ||. Therefore, the same considerations concerning module size apply here as for the block diagonal ︃(
=1 ∑︁ rank( ̃︀)|||| ≈ )︃ 2 ||| |2 ∑︁ rank( ̃︀) )︃ 1
|| =1 by 1, leading to the following simplification:
Because rank( ̃︀) can only take on values from 1 to ||, the summands can be upwardly bounded ︃( 1 2 ||| |2 ∑︁ 1 =1 )︃ = ︂( 1 ||| |2 ︂)
It follows then that for modules of constant size ( ∈ (| |)), the reduction of to ′ is performed in time (||| |). Just as for the block diagonal matrix, this reduction is fully parallelizable, and modules that have the same external transitions in addition to having the same internal incidence matrix don’t require separate computations.
Through the initial reduction, from the original || columns in ′, rank( ̃︀) have had all their entries eliminated. Excluding columns with only zeros, the efective number of columns is therefore: = ∑︁(|| − rank( ̃︀)) = | | − rank( ̃︀) = | | − rank()
=1
Consequently, ′ is efectively a || × matrix. As was the case for the blocks in , the subsequent reduction of ′ can be performed by any algorithm for reducing matrices to row echelon. In the case of naive Gaussian elimination, this leads to the following runtime:
︀( max(, ||) min(, ||)2)︀
This means that these computations, in contrast to the previous ones, cannot be considered as independent computations for each module. The runtime of the entire algorithm is therefore dominated by the reduction from ′ to ̃︀ . What is gained by the previous two reductions is therefore an efective reduction in rows and columns. The overall | ∖ | + || rows were reduced to just the || rows corresponding to the interactions between modules, and the | | columns were reduced to just a fraction depending on the rank of the internal incidence matrix.
Both Phase 1 and Phase 2 make use of the modular structure in such a way that their runtimes are significantly improved if the modular net is divided into modules of appropriate size. Additionally, Phase 2 is influenced by the size of the interfaces between modules, measured by || or more specifically by ||. On the other hand, Phase 3 doesn’t benefit in the same way so that its runtime grows asymptotically the most with the overall size of the modular net. Besides the number of places, the runtime also increases with the size of the interfaces between modules ||. To some degree these costly elimination steps, which involve the coupling components between modules, can be alleviated by work done in Phase 2, exploiting the independence between modules. The extent of this improvement results from the rank of the internal incidence matrix rank().
These measures directly influence the overall runtime, and as such, they serve as indicators for how the modularity of a given modular net aids in its analysis. In this sense, they determine whether a modular net has good or bad modularity.
The runtime analysis in Section 7 yielded formal expressions for assessing the modularity of a modular P/T net. We aim to put these indicators into the proper context by classifying what kind of measures they are. Specifically, we will express them as measures for coupling and cohesion.
However, we will first reconsider the underlying framework for describing the modular system. In
[
While such an approach can most definitely be taken [
|| coh( ) = () | | The cohesion of a Ptc-system net is equal to the number of internal transitions, whose efect vectors are linearly independent, divided by the number of all places:
In this case, the relation between the rank of the internal incidence matrix and what would be expected of a cohesion measure isn’t as direct as for the coupling measures. Therefore, we will show that the expected properties as outlined in Section 3.5 are indeed satisfied.
As the rank of a matrix is non-negative and bounded by the minimum between the number of rows and the number of columns, coh is non-negative and normalized: The coupling of a Ptc-system net is equal to the number of its synchronized firing groups: cou() = |{ ∈ | ∃ ∈ : ∈ }|
cou( ) = ||
Each synchronized firing group of a Ptc-system net corresponds to a transition in its equivalent P/T
net connecting places belonging to multiple modules [
As performing the reduction in Phase 2 leads to the runtime given in Equation (37), it depends on the number of external transitions || instead of ||. Therefore, another measure of coupling based on the Ptc-system net’s external transitions arises naturally.
Definition 5. The coupling of a P/T net module is equal to the number of its external transitions, and the coupling of a Ptc-system net is equal to the number of its external transitions: coue() = | |,
coue( ) = ||
The external transitions directly relate to the synchronized firing groups and, therefore, to the inter-module relationships . Again, it follows that coue does indeed satisfy the required properties.
Finally, the extent to which entries in ′ can be eliminated in Phase 2 instead of Phase 3 captures an important aspect of modularity in Ptc-system nets. Indeed, the expression of the remaining columns given in Equation (40) leads to the following measure of cohesion based on the rank of the internal incidence matrix.
Definition 6. The cohesion of a P/T net module is equal to the number of internal transitions, whose efect vectors are linearly independent, divided by the number of its places: other transitions are inter-module relationships. With this basis, we can now formally define coupling and cohesion.
Both the runtime of Phase 2, as given in Equation (36), and Phase 3, given in Equation (41), depend on the number of synchronized firing groups ||. On this basis, we formulate the first definition of coupling.
Definition 4. The coupling of a P/T net module is equal to the number of synchronized firing groups in
which the module participates:
coh() ∈ [
coh( ) ∈ [
There being no intra-module relationships in a module means that the module doesn’t contain any internal transitions. In that case the rank of the internal incidence matrix is equal to 0 for each module and for the entire modular net. Therefore, it follows:
= ∅ ⇒ coh() = 0, = ∅ ⇒ coh( ) = 0
Intramodule relationships can only be added by adding further internal transitions. If the efect of such transitions is a linear combination of already existing transitions, the rank stays the same. If it isn’t a linear combination, the rank increases. Consequently, for a module ′ that results from a module by adding intra-module relationships so that ⊆ ′ and the corresponding modular systems ′ (containing ′) and (containing ), it follows that: coh() ≤ coh( ′), coh( ) ≤ coh( ′)
After merging two unrelated modules, 1 and 2, into the combined ′, their combined incidence matrix is a block diagonal matrix with the individual incidence matrices as blocks. In this form, it can be directly seen that the rows/columns corresponding to 1 are necessarily linearly independent of the rows/columns corresponding to 2. Consequently, the rank of the combined internal incidence matrix is equal to the sum of the ranks of the individual internal incidence matrices:
rank( ′ ) = rank( 1 ) + rank( 2 ) For the cohesion follows then: coh(′) = rank( 1 ) + rank( 2 ) |1 | + |2 | ≤ max ︂( rank( 1 ) , rank( 2 ) ︂) |1 | |2 | Considering the modular system as a whole, both the rank of the internal incidence matrix as well as the number of places stay the same. Therefore, the modular system containing 1 and 2 has the same cohesion as the modular system ′ in which 1 and 2 are replaced by ′:
coh( ) = coh( ′)
In particular, the desired inequality of coh( ) ≥ coh( ′) holds.
Interestingly, this cohesion measure inversely relates to the number of internal P-invariants. By the
rank-nullity theorem [
Just as the inherent structure of modular P/T nets translates directly to the structure of the transposed
incidence matrix, forming an SBBD matrix [
Such a partition is suficient for deducing a modular structure for the initially unmodularized net
[
A matrix structure similar to the SBBD form is the doubly-bordered block diagonal (DBBD) structure, which also allows a border along the rightmost block column of the matrix. In the context of modular P/T nets, this additional border would, in the most direct way, translate to inter-module interactions between places in addition to the interactions between transitions. Therefore, the BDDB structure could be interpreted as a modular net allowing both synchronous channels and shared places.
But the BDDB structure is also relevant in modular P/T nets that use only synchronous channels. Specifically, it is the special case of symmetric matrices in DBBD form that is of interest. When considering the symmetric preTpre + postTpost in DBBD form, its blocks along the diagonal translate to internal transitions, while its borders translate to synchronized firing groups. Therefore, permuting matrices into BDDB form is also analogous to modularization of P/T nets. This is illustrated by the following example:
The transitions corresponding to the blocks in the diagonal would then be internal transitions. In
this case, 1 and 2 would be internal transitions of the module given by the set of places 1,2. The
same applies to 3, 4 and the module given by 3,4. The remaining places ∖ (1,2 ∪ 3,4) are only
connected to external transitions, which would be 5. The rank of the blocks in preTpre + postTpost
then relates back to the rank of the blocks in ∆ T [
Permuting matrices into SBBD or DBBD form is a well-researched topic [
It is also conceivable to use them in modularization procedures directly. For example, a probabilistic algorithm could output many diferent possible ways of splitting a net into modules. It would then be required to determine which of these potential modularizations is in some sense the best, which could be done through our coupling and cohesion measures.
Another interesting aspect of the reduction in Phase 1 is that having multiple modules that only
partially exhibit the same internal behavior is already beneficial. This would justify using the
modularization based on replication proposed in [
One aspect that wasn’t further examined in this paper is that the structure of the synchronized
incidence matrix could be further utilized. In practice, not every module will be participating in every
synchronized firing group, so that many entries in could be zeros. However, instead of specifically
addressing this through modifications in the modular Gaussian elimination, it might be more prudent
to instead arrange the matrix in a recursive bordered block diagonal form [
Lastly, it is worth mentioning that the use of the modular Gaussian elimination isn’t solely confined
to the computation of P-invariants. For example, just the step of reducing an incidence matrix to row
echelon form is enough to identify redundant information, reducing memory resources required for
state space construction [
The parts of the algorithm that benefit from the independence (Phase 1 and Phase 2) achieve asymptotic improvements if the number of modules depends on the net’s overall number of places and transitions as opposed to having a fixed number of modules regardless of the net’s overall size. This is in particular the case if modules are of roughly the same constant size.
The size of the interface between modules influences the algorithm’s runtime of parts, in which the terms corresponding to interactions between modules are considered (Phase 2 and Phase 3). The specific ways of measuring this interface size, either through the external transitions in the modules or the resulting possible synchronization, naturally serve as formal measures of coupling in modular P/T nets.
The extent to which the computation concerning interactions between modules can be performed in a manner that keeps modules independent is determined by the rank of the internal incidence matrix. This rank, then, constitutes a formal measure of cohesion in modular P/T nets.
These measures of coupling and cohesion are thus based on characteristics of modular nets that are demonstrably beneficial in the verification of system properties. Due to parallels in the good modularity in this sense for both matrices and modular nets, it naturally arises that procedures for transforming matrices into modular structures and the modularization of P/T nets aim to optimize the same goal. Specifically, procedures for permuting matrices into either SBBD or DBBD form can be directly used to transform a P/T net into a modular P/T net.
Further investigations, as discussed in the previous section, are quite promising. The concept of modules is highly relevant to the design of system models and analysis. The role of the concept of netswithin-nets is central for the design of complex interacting systems. Therefore, the topic of coupling and cohesion will be one of our research interests.
During the preparation of this work, the authors used . . . • . . . LanguageTool, QuillBot in order to: Grammar and spelling check • . . . DeepL in order to: Translate Text. • . . . ChatGPT in order to: Rephrasing.
• . . . Grammarly in order to: Grammar and spelling check, Repharsing.
After using these tool(s)/service(s), the authors reviewed and edited the content as needed and take full responsibility for the publication’s content.