All about unambiguous polynomial closure

Thomas Place; Marc Zeitoun

doi:10.46298/theoretics.23.11

Thomas Place ; Marc Zeitoun - All about unambiguous polynomial closure

theoretics:9932 - TheoretiCS, January 10, 2024, Volume 2 - https://doi.org/10.46298/theoretics.23.11

All about unambiguous polynomial closureArticle

Authors: Thomas Place ¹; Marc Zeitoun ¹

1 Laboratoire Bordelais de Recherche en Informatique

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.

https://doi.org/10.46298/theoretics.23.11

Source: arXiv.org:2205.12703

Volume: Volume 2

Published on: January 10, 2024

Accepted on: November 6, 2023

Submitted on: August 17, 2022

Keywords: Computer Science - Formal Languages and Automata Theory

Licence: Attribution 4.0 International (CC BY 4.0)

Funding:

Source : HAL