index) bounds for unambiguous languages

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

Dec. 20, 2017, 2:15 p.m.

Room

room 5050

Title in Polish

No

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.

---