Generalized nets

From Ifigenia, the wiki for intuitionistic fuzzy sets and generalized nets

(Redirected from Generalized net)
Jump to: navigation, search

Generalized nets (GNs) constitute a discrete tool for universal description of adaptable, flexible, structured and reusable models of complex systems with many different and interacting components, not necessarily of the homogeneous structure and origin, usually involved in parallel, simultaneous activities. Generalized nets represent a significant extension and generalization of the concept of Petri nets, as well as of other Petri nets extensions and modifications.

Contents

Components of a generalized net

A GN transition with m inputs and n outputs
A GN transition with m inputs and n outputs

A generalized net consists of:

  • a static structure,
  • a dynamic structure,
  • temporal components.

The static structure consists of objects called transitions, which have input and output places. Two transitions can share a place, but every place can be an input of at most one transition and can be an output of at most one transition.

The dynamic structure consists of tokens, which act as information carriers and can occupy a single place at every moment of the GN execution. The tokens pass through the transition from one input to another output place; such an ordered pair of places is called transition arc. The tokens' movement is governed by conditions (predicates), contained in the predicate matrix of the transition.

The information carried by a token is contained in its characteristics, which can be viewed as an associative array of characteristic names and values. The values of the token characteristics change in time according to specific rules, called characteristic functions. Every place possesses at most one characteristic function, which assigns new characteristics to the incoming tokens. Apart from movement in the net and change of the characteristics, tokens can also split and merge in the places.

The temporal components describe the time scale of GN execution. Temporal conditions control the transitions' moments of activation and duration of active state. Various other tools for fine tuning of the GN functioning are provided in the form of priorities of separate transitions, places and tokens, as well as capacities of places and transitions arcs.

Graphic representation

Formal description

Formally described, the generalized net is represented by the following four-tuple:

LaTeX: %0A%3C%20%5Cunderbrace%7B%20%3CA%2C%20%5Cpi_%7BA%7D%2C%20%5Cpi_%7BL%7D%2C%20c%2C%20f%2C%20%5Ctheta_%7B1%7D%2C%20%5Ctheta_%7B2%7D%20%3E%7D_%7B1.%5C%20Static%20%5C%20structure%7D%2C%0A%20%20%5Cunderbrace%7B%20%3CK%2C%20%5Cpi_%7BK%7D%2C%20%5Ctheta_%7BK%7D%20%3E%7D_%7B2.%20%5C%20Dynamic%20%5C%20structure%7D%2C%0A%20%20%5Cunderbrace%7B%20%3CT%2C%20t%5E%7B0%7D%2C%20t%5E%7B%2A%7D%20%3E%7D_%7B3.%20%5C%20Time%7D%2C%0A%20%20%5Cunderbrace%7B%20%3CX%2C%20%5CPhi%2C%20b%20%3E%7D_%7B4.%20%5C%20Memory%7D%20%3E%0A

where:

1. Static structure
  • LaTeX: A is a set of transitions (see the formal definition of a transition)
  • LaTeX: %5Cpi_%7BA%7D is a function giving the priorities of the transitions, i.e. LaTeX: %5Cpi_%7BA%7D%20%3A%20A%20%5Crightarrow%20N where N = {0, 1, 2, ...} ∪ {∞}
  • LaTeX: %5Cpi_%7BL%7D is a function giving the priorities of the places, i.e. LaTeX: %5Cpi_%7BL%7D%20%3A%20L%20%5Crightarrow%20N
  • LaTeX: c is a function giving the place capacities, i.e. LaTeX: c%20%3A%20L%20%5Crightarrow%20N
  • LaTeX: f is a function giving the truth value of the predicates. In the basic case, it may obtain values "true" (1) and "false" (0). In fuzzy generalized nets its domain is the [0;1] interval (see fuzzy set) and in the intuitionistic fuzzy generalized nets its domain is the set [0;1]×[0;1] (see intuitionistic fuzzy set).
  • LaTeX: %5Ctheta_%7B1%7D is a function giving the next time moment when a given transition will be fired (will become active). Hence, LaTeX: %5Ctheta_%7B1%7D%28t%29%20%3D%20t%27 where LaTeX: t%2C%20t%27%20%5Cin%20%5BT%2C%20T%2Bt%5E%2A%5D%3B%20t%20%5Cle%20t%27. The value of this function is being recalculated in the moment when the transition's active state ceases.
  • LaTeX: %5Ctheta_%7B2%7D is a function giving the duration of the transition's active state. Hence, LaTeX: %5Ctheta_%7B2%7D%28t%29%20%3D%20t%27 where LaTeX: t%2C%20t%27%20%5Cin%20%5BT%2C%20T%2Bt%5E%2A%5D%3B%20t%27%20%5Cge%200. The value of this function is calculated in the moment when the transition's active state begins.


