2 papers
cs.FL2023
Decision Problems on Copying and Shuffling
Vesa Halava, Tero Harju, Dirk Nowotka +1
We study decision problems of the form: given a regular or linear context-free language , is there a word of a given fixed form in , where given fixed forms are based on word…
cs.DM2021
On Bi-infinite and Conjugate Post Correspondence Problems
Olivier Finkel, Vesa Halava, Tero Harju +1
We study two modifications of the Post Correspondence Problem (PCP), namely 1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two give…