Seminario Milanese su Automi e Linguaggi Formali

Risultati recenti intorno al problema di Sakoda e Sipser

Nell’ambito dell’iniziativa "Seminario Milanese su Automi e Linguaggi Formali", che prevede seminari mensili a rotazione presso l'Università di Milano, l'Università di Milano-Bicocca e il Politecnico, giovedì 20 ottobre alle 15:30, Giovanni Pighizzini (Università degli Studi di Milano) terrà nella Sala Riunioni del DSI (I piano) presso il DSI-DICO in via Comelico 39, a Milano, il primo incontro dal titolo: “Risultati recenti intorno al problema di Sakoda e Sipser”.

Abstract:
E' ben noto che la possibilità di muovere la testina di input in entrambe le direzioni non aumenta la capacità riconoscitiva degli automi a stati finiti.
Infatti i modelli così 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 è tuttora aperta. Nel seminario verranno presentati alcuni risultati recenti riguardanti questo problema, tra cui relazioni con la questione aperta in complessità strutturale dell'uguaglianza tra le classi L e NL dei linguaggi accettati in spazio logaritmico da macchine di Turing deterministiche e non deterministiche.