Adding Modular predicates

Speaker(s)

Luc Dartois

Affiliation

LIAFA, Paris

Date

March 26, 2014, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

When considering classes of regular languages, it is a primordial question to be able to determine if a given language belongs to it. Over fragments of logic, this question has been largely studied since McNaughton-Papert [71] and Schutzenberger [65]. The proof methods often involve algebraic characterizations of fragments.

In this talk, we study the behaviour of fragments of logic when we add modular predicates to the signature.
The modular predicates is a set of regular predicates that treats the modular information of positions in the input word.
More precisely, we will first give an algebraic characterization of the adding of modular predicates.
We will then discuss particular cases where this characterization leads to the decidability of the definability problem.
This talk does not require any previous knowledge on algebra and we will recall any algebraic notion used.

---