| Summary: | 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.
|
|---|