2. Dynamic structure
  • LaTeX: K is the set of tokens of the generalized net. In certain cases it is more convenient to denote this set as LaTeX: K%20%3D%20%5Cbigcup_%7Bl%20%5Cin%20Q%5EI%7D%20K_%7Bl%7D%20 where LaTeX: K_%7Bl%7D is the set of all GN tokens which are waiting to enter place LaTeX: l and LaTeX: Q%5EI is the set of all input places in the net.
  • LaTeX: %5Cpi_K is a function giving the priorities of the tokens, i.e. LaTeX: %5Cpi_%7BK%7D%20%3A%20K%20%5Crightarrow%20N
  • LaTeX: %5Ctheta_K is a function giving the moment of time when a given token may enter the GN, i.e. LaTeX: %5Ctheta_K%20%28%5Calpha%29%3Dt where LaTeX: %5Calpha%20%5Cin%20K%2C%20t%20%5Cin%20%5BT%3B%20T%2Bt%5E%2A%5D


3. Time
  • LaTeX: T is the moment of time when the generalized net starts functioning. This moment is determined according to a fixed global timescale.
  • LaTeX: t%5E0 is the elementary time step of the fixed global timescale (the interval with which time increments in the timescale).
  • LaTeX: t%5E%2A is the total duration of functioning of the net.


4. Memory
  • LaTeX: X is the set of initial characteristics, which tokens may exhibit when they enter the net for first.
  • LaTeX: %5CPhi is a characteristic function, which assigns a new characteristic to each token when it makes the transfer from an input to an output place of a given transition.
  • LaTeX: b is a function giving the maximal number of characteristics, which a given token may obtain during its movement throughout the net, i.e. LaTeX: b%20%3A%20K%20%5Crightarrow%20N. In general, LaTeX: b may possess four different values: 0, 1, LaTeX: s or LaTeX: %5Cinfty meaning that the token keeps, respectively: none of its characteristics, its last characteristic, its last LaTeX: s characteristics, or all of its characteristics obtained during its movement in the net.

Algorithms related to generalized nets

In a Petri net implementation, parallelism is reduced to a sequential firing of the net transitions and in general the order of their activation is probabilistic or dependent on the transitions' priorities, if any. The respective algorithms for generalized nets enable a more detailed modelling of the described process.

In the the book "Generalized Nets" from 1991 year [1], there were formulated two major algorithms, related to generalized nets:

The algorithm for transition functioning was later modified in 2007 [2].

Theorem 20 in the book "On Generalized Nets Theory" from 2007 year [3] states that the functioning and the results of the work of a given GN transition are equal for both algorithms, yet the difference between both algorithms is that in almost any case the modified algorithm yields results more quickly.

Reduced generalized nets

Extensions of generalized nets

Generalized nets have been subject of multiple different extensions. For each of these it has been proved that represents a conservative extension, i.e. there exists an ordinary generalized net which describes the extended GN, i.e. both nets have the same modelling capabilities.

The following extensions of GNs have been determined so far:

Theoretical aspects of generalized nets

Algebraic aspect

Topological aspect

Logical aspect

Functional aspect

Construction of generalized nets

Modelling and simulation

Software implementation of generalized nets

See also

References

Ifigenia stub This article is a stub. You can help Ifigenia by expanding it.
Personal tools