Dipartimento | Combinatorics on Words Research Lab

1. Mission e Interessi di Ricerca

Il CoWordsLab nasce dal desiderio di unire varie passioni dei docenti e ricercatori intorno alla Combinatoria delle Parole (Combinatorics on Words), disciplina relativamente giovane, che studia parole e linguaggi e che ha implicazioni in varie aree dell’algebra e dell’informatica teorica, diventando cruciale nello studio di algoritmi e codici. Importanti applicazioni sono emerse nello sviluppo dello string processing, recentemente applicato in particolare alla Biologia.

Il laboratorio vuole esprimere, anche a partire dal nome, il desiderio di collaborare nello studio delle parole (Collaboration on Words).

Il gruppo dei docenti che partecipa al laboratorio ha una lunga attività di ricerca e formazione nell’ambito della teoria degli Automi e Linguaggi Formali (Area di ricerca del Dipartimento: Automi e Linguaggi Formali), un'area consolidata dell’informatica che si occupa di problemi al crocevia fra l’informatica teorica, la matematica e le applicazioni. Le principali tematiche oggetto di ricerca sono:

• Automi a stati finiti e linguaggi regolari
• Codici a lunghezza variabile
• Combinatoria delle parole
• Linguaggi bidimensionali

Le linee di ricerca sviluppate abbracciano spesso due o più delle suddette aree. Tuttavia, negli ultimi anni, tali ricerche si sono permeate di nuovi collegamenti in problematiche anche di altri settori. In particolare, sono e sono stati oggetto d'indagine:

• Proprietà strutturali dei codici a lunghezza variabile e loro relazioni con la teoria degli automi e delle serie formali
• Estensioni della teoria dei codici al caso bidimensionale
• Proprietà combinatorie e di riconoscibilità dei linguaggi bidimensionali
• Algoritmi e strutture dati per i linguaggi bidimensionali
• Modelli computazionali ispirati dalla biologia (Sistemi splicing)
• Applicazioni della teoria dei sistemi splicing alla composizione musicale
• Applicazioni della combinatoria delle parole alla bioinformatica, alla compressione dati e alla progettazione di strutture dati efficienti
• Analisi e sperimentazioni di algoritmi per l’overlap e l’assemblaggio di sequenze biologiche, anche utilizzando tecniche di combinatoria delle parole
• Applicazione di tecniche combinatorie per lo sviluppo di tool di Machine Learning e Deep Learning per classificazione di sequenze biologiche e predizione genica.

In questi anni sono stati coinvolti, nelle varie attività di ricerca, ospiti, borsisti e assegnisti, ed il gruppo è stato costantemente affiancato da un elevato numero di tesisti, triennali e magistrali, impegnati in attività teoriche e sperimentazioni software su grandi quantità di dati reali (con particolare riferimento alle linee di ricerca applicative descritte sopra).

1.1 Collaborazioni

prof.ssa Valérie Berthé (CNRS, Université Paris Diderot, Francia)

prof.ssa Paola Bonizzoni (Università di Milano Bicocca)

prof.ssa Giuseppa Castiglione (Università di Palermo)

dott.ssa Manuela Flores (Università del Molise)

prof.ssa Dora Giammarresi (Università di Roma Tor Vergata)

prof.ssa Maria Madonia (Università di Catania)

prof.ssa Sabrina Mantaci (Università di Palermo)

prof. Dominique Perrin (Université Paris Est, Francia)

prof. Antonio Restivo (Università di Palermo)

prof. Christophe Reutenauer (Université du Québec à Montréal, Canada)

prof.ssa Giuseppina Rindone (Université Paris Est)

prof.ssa Raffaella RIzzi (Università di Milano Bicocca)

prof.ssa Carla Selmi (Université de Rouen, Francia)

2. Categorie ISI WEB of Science di Riferimento

• Computer Science, Theory & Methods;
• Computer Science, Artificial Intelligence;
• Mathematical & Computational Biology;
• Mathematics, Interdisciplinary Applications;
• Computer Science, Information Systems;
• Computer Science, Interdisciplinary Applications;

3. Categorie ERC di Riferimento

• PE1_15 Discrete mathematics and combinatorics;
• PE1_16 Mathematical aspects of computer science;
• PE1_18 Scientific computing and data processing;
• PE1_20 Application of mathematics in sciences;
• PE1_21 Application of mathematics in industry and society;
• PE6_4 Theoretical computer science, formal methods, and quantum computing;
• PE6_7 Artificial intelligence, intelligent systems, multi agent systems;
• PE6_11 Machine learning, statistical data processing and applications using signal processing (e.g., speech, image, video);
• PE6_13 Bioinformatics, biocomputing, and DNA and molecular computation;
• LS2_12 Bioinformatics.

4. Settori Scientifico-Disciplinari di Riferimento

INFO - 01/A (INFORMATICA)

5. Didattica

Il laboratorio, oltre ad attività di ricerca, svolge anche attività di supervisione tesi e tirocini per studenti dei corsi della Laurea Triennale e Magistrale in Informatica, interessati allo sviluppo di modelli e applicazioni che rientrano negli ambiti di ricerca elencati in Sezione 2, promuove e supporta altresì la crescita scientifica e culturale di ricercatori e docenti.

L’impegno didattico del gruppo è concentrato sul Corso di Laurea in Informatica, precisamente negli insegnamenti di Metodi Matematici per l’Informatica, Progettazione di Algoritmi, Elementi di Teoria della Computazione. Inoltre alcune aree di ricerca sono oggetto dell’insegnamento Strumenti Formali per la Bioinformatica, per il Corso di Laurea Magistrale, attivato dall’anno acc. 2022-2023, e che prevede attività teorica e sperimentale per la preparazione del progetto d’esame. Un numero sempre crescente di studenti lo inserisce nel piano di studi, segno dell’interesse per questa tematica.

5.1 ITACPC

Fra le iniziative portate avanti da alcuni membri del laboratorio, ricordiamo la partecipazione a ITACPC (Italian Collegiate Programming Contest) a partire dalla sua seconda edizione nel 2023. Si tratta di una competizione di programmazione tra squadre di università su scala nazionale che si ispira alla competizione ICPC, che invece è su scala globale. Le squadre lavorano per risolvere il maggior numero di problemi del mondo reale, promuovendo la collaborazione, la creatività, l'innovazione e la capacità di lavorare sotto pressione. L’adesione degli studenti alle varie edizioni è sempre più numerosa e soddisfacente.

6. Sito Web

CoWordsLab.unisa.it

7. Contatti

• Marcella Anselmo, manselmo@unisa.it
• Clelia De Felice, cdefelice@unisa.it
• Rocco Zaccagnino, rzaccagnino@unisa.it
• Rosalba Zizza, rzizza@unisa.it