Descrizione
Nell’ambito del settore dell’Informatica Teorica l’attività di ricerca si è articolata su tre temi principali:
- Statistiche di pattern
Si tratta di valutare il numero di occorrenze di pattern (motivi significativi) all’interno di parole generate a caso secondo opportuni modelli probabilistici. Questa tematica trova motivazioni in vari ambiti di ricerca tra i quali i linguaggi formali, il riconoscimento di pattern, la bioinformatica e in particolare l’analisi di sequenze di dna. I risultati raggiunti e gli obbiettivi di indagine attuali riguardano le distribuzioni limite di tali statistiche, le loro proprietà di limite locale e di large deviations [1,2,4,5,6]. - Algoritmi di riconoscimento di linguaggi traccia
I linguaggi traccia sono insiemi di stringhe caratterizzati da relazioni di commutazione parziale tra le lettere, introdotti in letteratura per studiare le proprietà di modelli di calcolo parallelo. In questo ambito temi specifici affrontati riguardano l’analisi probabilistica di algoritmi per il riconoscimento di linguaggi traccia regolari e liberi da contesto [3]. - Problemi di clustering
Si tratta di problemi di ottimizzazione per determinare una partizione di un insieme finito di punti in un dato spazio che minimizzi una opportuna distanza tra i punti stessi. Questi problemi sono fondamentali in molti settori di ricerca di area informatica e matematica (data mining, pattern recognition, analisi delle immagini, bioinformatica, apprendimento automatico, analisi statistica di dati). Obiettivi specifici in questo contesto sono stati la determinazione delle condizioni che rendono difficili (NP-hard) i problemi e la progettazione di algoritmi efficienti quando il problema è risolubile in tempo polinomiale [7,8,9].
Pubblicazioni
[1] M. Goldwurm, M. Vignati, Large deviation properties of pattern statistics in primitive rational models, Proceedings ICTCS 2023, Italian Conference on Theoretical Computer Science, to appear in CEUR-WS.ORG, November 2023 (https://ictcs2023.unipa.it/wp-content/uploads/2023/08/ICTCS2023_PAPER_1908.pdf).
[2] M. Goldwurm, J. Lin, M. Vignati, Local limit properties for symbol statistics in bicomponent rational models, Theoretical Computer Science, vol.970, art. 114051 (https://doi.org/10.1016/j.tcs.2023.114051), August 2023.
[3] C. Banderier, M. Goldwurm, Number of prefixes in trace monoids: clique polynomials and dependency graphs, In "Beyond the Horizon of Computability, Proceedings CIE 2020, Conference on Computability in Europe'', Lecture Notes in Computer Science n.12098, Springer, pp. 251-263, 2020.
[4] M. Goldwurm, L. Lin, M. Vignati, Analysis of symbol statistics in bicomponent rational models, Proceedings 23rd DLT, International Conference on Developments in Language Theory, Lecture Notes in Computer Science n.11647, Springer, pp. 306-318, 2019.
[5] M. Goldwurm, L. Lin, M. Vignati, Saddle Point Method in the analysis of pattern statistics for regular languages, Proceedings 20th ICTCS, Italian Conference on Theoretical Computer Science, CEUR-WS.ORG vol. 2504 (http://ceur-ws.org/Vol-2504/), pp. 78-90, 2019.
[6] M. Goldwurm, L. Lin, M. Vignati, A local limit property for pattern statistics in bicomponent stochastic models, Proceedings 20th DCFS, International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science n.10952, Springer, pp. 114-125, 2018.
[7] M. Goldwurm, J. Lin, F. Saccà, On the complexity of clustering with relaxed size constraints in fixed dimension, Theoretical Computer Science, vol. 717, pp. 37-46, 2018.
[8] J. Lin, A. Bertoni, M. Goldwurm, Exact algorithms for size constrained 2-Clustering in the plane, Theoretical Computer Science, vol. 629, pp. 80-95, 2016.
[9] M. Goldwurm, L. Lin, F. Saccà, On the complexity of clustering with relaxed size constraints, Proceedings 11th AAIM, International Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science n.9778, Springer, pp. 26-38, 2016.
