Thomas Place ; Marc Zeitoun - All about unambiguous polynomial closure

theoretics:9932 - TheoretiCS, January 10, 2024, Volume 2 -
All about unambiguous polynomial closureArticle

Authors: Thomas Place 1; Marc Zeitoun ORCID1

  • 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.

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
    Source : HAL
  • DÉfis pour la Logique, les Transducteurs et les Automates; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

Consultation statistics

This page has been seen 152 times.
This article's PDF has been downloaded 61 times.