Submit your research to the International Journal "Notes on Intuitionistic Fuzzy Sets". Contact us at nifs.journal@gmail.com

Call for Papers for the 27th International Conference on Intuitionistic Fuzzy Sets is now open!
Conference: 5–6 July 2024, Burgas, Bulgaria • EXTENDED DEADLINE for submissions: 15 APRIL 2024.

Algorithm for transition functioning: Difference between revisions

From Ifigenia, the wiki for intuitionistic fuzzy sets and generalized nets
Jump to navigation Jump to search
mNo edit summary
No edit summary
Line 3: Line 3:
The algorithm comprises a "building block" for the entire [[algorithm for generalized net functioning]].
The algorithm comprises a "building block" for the entire [[algorithm for generalized net functioning]].


The first book it was published in, was the book "[[Generalized Nets (World Scientific)|Generalized Nets]]" from 1991 year <ref>Atanassov K., "Generalized Nets", World Scientific, Singapore, 1991, ISBN 978-981-02-0598-0</ref>. The algorithm was [[Algorithm for transition functioning#Modified algorithm, 2007|later modified]] in 2007 <ref>Atanassov K., Tasseva V., Trifonov T., [[Issue:Modification of the algorithm for token transfer in generalized nets|Modification of the algorithm for token transfer in generalized nets]], Cybernetics and Information Technologies, Vol.  7, 2007, Np. 1, 62-66</ref>.  
The first book it was published in, was the book "[[Generalized Nets (World Scientific)|Generalized Nets]]" from 1991 year <ref>Atanassov K., "Generalized Nets", World Scientific, Singapore, 1991, ISBN 978-981-02-0598-0</ref>. The algorithm was [[Algorithm for transition functioning#Modified algorithm, 2007|modified]] in 2007 <ref>Atanassov K., Tasseva V., Trifonov T., [[Issue:Modification of the algorithm for token transfer in generalized nets|Modification of the algorithm for token transfer in generalized nets]], Cybernetics and Information Technologies, Vol.  7, 2007, Np. 1, 62-66</ref>.  


The functioning and the results of the work of a given GN transition are equal for both the original and the modified algorithms, yet the difference between both is that in almost any case the modified algorithm yields results more quickly.
The functioning and the results of the work of a given GN transition are equal for both the original and the modified algorithms, yet the difference between both is that in almost any case the modified algorithm yields results more quickly.
Line 47: Line 47:
|- valign="top"
|- valign="top"
| '''Step 10'''
| '''Step 10'''
| style="padding-bottom:1em" | If the answer to the question on '''Step 9''' is '''"yes"''', go to '''Step 2''' (to update the tokens' order in the places).  
| style="padding-bottom:1em" | If the answer to the question on '''Step 9''' is ''"yes"'', go to '''Step 2''' (to update the tokens' order in the places).  
|- valign="top"
|- valign="top"
| '''Step 11'''
| '''Step 11'''
| style="padding-bottom:1em" | If the answer to the question on '''Step 9''' is '''"no"''', terminate the current functioning of the transition.  
| style="padding-bottom:1em" | If the answer to the question on '''Step 9''' is ''"no"'', terminate the current functioning of the transition.  
|}
|}
   
   
== Modified algorithm, 2007 ==
== Modified algorithm, 2007 ==
{| width="100%"
|- valign="top"
| width="10%" | '''Step 1*'''
| style="padding-bottom:1em" width="90%" | The input and the output places are arranged by priority.
|- valign="top"
| '''Step 2*'''
| style="padding-bottom:1em" | In each input place two lists are formed: a list of all tokens, arranged by priority, and an empty list.
|- valign="top"
| '''Step 3*'''
| style="padding-bottom:1em" | An empty index matrix '''R''', which corresponds to the matrix of the predicates '''r''' of the given transition, is generated. It is initialized with a value "0" (corresponding to value "false") of all of the elements of this new matrix, which:
* are placed in a row, corresponding to an empty input place,
* are placed in a column, corresponding to a full output place,
* are placed in ''(i,j)''-th position, for which ''m<sub>i,j</sub> = 0'', i.e. the current capacity of the arc between ''i''<sup>-th</sup> input and ''j''<sup>-th</sup> output place is zero.
|- valign="top"
| '''Step 4*'''
| style="padding-bottom:1em" | The sorted places are passed sequentially by their priority, starting with the place having the highest priority, which has at least one token and through which no transfer has occurred on the current time-step. For its highest priority token (from the first list) the predicates corresponding to the relevant row of matrix '''R''' are checked. The elements of '''r''', for which the elements of '''R''' are not zeros, are calculated.
|- valign="top"
| '''Step 5*'''
| style="padding-bottom:1em" | Depending on the execution of the operator for permission or prohibition of tokens splitting over the net, the token from '''Step 4*''' will pass either to all permitted to it output places, or to this very place among them, which has the highest priority. If one token cannot pass through a given transition on this time interval, it is moved to the second list of tokens of the corresponding place. The tokens, which have entered the place after the transition activation, are moved to the second list, too.
|- valign="top"
| '''Step 6*'''
| style="padding-bottom:1em" | The capacities of all places on the output of the transition, which are input places for another currently active transitions, increment with 1 for each token that has left them on this step.
|- valign="top"
| '''Step 7*'''
| style="padding-bottom:1em" | The capacities of all output places, in which a token, determined at '''Step 4*''', has entered, decrement with 1. If the maximum number of tokens for a given output place has been reached, the elements of the corresponding column of matrix '''R''' are set to value "0".
|- valign="top"
| '''Step 8*'''
| style="padding-bottom:1em" | The capacities of all arcs, through which a token has passed, decrement with 1. If the capacity of an arc has reached 0, the elements of the corresponding output place of matrix '''R''' are set to value 0.
|- valign="top"
| '''Step 9*'''
| style="padding-bottom:1em" | The values of the characteristic function '''Φ''' for the output places, in which tokens have entered (formed by the token passed according to '''Step 5*''') are calculated.
|- valign="top"
| '''Step 10*'''
| style="padding-bottom:1em" | If there are more places, which could be output ones for tokens at this step, the algorithm returns back to '''Step 4*'''; in the opposite case it proceeds to '''Step 11*'''.
|- valign="top"
| '''Step 11*'''
| style="padding-bottom:1em" | The current model time '''t''' is increased with '''t<sup>0</sup>'''.
|- valign="top"
| '''Step 12*'''
| style="padding-bottom:1em" | Is the current time moment equal to or greater than '''t<sub>1</sub> + t<sub>2</sub>'''?
* If the answer of the question is ''"no"'', return to '''Step 4*'''.
* Otherwise, the transition functioning terminates.
|}


== References ==
== References ==

Revision as of 18:10, 22 November 2009

The algorithm for generalized net transition functioning represents the algorithm of GN tokens transfer from an input place of a GN transition to its output place.

The algorithm comprises a "building block" for the entire algorithm for generalized net functioning.

The first book it was published in, was the book "Generalized Nets" from 1991 year [1]. The algorithm was modified in 2007 [2].

The functioning and the results of the work of a given GN transition are equal for both the original and the modified algorithms, yet the difference between both is that in almost any case the modified algorithm yields results more quickly.

Original algorithm, 1991

Step 1 Sort the input and output places of the transitions by their priorities.
An important addition to the GN transition description above, which is related to the software implementation of the transition's functioning, is the following. The tokens from a given input place are divided into two groups. The first group contains those tokens that can be transferred to the transition output, while the second group contains the rest tokens. Let both groups be denoted by P1(l) and P2(l), respectively, where l is the corresponding place.
Step 2 Sort the tokens from group P1 of the input places (following the order from Step 1) by their priorities.
Let ri,j denote the predicate index matrix of the transition. Then, let us make the following assumption:
Step 3 Assign value 0 to all elements of R, for which either
  • the input place which corresponds to the respective predicate is empty (the P1 part is empty); or
  • the output place which corresponds to the respective predicate is full; or
  • the current capacity of the arc between the corresponding input and output places is 0.
Step 4 Calculate the values of the other elements of matrix r and assign the obtained values to the elements of matrix R.
Step 5 Calculate the values of the characteristic functions related to the corresponding output places in which tokens will enter. Assign these characteristics to the entering tokens.
Step 6 Perform the following sub-steps for each input place by the order of input place priorities:
  • Select the tokens with the highest priority in this input place;
  • Transfer the selected tokens to all output places, for which the corresponding predicate enables this (the tokens go to group P2 of the output places).
Step 7 Transfer the tokens with the highest priority, for which all calculated values of the predicates are equal to "false" to the group P2 of the corresponding places. To this group, also transfer all tokens that cannot be transferred to the corresponding output places because these places have already been filled up with tokens from other places with higher priorities.
Step 8 Add t0 to the current time, i.e., TIME := TIME + t0
Step 9 Check whether the value of the current time is less than t1 + t2 (the time- components of the considered transition).
Step 10 If the answer to the question on Step 9 is "yes", go to Step 2 (to update the tokens' order in the places).
Step 11 If the answer to the question on Step 9 is "no", terminate the current functioning of the transition.

Modified algorithm, 2007

Step 1* The input and the output places are arranged by priority.
Step 2* In each input place two lists are formed: a list of all tokens, arranged by priority, and an empty list.
Step 3* An empty index matrix R, which corresponds to the matrix of the predicates r of the given transition, is generated. It is initialized with a value "0" (corresponding to value "false") of all of the elements of this new matrix, which:
  • are placed in a row, corresponding to an empty input place,
  • are placed in a column, corresponding to a full output place,
  • are placed in (i,j)-th position, for which mi,j = 0, i.e. the current capacity of the arc between i-th input and j-th output place is zero.
Step 4* The sorted places are passed sequentially by their priority, starting with the place having the highest priority, which has at least one token and through which no transfer has occurred on the current time-step. For its highest priority token (from the first list) the predicates corresponding to the relevant row of matrix R are checked. The elements of r, for which the elements of R are not zeros, are calculated.
Step 5* Depending on the execution of the operator for permission or prohibition of tokens splitting over the net, the token from Step 4* will pass either to all permitted to it output places, or to this very place among them, which has the highest priority. If one token cannot pass through a given transition on this time interval, it is moved to the second list of tokens of the corresponding place. The tokens, which have entered the place after the transition activation, are moved to the second list, too.
Step 6* The capacities of all places on the output of the transition, which are input places for another currently active transitions, increment with 1 for each token that has left them on this step.
Step 7* The capacities of all output places, in which a token, determined at Step 4*, has entered, decrement with 1. If the maximum number of tokens for a given output place has been reached, the elements of the corresponding column of matrix R are set to value "0".
Step 8* The capacities of all arcs, through which a token has passed, decrement with 1. If the capacity of an arc has reached 0, the elements of the corresponding output place of matrix R are set to value 0.
Step 9* The values of the characteristic function Φ for the output places, in which tokens have entered (formed by the token passed according to Step 5*) are calculated.
Step 10* If there are more places, which could be output ones for tokens at this step, the algorithm returns back to Step 4*; in the opposite case it proceeds to Step 11*.
Step 11* The current model time t is increased with t0.
Step 12* Is the current time moment equal to or greater than t1 + t2?
  • If the answer of the question is "no", return to Step 4*.
  • Otherwise, the transition functioning terminates.

References

  1. Atanassov K., "Generalized Nets", World Scientific, Singapore, 1991, ISBN 978-981-02-0598-0
  2. Atanassov K., Tasseva V., Trifonov T., Modification of the algorithm for token transfer in generalized nets, Cybernetics and Information Technologies, Vol. 7, 2007, Np. 1, 62-66