Threshold dot-depth one languages.

22 février 2021

Nathan Grosshans (Theoretische Informatik / Komplexe Systeme, Universität Kassel)

Dot-depth one languages are regular languages for which membership of words
basically depends on the sequences of factors they contain. This class of
languages does also correspond to the Boolean closure of the fragment of first
order logic with successor where only existential quantification is allowed.

I this talk, I will present a new class of regular languages that is a
restriction of the class of dot-depth one languages where factor-detection
only works up to a certain threshold. The main motivation behind its
definition is to capture the effect of intersecting the class of dot-depth one
languages with another well-known class of languages: the one of unambiguous
polynomials. I shall explain why considering such a new class is interesting,
give some properties of it and establish its links with other classes of
languages. I will finish with some research avenues suggested by my work on
threshold dot-depth one languages.