论文标题
关于明确的多项式闭合
All about unambiguous polynomial closure
论文作者
论文摘要
我们在语言类别上研究标准运营商：明确的多项式闭合。我们证明，对于满足轻度特性的每类普通语言的C级，其明确的多项式闭合Upol（c）的会员资格问题降低到同一问题。我们还表明，明确的多项式闭合与交替的左和右确定性封闭相吻合。此外，我们证明，如果c是有限的，则分离和覆盖问题对于upol（c）是可决定的。最后，我们概述了使用明确多项式闭合构建的类的通用逻辑特征。
We study a standard operator on classes of languages: unambiguous polynomial closure. We prove that for every class C of regular languages satisfying mild properties, the membership problem for its unambiguous polynomial closure UPol(C) reduces to the same problem for C. We also show that unambiguous polynomial closure coincides with alternating left and right deterministic closure. Moreover, we prove that if additionally C is finite, the separation and covering problems are decidable for UPol(C). Finally, we present an overview of the generic logical characterizations of the classes built using unambiguous polynomial closure.
