You are not logged in | Log in

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.