A1 Refereed original research article in a scientific journal
Decision Problems on Copying and Shuffling
Authors: Halava, Vesa; Harju, Tero; Nowotka, Dirk; Sahla, Esa
Publisher: IOS Press BV
Publication year: 2024
Journal: Fundamenta Informaticae
Journal name in source: Fundamenta Informaticae
Volume: 191
Issue: 3-4
First page : 269
Last page: 284
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-242182
Publication's open availability at the time of reporting: No Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.3233/FI-242182
Self-archived copy’s web address: https://arxiv.org/pdf/2302.06248
Preprint address: https://arxiv.org/abs/2302.06248
Self-archived copy's version: Publisher`s PDF
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.
Keywords:
linear context-free language, marked copy, membership problem, reverse copy, Shuffle
Funding information in the publication:
Supported by emmy.network foundation under the aegis of the Fondation de Luxembourg.
