Soluzione di equazioni su linguaggi: teoria e applicazioni

Relatore
Tiziano Villa - Universita` di Udine

Data e ora
martedì 7 dicembre 2004 alle ore 17.30 - ore 17:00: te`,caffe`, biscotti/ini

Referente
Franco Fummi

Referente esterno

Data pubblicazione
29 novembre 2004

Dipartimento
 

Riassunto

Il problema di progettare una componente che combinata con una parte
nota dia luogo a un sistema che si conforma a una specifica data si pone
in molte applicazioni che vanno dalla sintesi logica al controllo discreto.
In questo seminario presentiamo una formulazione del problema come
risoluzione di equazioni su linguaggi.
Le equazioni sui linguaggi possono essere definite rispetto a vari
operatori di composizione e nozioni di conformita'.
In particolare abbiamo considerato due operatori di composizione,
chiamati sincrona e parallela, e come criterio di conformita'
il contenimento tra linguaggi.
La composizione sincrona modella la composizione di sistemi digitali
sincroni; la composizione parallela (chiamata anche asincrona)
nasce nel contesto dei processi insensibili al ritardo e
modella un protocollo tra agenti interagenti in modo asincrono.

In particolare studiamo la soluzione piu' generale delle equazioni
A @ X <= C, dove @ sta per composizione sincrona o parallela, e definiamo
gli operatori su linguaggi necessari per esprimerla.
Poi specializziamo tali equazioni a linguaggi regolari e linguaggi
generati da macchine a stati finiti, studiando la soluzione piu'
generale nella classe data e alcune sue restrizioni interessanti, come
quelle che sono progressive o composizionalmente progressive
(definendo macchine a stati e loro composizioni specificate per ogni
ingresso).

Ad illustrazione, applichiamo la teoria alla sintesi di un convertitore
tra due diversi protocolli di comunicazione.
ornamento
Inizio pagina