Decision Problems on Copying and Shuffling

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

Publisher: IOS Press BV

: 2024

: Fundamenta Informaticae

: 191

: 3-4

: 269

: 284

: 1875-8681

DOI: https://doi.org/10.3233/FI-242182(external)

: https://doi.org/10.3233/FI-242182(external)

: https://arxiv.org/pdf/2302.06248(external)

: https://arxiv.org/abs/2302.06248(external)

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.

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