2024/01/29 by Thomas Place, Place, Thomas, Marc Zeitoun +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2401.16195
openalex publication_date 2024/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We look at concatenation hierarchies of classes of regular languages. Each such hierarchy is determined by a single class, its basis: level n is built by applying the Boolean polynomial closure operator (BPol), n times to the basis. A prominent and difficult open question in automata theory is to decide membership of a regular language in a given level. For instance, for the historical dot-depth hierarchy, the decidability of membership is only known at levels one and two. We give a generic algebraic characterization of the operator BPol. This characterization implies that for any concatenation hierarchy, if n is at least two, membership at level n reduces to a more complex problem, called covering, for the previous level, n-1. Combined with earlier results on covering, this implies that membership is decidable for dot-depth three and for level two in most of the prominent hierarchies in the literature. For instance, we obtain that the levels two in both the modulo hierarchy and the group hierarchy have decidable membership.