A robust class of regular languages
Antonio Cano Gómez, Jean-Éric Pin · 2010
Abstract. In this survey paper, we present known results and open questions on a proper subclass of the class of regular languages. This class, denoted by W, is especially robust: it is closed under union, intersection, product, shuffle, left and right quotients, inverse of morphisms, length preserving morphisms and commutative closure. It can be defined as the largest positive variety of languages not containing the language (ab) ∗. It admits a nontrivial algebraic characterization in terms of finite ordered monoids, which implies that W is decidable: given a regular language, one can effectively decide whether or not it belongs to W. We propose as a challenge to find a constructive description and a logical characterization of W. Warning. In this paper, square brackets are used as a substitute to “respectively” to gather several definitions [properties] into a single one. The search for robust classes of regular languages is an old problem of automata theory, which occurs in particular in the study of regular model checking