Nie jesteś zalogowany | Zaloguj się

Choice on thin trees and unambiguity

Prelegent(ci)
Michał Skrzypczak
Afiliacja
Uniwersytet Warszawski
Termin
17 października 2012 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

During the talk I will almost provide a decidable characterisation of strongly unambiguous languages - regular languages of infinite trees L such that both L and its complement can be recognised by an unambiguous automaton. It turns out that what remains for the characterisation to hold is a new conjecture:

  There is no MSO definable choice function on thin trees

This statement can be seen as an extension of the classical choice problem, solved negatively by Gurevich and Shelah.