Bruno Guillon (University of Milan, Italy)

Two-way nondeterministic transducers

Abstract: We study binary relations on words, namely transductions, that are computed by different kinds of transducers, beyond the rational transductions. Our main focus is the class of transductions that are realized by two-way nondeterministic transducers. We discuss two approaches to describe nonfunctional transductions realized by two-way transducers. The first approach is algebraic. We introduce natural operators that mimic the abilities of two-way transducers. These operations are sufficient to capture some families of transductions realized by restricted versions of transducers, such as sweeping or unary two-way transducers. The second approach is obtained by enriching the semantics of transducers. We consider transductions with origin information, that intuitively says which output position depends on which input position. We briefly discuss how this enriched semantics helps in recovering some decidability results, and we present other classes of nonfunctional transductions that can be characterized through this information.

José Sempere (Technical University of Valencia, Spain)

On the application of Watson-Crick finite automata for the resolution of bioinformatic problems

Abstract: In this talk, we will show some cases of application of the Watson-Crick finite automata for the prediction and annotation of genomic sequences. We will see how the double tape structure together with the complementarity relationship are efficiently adapted to the DNA / RNA / protein structure for the annotation of structural and functional motifs. We will also see how to approach the phase of machine learning in these models using techniques of reduction to the classical classes of regular, even linear and linear languages. Finally, we will provide some results obtained from our approach to the resolution of genomic annotation problems with real data.