Abbiamo introdotto un’algebra di processi come CCS dove processi sequenziali interagiscono tra loro tramite handshaking. Un altro modello usato, con varie implementazioni, sono gli automi a stati finiti (usati per reti neurali, riconoscitori di linguaggi, modelli di protocolli di comunicazioni, etc…).

Si passa ora alle reti di Petri, introdotte da Petri nel 1962 nella sua tesi di dottorato, partendo da una critica ai modelli fatti tramite automi a stati per protocolli di comunicazioni.

La nuova teoria dei sistemi è basata sui principi della fisica quantistica, il modello, nell’ottica di Petri, non è quindi un modello chiuso ma è in grado di comunicare con l’ambiente (in sintonia con le teorie della fisica). Vuole una teoria dei sistemi in grado di descrivere il flusso di informazioni e che permetta di analizzare sistemi con un’organizzazione complessa.

La sua teoria generale dei sistemi che processano informazione si basa su, tra le altre cose:

• comunicazione
• sincronizzazione
• flusso di informazione
• relazione di concorrenza e indipendenza causale

A partire dagli anni 70 questa teoria si è sviluppata dal punto di vista dell’espressività, portando allo studio di diverse classi di reti. Si sviluppano anche tecniche formali di analisi e di verifica delle reti (tramite algebra lineare, teoria dei grafi, ecc). Le reti di Petri hanno tantissimi ambiti d’uso, tra i quali:

• specificare protocolli di comunicazioni
• disegnare circuiti asincroni
• algoritmi concorrenti / paralleli
• modellare sistemi organizzativi
• modellare db distribuiti
• specificare sistemi di controllo industriali
• modellare sistemi biologici e per modellare reazioni chimiche
• valutare le prestazioni (tramite reti stocastiche e temporizzate)

Sistemi di Transizioni Etichettati - LTS

Definizione: I sistemi di transizione etichettati sono definiti come gli automi a stati finiti ma senza essere visti come riconoscitori di linguaggi, infatti un sistema è formato da un insieme, solitamente finito, di stati globali $S$. Si ha poi un alfabeto delle possibili azioni che può eseguire il sistema. Si hanno anche delle relazioni di transizioni, ovvero delle transizioni che permettono di specificare come, attraverso un’azione, si passa da uno stato ad un altro. Le transizioni si rappresentano con archi etichettati tra i nodi, che rappresentano gli stati. Le etichette degli archi rappresentano le azioni necessarie alla trasformazione. L’insieme delle azioni viene chiamato $E$ mentre $T\subseteq S \times E\times S$ è l’insieme degli archi etichettati. Può essere individuato uno stato iniziale $s_0$. Un sistema non è obbligato a “terminare”, quindi non si ha obbligatoriamente uno stato finale.