An algebraic characterization of relations accepted by two-way unary transducers.
Transducers are extensions of finite automata that are able to output some words on a write-only tape during their computations. Thus they recognize relations on words. It is known that one-way transducers accept exactly the class of rational relations. However two-way transducers strictly extend the computational power of one-way transducers, even in the case of unary (input and output) alphabets (that is alphabets that contain a single letter).
After having introduced the model through a simple examples, I will present a construction, based on crossing sequences, that gives an algebraic characterization of the relations accepted by two-way transducers in the restricted case of unary input and output alphabets. I will then discuss some extensions and corollaries of the result.
Joint work with Christian Choffrut.
speaker: Bruno Guillon (LIAFA, Université Paris Diderot - Paris 7, DI, Università degli studi di Milano)
Where and when: Hall 5, DI via Comelico 39 - Milan - Wednesday 2nd July, 11:00am
Reference people: Prof. Giovanni Pighizzini