You are not logged in | Log in

index) bounds for unambiguous languages

Speaker(s)
Michał Skrzypczak
Affiliation
Uniwersytet Warszawski
Date
Dec. 20, 2017, 2:15 p.m.
Room
room 5050
Seminar
Seminar Automata Theory

The talk is about the class of regular languages of infinite trees
that can be recognised by unambiguous automata. Although the class is
very natural, its properties are usually non-trivial with many basic
questions unanswered at the moment. I will focus on the following
problem:

Is it the case that all unambiguous languages can be recognised by
alternating automata of bounded parity index (i.e. bounded
complexity)?

For quite some time it was believed that the answer is positive, with
bound (0,1) on the index. Then Hummel gave an example that requires
index (1,2). By further improvements, he managed to reach
approximately up to the intersection of indices (0,2) and (1,3).
However, his inductive techniques were not sufficing to go above this
level. During the talk I will present a new approach that seems to
provide examples requiring arbitrarily high indices. The novelty of
that approach can be stated as moving from inductive to co-inductive
(i.e. ill-founded) construction.