Choice on thin trees and unambiguity

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

Oct. 17, 2012, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---