Decision Problems on Copying and Shuffling

Issue title: Codes, Graphs, Coverings, and Identification: Special Issue Honoring the 60-th Birthday of Professor Iiro Honkala

Guest editors: Vesa Halava, Jarkko Kari and Tero Laihonen

Article type: Research Article

Authors: Halava, Vesa^{a; *; †} | Harju, Tero^b | Nowotka, Dirk^c | Sahla, Esa^d

Affiliations: [a] Department of Mathematics and Statistics, University of Turku, Finland. [email protected] | [b] Department of Mathematics and Statistics, University of Turku, Finland. [email protected] | [c] Department of Computer Science, Kiel University, Germany. [email protected] | [d] Department of Mathematics and Statistics, University of Turku, Finland. [email protected]

Correspondence: [†] Address for correspondence: Department of Mathematics and Statistics, University of Turku, Finland.

Note: [*] Supported by emmy.network foundation under the aegis of the Fondation de Luxembourg.

Abstract: 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: Regular language, linear context-free language, shuffle, marked copy, reverse copy, membership problem

DOI: 10.3233/FI-242182

Journal: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 269-284, 2024