论文标题
语言家族的半线性
Semilinearity of Families of Languages
论文作者
论文摘要
开发了一种技术，可以创建仅半线性语言的新的和通用的语言家族，并且显示家庭仅包含半线性语言。结果表明，对于半线性完整三重奏的语言家族，最小的完整AFL包含L，在NCM中与语言的交集（其中NCM是NFAS所接受的语言家族）也被NFAS增强的语言家族，也是半线性的。如果这些关闭特性有效，这也立即意味着这些普通家庭的会员资格，空虚和无限性的可决定性。从一般技术中，给出了新的语法系统，这些系统是众所周知的半线性完整三重奏家族的扩展，因此暗示这些扩展只能描述半线性语言。这也意味着新系统的积极可决定性属性。还给出了新家庭的一些特征。
Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families L that are semilinear full trios, the smallest full AFL containing L that is also closed under intersection with languages in NCM (where NCM is the family of languages accepted by NFAs augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given.
