RICERCA ITALIANA     

Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali

Università degli Studi di Palermo

Abstract

Questo progetto di ricerca si concentra su linguaggi formali e automi e mira a far progredire la teoria su questi temi e le loro applicazioni a problemi tecnologici e scientifici. La teoria dei linguaggi formali e degli automi, uno dei più affermati campi in Computer Science, offre ancora complessi problemi aperti e linee di ricerca in molte direzioni.
Infatti, da un lato, sono emerse nuove applicazioni di concetti della teoria degli automi, in aggiunta alle più classiche applicazioni come il pattern matching, l’analisi sintattica e la validazione di software. Queste includono i sistemi di analisi e di verifica, l’elaborazione dei linguaggi naturali, l’information retrieval, la compressione dei dati, e il controllo di sistemi a eventi discreti. Inoltre, le nuove sfide per la teoria degli automi comprendono la biologia, la sicurezza delle reti, il calcolo quantistico, la tomografia, e l’elaborazione di immagini.
D'altra parte, alcune profonde questioni della teoria classica sono ancora aperte, e nuovi problemi teorici derivano anche dalle applicazioni. Questo è il motivo per cui i fondamenti matematici di questa teoria si basano sulle aree più avanzate della matematica. Mentre nei primi anni sessanta si utilizzavano solo la teoria elementare dei grafi e la combinatoria, successivamente sono stati introdotti nuovi strumenti di algebra non commutativa, logica, teoria della probabilità e dinamica simbolica, e gli sviluppi più recenti prendono in prestito idee >>>

Coordinatore Scientifico del Programma di Ricerca

Antonio Restivo Università degli Studi di PALERMO

Obiettivo del Programma di Ricerca

L'obiettivo del progetto è quello di sviluppare la ricerca nel campo dei linguaggi formali e automi (sia per i modelli teorici e le applicazioni in campi specifici) integrando le diverse competenze delle unità che partecipano al progetto. Il progetto è sinergico con un programma di 5 anni della European Science Foundation chiamato AutoMathA (2005-2010), che è stato proposto con successo da alcuni membri del nostro gruppo. L’iniziativa ESF offrirà delle opportunità per la comunicazione scientifica e la collaborazione con i principali gruppi europei in questo settore, amplificando così efficacemente l'impatto potenziale della nostra ricerca. Il progetto è incentrato su un certo numero di argomenti. Più in particolare, si prevede di sviluppare le linee di ricerca riportate di seguito.

A1) Modelli di automi, serie formali, e loro proprietà.
La nozione di automa a stati finiti, e la descrizione del suo comportamento come linguaggio, è stata proposta negli anni Cinquanta. I modelli ottenuti sono ancora estremamente rilevanti sia dal punto di vista teorico che per le loro innumerevoli applicazioni. Una linea di ricerca che proponiamo in questo settore riguarda lo studio di automi quantistici. In questo contesto, ci occuperemo di problemi di decisione e di riconoscimento di linguaggi regolari per mezzo di automi quantistici. Come altra linea di ricerca, studieremo la misura della complessità descrittiva di linguaggi. In questo contesto, saranno >>>

Risultati parziali attesi

I risultati attesi e il loro interesse sono illustrati nelle seguenti linee di ricerca del progetto. La maggior parte di essi sono essenzialmente teorici e sono compatibili con gli interessi attuali della comunità scientifica. In molti casi hanno una chiara potenziale applicazione.

Per quanto riguarda lo studio di automi, e di altri modelli di calcolo, ci aspettiamo di ottenere risultati su problemi come la sintesi di automi quantistici e gli splicing System, e sui problemi di complessità descrizionale. Tali risultati contribuiranno a migliorare le nostre conoscenze sul complesso rapporto tra la potenza del deterministico, probabilistico, quantistico
e DNA computing. D'altro canto, la soluzione di problemi specifici riguardanti modelli di automi, al di là del loro interesse intrinseco, porterebbero anche a sviluppi di nuove metodologie. A titolo di esempio, trovare una procedura per stabilire se un linguaggio quantistico è incluso in un linguaggio regolare ci permetterebbe di estendere la metodologia proposta da Blondel e al. (basata sulla compattezza del gruppo di matrici unitarie, relativo al calcolo delle inverse) a casi più generali (basati su semigruppi, consentendo anche elementi non invertibili).
Ci aspettiamo anche di fare qualche progresso in merito ad alcune questioni algoritmiche basilari su automi finiti ancora irrisolte. Una di queste riguarda la minimizzazione di automi deterministici. Nel 1971 Hopcroft ha dato un algoritmo per >>>

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

A1) Modelli di automi, serie formali, e loro proprietà
La nozione di automa a stati finiti e la descrizione del suo comportamento tramite un linguaggio fu proposta negli anni 50. Problemi classici considerati in questo contesto sono l’analisi e la sintesi di un modello. Essi sono stati studiati per modelli deterministici e non deterministici, per quelli probabilistici e più recentemente per modelli quantistici. L’idea di usare l’interferenza quantistica per scopi computazionali fu originariamente proposta da Feymann e successivamente sistematizzata da vari autori nel contesto della teoria della complessità strutturale. In quest’area sono stati ottenuti rilevanti risultati che confermano l’interesse per i modelli computazionali quantistici [G].
Esistono alcune fondamentali questioni algoritmiche ancora aperte sugli automi finiti e una tra queste è legata alla minimizzazione di automi deterministici. Nel 1971 Hopcroft propose un algoritmo per minimizzare un automa deterministico di taglia n in tempo O(nlogn). Recentemente è stato provato che il precedente bound è effettivamente raggiunto per alcune particolari scelte [BC].
Problemi algoritmici per semigruppi inversi hanno ricevuto attenzione sempre crescente negli ultimi anni. Gli automi di Schützenberger (generalizzazioni dei grafi di Cayley) hanno un ruolo centrale in quest’ambito. Recentemente sono stati proposti monoidi inversi come modelli per sistemi reali con un’operazione “undo” [D].
Le >>>