BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Vesa Halava appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that there exists a fixed recursive function $e$ such that for all functions $h\colon \mathbb{N}\to \mathbb{N}$, there exists an injective function $c_h\colon \mathbb{N}\to \mathbb{N}$ such that $c_h(h(n))=e(c_h(n))$, i.e., $h=c_h^{-1}ec_h$.
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 $Σ_2^0$ 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.
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.
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, and he proved that the problem is undecidable. In this article we follow the steps of Post, and give another, simpler and more straightforward proof of the undecidability of the problem using the same source of reduction as Post original did, namely, the Post Normal Systems.
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).
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.