All about unambiguous polynomial closure
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910327587733504 |
|---|---|
| author | Place, Thomas Zeitoun, Marc |
| author_facet | Place, Thomas Zeitoun, Marc |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_12703 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | All about unambiguous polynomial closure Place, Thomas Zeitoun, Marc Formal Languages and Automata Theory 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. |
| title | All about unambiguous polynomial closure |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2205.12703 |