论文标题
表征基于小组的串联层次结构中的第一级
Characterizing level one in group-based concatenation hierarchies
论文作者
论文摘要
我们研究了两个常规语言类别的运营商：多项式闭合（POL）和布尔闭合（BOOL）。我们将这些运算符应用于G group语言G及其合理的扩展G+，这是包含G和包含空词的Singleton语言的最小布尔代数。这产生了类Bool（POL（G））和BOOL（POL（G+））。这些类构成了普通语言类别的重要类别（称为串联层次结构）的第一级，这些层次是自然逻辑特征。我们介绍了这些类别的通用代数特征。他们暗示人们可以决定是否普通语言属于这样的班级，但前提是输入G类更一般的问题是可以决定的。
We investigate two operators on classes of regular languages: polynomial closure (Pol) and Boolean closure (Bool). We apply these operators to classes of group languages G and to their well-suited extensions G+, which is the least Boolean algebra containing G and the singleton language containing the empty word. This yields the classes Bool(Pol(G)) and Bool(Pol(G+)). These classes form the first level in important classifications of classes of regular languages, called concatenation hierarchies, which admit natural logical characterizations. We present generic algebraic characterizations of these classes. They imply that one may decide whether a regular language belongs to such a class, provided that a more general problem called separation is decidable for the input class G. The proofs are constructive and rely exclusively on notions from language and automata theory.
