All about unambiguous polynomial closure
TheoretiCS · 2024
DOI: 10.46298/theoretics.23.11 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von Thomas Place und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref). Gefördert von: French National Research Agency.
Abstract (Originalsprache)
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.
Förderung
- French National Research Agency
Zitieren
APA
Place, T., & Zeitoun, M. (2024). All about unambiguous polynomial closure. TheoretiCS. https://doi.org/10.46298/theoretics.23.11
Vancouver
Place T, Zeitoun M. All about unambiguous polynomial closure. TheoretiCS. 2024. doi:10.46298/theoretics.23.11
BibTeX
@article{Place2024,
author = {Place, Thomas and Zeitoun, Marc},
title = {All about unambiguous polynomial closure},
journal = {TheoretiCS},
year = {2024},
doi = {10.46298/theoretics.23.11}
}
EUVIMED