Fiche du document
10 janvier 2024
- handle: 10670/1.l89uxg
- doi: 10.46298/theoretics.23.11
info:eu-repo/semantics/openAccess , info:eu-repo/semantics/openAccess
Sujets proches
Foreign languages LanguagesCiter ce document
Thomas Place et al., « All about unambiguous polynomial closure », Episciences.org, ID : 10.46298/theoretics.23.11
Métriques
Partage / Export
Résumé
We study a standard operator on classes of languages: unambiguous polynomialclosure. We prove that for every class C of regular languages satisfying mildproperties, the membership problem for its unambiguous polynomial closureUPol(C) reduces to the same problem for C. We also show that unambiguouspolynomial closure coincides with alternating left and right deterministicclosure. Moreover, we prove that if additionally C is finite, the separationand covering problems are decidable for UPol(C). Finally, we present anoverview of the generic logical characterizations of the classes built usingunambiguous polynomial closure.