Milan Seminar on Automata and Formal Languages

Recent results about Sakoda and Sipser problem

In the framework of the "Milan Seminar on Automata and Formal Languages" series, which provides monthly seminars at UniversitÓ di Milano, UniversitÓ di Milano-Bicocca and Politecnico di Milano, on Thursday, October 20th at 15:30, in the Meeting Room of the DSI (first floor) at the DSI-DICO, Comelico 39, in Milan, Giovanni Pighizzini (UniversitÓ di Milano) will speak about "Recent results about Sakoda and Sipser problem".

It is known from theory that the ability of moving the input head of finite state automata does not impact on the expressive power of the formalism. Indeed such models, called two-way, both in the deterministic and non-deterministic versions, define the class of regular languages. In 1978 Sakoda and Sipser proposed the still open question of the cost in term of numer of states of optimal simulation of non-deterministic two-way automata through two-way deterministic ones. This seminar will present some recent results on the problem and some related issues.