一句话:给出 BPol 算子的通用代数刻画,将高层成员问题归约到覆盖问题,并证明点深度三可判定。
本文研究正则语言类的拼接层级。该层级由基类经布尔多项式闭包 BPol 反复作用生成,判定一个正则语言是否属于给定层级是自动机理论中长期未决的问题;历史上点深层级仅一、二层已知可判定。作者给出 BPol 算子的通用代数刻画,证明当 n≥2 时,第 n 层的成员问题可归约到第 n-1 层的覆盖问题。结合已有覆盖问题结果,得到点深度三以及文献中主要层级第二层成员问题的可判定性,例如模层级和群层级。
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. We give a generic algebraic characterization of the operator BPol. It 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 the main hierarchies of the literature. For instance, we obtain that the levels two in both the modulo hierarchy and the group hierarchy have decidable membership.