Concatenation hierarchies are natural classifications of regular languages. All such hierarchies are built through the same construction process: one starts from an initial, specific class of languages (the basis) and builds new levels using two generic operations. Concatenation hierarchies have gathered a lot of interest since the early 70s, notably thanks to an alternate logical definition: each concatenation hierarchy can be defined as the quantification alternation hierarchy within a variant of first-order logic over words (while the hierarchies differ by their bases, the variants differ by their set of available predicates). Our goal is to understand these hierarchies. A typical approach is to look at two decision problems: membership and separation. In the paper we are interested in the latter, which is more general. For a class of languages C, C-separation takes two regular languages as input and asks whether there exists a third one in C including the first one and disjoint from the second one. Settling whether separation is decidable for the levels within a given concatenation hierarchy is among the most fundamental and challenging questions in formal language theory. In all prominent cases, it is open, or answered positively for low levels only. Recently, a breakthrough was made using a generic approach for a specific kind of hierarchies: those with a finite basis. In this case. separation is always decidable for levels 1/2. 1 and 3/2. Our main theorem is similar but independent: we consider hierarchies with possibly infinite bases, but that contain only group languages. An example is the group hierarchy introduced by Pin and Margolis: its basis consists of all group languages. Another example is the quantifier alternation hierarchy of first-order logic with modular predicates FO( <;, MOD): its basis consists of the languages that count the length of words modulo some number. Using a generic approach, we show that for any such hierarchy, if separation is decidable for the basis, then it is decidable as well for levels 1/2, 1 and 3/2 (we actually solve a more general problem called covering). This complements the aforementioned result nicely: all bases considered in the literature are either finite or made of group languages. Thus, one may handle the lower levels of any prominent hierarchy in a generic way.

@inproceedings{paperbot5028,
  title = {Separation and covering for group based concatenation hierarchies},
  author = {Thomas Place and Marc Zeitoun},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785655}
}