16 citations · 19 across the 8 of their papers we have counts for
9 papers
On the Complexity of the Bi-infinite Post Correspondence Problem
Olivier Finkel, Vesa Halava
In the bi-infinite Post Correspondence Problem (PCP), it is asked whether the same bi-infinite word can be constructed correspondingly from a given finite set of pairs of words…
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…
A recursive function coding number theoretic functions
Vesa Halava, Tero Harju, Teemu Pirttimäki
We show that there exists a fixed recursive function such that for all functions , there exists an injective function $c_h\colon \mathbb{N}\to…
Undecidability in Finite Transducers, Defense Systems and Finite Substitutions
Vesa Halava
In this manuscript we present a detailed proof for undecidability of the equivalence of finite substitutions on regular language . The proof is based on the works of L…
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…
Another proof of undecidability for the correspondence decision problem - Had I been Emil Post
Vesa Halava
In 1946 Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264 - 268) defined a famous correspondence decision problem which is nowadays called the Post Correspondence Problem…