Decision Problems on Copying and Shuffling

: Halava, Vesa; Harju, Tero; Nowotka, Dirk; Sahla, Esa

Publisher: IOS Press BV

: 2024

Fundamenta Informaticae

: Fundamenta Informaticae

: 191

: 3-4

: 269

: 284

: 1875-8681

DOI: https://doi.org/10.3233/FI-242182

: https://doi.org/10.3233/FI-242182

: https://arxiv.org/pdf/2302.06248

: https://arxiv.org/abs/2302.06248

We study decision problems of the form: given a regular or linear context-free language L, is there a word of a given fixed form in L, where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.

linear context-free language, marked copy, membership problem, reverse copy, Shuffle

:
Supported by emmy.network foundation under the aegis of the Fondation de Luxembourg.