Risultati recenti intorno al problema di Sakoda e Sipser

Giovanni Pighizzini (Università degli Studi di Milano)

giovedì 20 ottobre 2011 - 15.30 Sala Riunioni del DSI (I piano)

slides

 

Abstract:

E' ben noto che la possibilita' di muovere la testina di input in entrambe le direzioni non aumenta la capacita' riconoscitiva degli automi a stati finiti. Infatti i modelli cosi' ottenuti, detti automi two-way, caratterizzano sia nella versione deterministica che in quella non deterministica la classe dei linguaggi regolari.

Nel 1978 Sakoda e Sipser hanno posto il problema del costo, in termini di stati, della simulazione ottimale degli automi two-way non deterministici mediante automi two-way deterministici, congetturando che esso sia esponenziale. Nonostante i numerosi tentativi, la questione e' tuttora aperta.

Nel seminario verrano presentati alcuni risultati recenti riguardanti questo problema, tra cui relazioni con la questione aperta in complessita' strutturale dell'uguaglianza tra le classi L e NL dei linguaggi accettati in spazio logaritmico da macchine di Turing deterministiche e non deterministiche.