Dot-depth three, return of the J-class
Thomas Place, Marc Zeitoun · 2024
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. An important and challenging open question in automata theory is deciding if a regular language belongs to a given level. For the historical dot-depth hierarchy, the membership problem is only known to be decidable at levels one and two.