A recursive function coding number theoretic functions
We show that there exists a fixed recursive function such that for all functions , there exists an injective function such that , i.e., .
Source author record
Tero Harju
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
13works
7topics
4close collaborators
Published work
13 publications
preprint2022arXiv
On Bi-infinite and Conjugate Post Correspondence Problems
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 given morphisms agree on it, and 2) the conjugate version, where we require the images of a solution for two given morphisms are conjugates of each other. For the bi-infinite PCP we show that it is in the class Σ20 of the arithmetical hierarchy and for the conjugate PCP we give an undecidability proof by reducing it to the word problem for a special type of semi-Thue systems.
Open access
preprint2022arXiv
On the Self Shuffle Language
The shuffle product \(u\shuffle v\) of two words u and v is the set of all words which can be obtained by interleaving u and v. Motivated by the paper \emph{The Shuffle Product: New Research Directions} by Restivo (2015) we investigate a special case of the shuffle product. In this work we consider the shuffle of a word with itself called the \emph{self shuffle} or \emph{shuffle square}, showing first that the self shuffle language and the shuffle of the language are in general different sets. We prove that the language of all words arising as a self shuffle of some word is context sensitive but not context free. Furthermore, we show that the self shuffle \(w \shuffle w\) uniquely determines w.
Open access
preprint2020arXiv
Disposability in Square-Free Words
We consider words w over the alphabet Σ={0,1,2}. It is shown that there are irreducibly square-free words of all lengths n except 4,5,7 and 12. Such a word is square-free (i.e., it has no repetitions uu as factors), but by removing any one internal letter creates a square in the word.
Open access
preprint2015arXiv
Abelian bordered factors and periodicity
A finite word u is said to be bordered if u has a proper prefix which is also a suffix of u, and unbordered otherwise. Ehrenfeucht and Silberger proved that an infinite word is purely periodic if and only if it contains only finitely many unbordered factors. We are interested in abelian and weak abelian analogues of this result; namely, we investigate the following question(s): Let w be an infinite word such that all sufficiently long factors are (weakly) abelian bordered; is w (weakly) abelian periodic? In the process we answer a question of Avgustinovich et al. concerning the abelian critical factorization theorem.
Open access
preprint2015arXiv
Weighted automata on infinite words in the context of Attacker-Defender games
We consider infinite-state Attacker-Defender games with reachability objectives. The results of the paper are twofold. Firstly we prove a new language-theoretic result for weighted automata on infinite words and show its encoding into the framework of Attacker-Defender games. Secondly we use this novel concept to prove undecidability for checking existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games.
Open access
preprint2014arXiv
On Generating Binary Words Palindromically
We regard a finite word u=u1u2⋯un up to word isomorphism as an equivalence relation on {1,2,…,n} where i is equivalent to j if and only if xi=xj. Some finite words (in particular all binary words) are generated by "{\it palindromic}" relations of the form k∼j+i−k for some choice of 1≤i≤j≤n and k∈{i,i+1,…,j}. That is to say, some finite words u are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function μ(u) defined as the least number of palindromic relations required to generate u. We show that every aperiodic infinite word must contain a factor u with μ(u)≥3, and that some infinite words x have the property that μ(u)≤3 for each factor u of x. We obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast for the Thue-Morse word, we show that the function μ is unbounded.
Open access
preprint2014arXiv
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More
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 Corner (R). Let d and k be positive integers. Define M(k, d x d) as the following special case of the Mortality problem: given a set X of d -by-d integer matrices such that the cardinality of X is not greater than k, decide whether the d-by-d zero matrix belongs to X^+, where X^+ denotes the closure of X under the usual matrix multiplication. In the same way, define the Z(k, d x d) problem as: given an instance X of M(k, d x d) (the instances of Z(k, d x d) are the same as those of M(k, d x d)), decide whether at least one matrix in X^+ has a zero in the left-upper corner. Define R(k, d x d) as the variant of Z(k, d x d) where "left-upper corner" is replaced with "right-upper corner". In the paper, we prove that M(6, 3 x 3), M(4, 5 x 5), M(3, 9 x 9), M(2, 15 x 15), Z(5, 3 x 3), Z(3, 5 x 5), Z(2, 9 x 9), R(6, 3 x 3), R(5, 4 x 4), and R(3, 6 x 6) are undecidable. The previous best comparable results were the undecidabilities of M(7, 3 x 3), M(3, 13 x 13), M(2, 21 x 21), Z(7, 3 x 3), Z(2, 13 x 13), R(7, 3 x 3), and R(2, 10 x 10).
Open access
preprint2013arXiv
On a question of Hof, Knill and Simon on palindromic substitutive systems
In a 1995 paper, Hof, Knill and Simon obtain a sufficient combinatorial criterion on the hull Ω of the potential of a discrete Schrödinger operator which guarantees purely singular continuous spectrum on a generic subset of Ω. In part, this condition requires the existence of infinitely many palindromic factors. In this same paper, they introduce the class P of morphisms f:A∗→B∗ of the form a↦pqa and ask whether every palindromic subshift generated by a primitive substitution arises from morphisms of class P or by morphisms of the form a↦qap where again p and qa are palindromes. In this paper we give a partial affirmative answer to the question of Hof, Knill and Simon: we show that every rich primitive substitutive subshift is generated by at most two morphisms each of which is conjugate to a morphism of class P. More precisely, we show that every rich (or almost rich in the sense of finite defect) primitive morphic word y∈Bω is of the form y=f(x) where f:A∗→B∗ is conjugate to a morphism of class P, and where x is a rich word fixed by a primitive substitution g:A∗→A∗ of class P.
Open access
preprint2013arXiv
Square-Free Shuffles of Words
Let $u \shuffle v$ denote the set of all shuffles of the words u and v. It is shown that for each integer n≥3 there exists a square-free ternary word u of length n such that $u\shuffle u$ contains a square-free word. This property is then shown to also hold for infinite words, i.e., there exists an infinite square-free word u on three letters such that u can be shuffled with itself to produce an infinite square-free word $w \in u \shuffle u$.
Open access
preprint2011arXiv
A new proof for the decidability of D0L ultimate periodicity
We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and Linna.
Open access
preprint2011arXiv
Square-free Walks on Labelled Graphs
A finite or infinite word is called a G-word for a labelled graph G on the vertex set An={0,1,...,n−1} if w=i1i2...ik∈An∗, where each factor ijij+1 is an edge of E, i.e, w represents a walk in G. We show that there exists a square-free infinite G-word if and only if G has no subgraph isomorphic to one of the cycles C3, C4, C5, the path P5 or the claw K1,3. The colour number γ(G) of a graph G=(An,E) is the smallest integer k, if it exists, for which there exists a mapping ϕ:An→Ak such that ϕ(w) is square-free for an infinite G-word w. We show that γ(G)=3 for G=C3,C5,P5, but γ(G)=4 for G=C4,K1,3. In particular, γ(G)≤4 for all graphs that have at least five vertices.
Open access
preprint2008arXiv
Pivots, Determinants, and Perfect Matchings of Graphs
We give a characterization of the effect of sequences of pivot operations on a graph by relating it to determinants of adjacency matrices. This allows us to deduce that two sequences of pivot operations are equivalent iff they contain the same set S of vertices (modulo two). Moreover, given a set of vertices S, we characterize whether or not such a sequence using precisely the vertices of S exists. We also relate pivots to perfect matchings to obtain a graph-theoretical characterization. Finally, we consider graphs with self-loops to carry over the results to sequences containing both pivots and local complementation operations.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.