EUVIMEDEUVIMED entdecken
Crossref

All about unambiguous polynomial closure

Thomas Place, Marc Zeitoun

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →