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.

---