16 citations · 31 across the 15 of their papers we have counts for
5 papers · 1 filter
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…
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…
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More
Julien Cassaigne, Vesa Halava, Tero Harju +1
We study the decidability of three well-known problems related to integer matrix multiplication: Mortality (M), Zero in the Left-Upper Corner (Z), and Zero in the Right-Upper Corne…
Square-Free Shuffles of Words
Tero Harju, Mike Müller
Let $u \shuffle v$ denote the set of all shuffles of the words and . It is shown that for each integer there exists a square-free ternary word of length s…
Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture
Tero Harju, Dirk Nowotka
The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this paper. Consider a finite word w of length n. We call a word b…