moteur de recherche

Séminaire Algo - Nathan Grosshans
Séminaire Algo - Nathan Grosshans
16-Mar-2021 14:00
Age: 35 days

Nathan Grosshans

Threshold dot-depth one languages

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Abstract: 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, min and max where only existential quantification is allowed.

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

<- Back to: Accueil