Mikołaj Bojańczyk, University of Warsaw, Poland

Finite-state polynomial computation 

For powerful computational models, such as Turing machines, or polynomial time Turing machines, it does not make much of a difference if one considers string-to-Boolean functions (i.e. languages) or string-to-string functions.  For finite-state models, such as finite automata, there is a difference, and hence the study of string-to-string functions computed by automata, also known as transducers, is its own field.  
Early models of transducers where minor variations on automata. An example of such a model is a Mealy machine, which is a deterministic finite automaton that produces one output letter in each transition. In time, transducer models have grown in sophistication, and now they are powerful enough to resemble programming languages, with features such as loops or higher-order functions. At the same time, because they are “finite-state”, the halting problem remains decidable. An appealing part of transducer theory is that, similarly to the language case, the important transducer models have many equivalent characterisations, using automata, logics, algebra, etc. 
In this talk, I would like to discuss such transducer models, with an emphasis on those which compute string-to-string functions of polynomial growth. 

_____________________________________________

Paola Bonizzoni, University of Milano-Bicocca, Italy

Graph Pangenomics: a journey from Applications to Theory and back…

Graph pangenomics is a new emerging field within genome informatics that departs from the conventional notion of a reference genome as a linear sequence. Instead, it embraces the paradigm of a sequence graph, referred to as a pangenome, to model variations across  multiple evolutionarily related genomes. Establishing the theoretical foundations of graph pangenomics offers a remarkable opportunity for computer science researchers engaged in topics related to various aspects of sequence and graph theory. Indeed, many recent advancements in this field remain firmly grounded in established literature on combinatorics on words, formal languages and space efficient data structures. During my talk, I will embark on a journey that starts with computational problems inspired  by applications in graph pangenomics. I will  then delve into theoretical concepts before circling  back  to the original challenges by presenting relevant solutions.