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.
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.