Source author record

Vesa Halava

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Formal Languages and Automata Theory Logic in Computer Science math.CO Computer Science and Game Theory

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A recursive function coding number theoretic functions

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$ .

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 $Σ_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.

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.

preprint2014arXiv

Another proof of undecidability for the correspondence decision problem - Had I been Emil Post

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.

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).

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.

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.