Redes de petri01

REDES DE PETRI

1.

´ Introduccion

El desarrollo de las Redes de Petri (RdP) comienza con la publicaci´n en 1962 o de la tesis doctoral “Kommunikation mit Automaten” de Carl A. Petri. Ah´ se exı pone una teor´ no enteramente formalizada, que tiene prop´sitos a la vez te´ricos ıa o o y pr´cticos. a A partir de 1970, J.B. Dennis y su grupo, “Computation Structure Group” (MIT), se interesanen el trabajo de Petri, como medio para modelar algoritmos paralelos y estructuras concurrentes en hardware y software. El grupo de Dennis introduce refinamientos en la teor´ b´sica de Petri. ıa a A partir de entonces, la teor´ de las RdP ha conocido cierto auge, y diversos ıa autores han propuesto muy diversas variantes (RdP coloreadas, RdP temporizadas, etc.). Asimismo, las aplicaciones haninvadido varios dominios t´cnicos, en partice ular los sistemas de manufactura. De estos datos hist´ricos concluimos lo siguiente: o 1. La definici´n de las RdP se ha extendido con el tiempo. o 2. Actualmente hay varias definiciones alternativas. 3. La teor´ se ha desarrollado junto con la pr´ctica. ıa a Para nosotros las RdP van a ser una representaci´n expl´ o ıcita de las funciones de transici´n de losSED, descritas de una forma gr´fica, intuitiva y capturando o a mucha informaci´n del sistema. o Un aut´mata siempre puede ser representado por una RdP, el inverso no siempre o se cumple.

1

2

REDES DE PETRI

2.

Bases de las RdP

El proceso de definir una RdP lleva dos pasos: 1. Definir el grafo de la red de Petri, tambi´n llamado estructura de la RdP, e que equivale al diagrama detransici´n de estados de los aut´matas. o o 2. A˜adir a este grafo unos estados iniciales y un conjunto de estados marcan dos, y una funci´n etiquetando la transici´n, dando el modelo completo de o o la RdP, su din´mica asociada, y los lenguajes que genera y marca. a Los eventos est´n asociados con las transiciones. Para que una transici´n se ejea o cute (dispare) antes se deben cumplir una seriede condiciones que a su vez est´n a asociadas algunos lugares, que son vistos como entradas a la transici´n. Tras proo ducirse el disparo empiezan a cumplirse otras condiciones -asociadas a sus lugares correspondientes- que son vistos como salidas de la transici´n. o Las transiciones, los lugares, y las relaciones entre ellos son los componentes b´sicos del grafo de la Red de Petri. a Una RdP,tiene dos tipos de nodos, lugares y transiciones, y arcos conect´ndolos a entre s´ Es un grafo bipartito, en el sentido de que los arcos no pueden conectar ı. directamente nodos del mismo tipo, es decir, conectan lugares a transiciones, o transiciones a lugares, pero nunca un lugar con un lugar ni un transici´n con una o transici´n. o

2.1. d´nde o

Definici´n. Una Red de Petri es un grafobipartito pesado o (P, T, A, w)

P es un conjunto finito de lugares. Representaremos cada lugar con un c´ ırculo P = {p1 , p2 , ..., pn }

T es el conjunto finito de transiciones. Representaremos cada transici´n con o una raya T = {t1 , t2 , ..., tm }

A ⊆ (P × T ) ∪ (T × P ) es el conjunto de los arcos de los lugares a las transiciones a los lugares. Los representaremos con una flecha → (pi , tj ) o(tj , pi )

REDES DE PETRI

3

w : A → {1, 2, 3, ...} es la funci´n peso de los arcos. El peso de los arcos o ser´ un entero positivo. a Asumimos que la RdP (P,T,A,w) no tiene lugares ni transiciones aislados. Es conveniente, aunque no necesario que P y T sean contables. En la descripci´n de una RdP utilizamos I(tj ) para representar el conjunto de o lugares de entrada a la transici´n tj yO(tj ) para representar el conjunto de lugares o de salida de la transici´n j. o I(tj ) = {pi ∈ P : (pi , tj ) ∈ A} O(tj ) = {pi ∈ P : (tj , pi ) ∈ A}

An´logamente podemos ver I(pi ) y O(pi ) a

I(pi ) = {tj ∈ P : (tj , pi ) ∈ A} O(pi ) = {tj ∈ P : (pi , tj ) ∈ A}

Si w(pi , tj ) = k entonces hay k arcos de pi a tj . A la hora de la representaci´n o gr´fica para valores de k peque˜os...