FLJul 15, 2024
Decision Problems on Copying and Shuffling
arXiv:2302.06248h-index: 25
AI Analysis
This work addresses fundamental decision problems in formal language theory, providing complexity classifications that are relevant for theoretical computer science.
The paper studies decision problems for regular and linear context-free languages, asking whether a word of a specific form (based on copy, marked copy, and shuffle operations) exists in the language. It provides complexity results, including undecidability for certain combinations.
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.