JKJarkko Kari

Jarkko Kari

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Jarkko Kari has a total of 108 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The group of reversible turing machines: subgroups, generators, and computability

    by Sebastian Barbieri, Jarkko Kari, Ville Salo

    We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and a head carrying a state. These homeomorphisms can only modify the tape at a bounded distance around the head, change the state, and move the head in a bounded way. We study three natural subgroups arising in this model: the group of finite-state automata, which generalizes the topological full groups studied in topological dynamics and the theory of orbit-equivalence; the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates, and the group of elementary Turing machines, which are the machines which are obtained by composing finite-state automata and oblivious Turing machines. We show that both the group of oblivious Turing machines and that of elementary Turing machines are finitely generated, while the group of finite-state automata and the group of reversible Turing machines are not. We show that the group of elementary Turing machines has undecidable torsion problem. From this, we also obtain that the group of cellular automata (more generally, the automorphism group of any uncountable one-dimensional sofic subshift) contains a finitely generated subgroup with undecidable torsion problem. We also show that the torsion problem is undecidable for the topological full group of a full $\mathbb {Z}^d$ -shift on a nontrivial alphabet if and only if $d \geq 2$ .


  • Open Access

    Periodicity and local complexity of Delone sets

    by Pyry Herva, Jarkko Kari

    We study complexity and periodicity of Delone sets by applying an algebraic approach to multidimensional symbolic dynamics. In this algebraic approach, $\mathbb{Z}^d$-configurations $c: \mathbb{Z}^d \to \mathcal{A}$ for a finite set $\mathcal{A} \subseteq \mathbb{C}$ and finite $\mathbb{Z}^d$-patterns are regarded as formal power series and Laurent polynomials, respectively. In this paper we study also functions $c: \mathbb{R}^d \to \mathcal{A}$ where $\mathcal{A}$ is as above. These functions are called $\mathbb{R}^d$-configurations. Any Delone set may be regarded as an $\mathbb{R}^d$-configuration by simply presenting it as its indicator function. Conversely, any $\mathbb{R}^d$-configuration whose support (that is, the set of cells for which the configuration gets non-zero values) is a Delone set can be seen as a colored Delone set. We generalize the concept of annihilators and periodizers of $\mathbb{Z}^d$-configurations for $\mathbb{R}^d$-configurations. We show that if an $\mathbb{R}^d$-configuration has a non-trivial annihilator, that is, if a linear combination of some finitely many of its translations is the zero function, then it has an annihilator of a particular form. Moreover, we show that $\mathbb{R}^d$-configurations with integer coefficients that have non-trivial annihilators are sums of finitely many periodic functions $c_1,\ldots,c_m: \mathbb{R}^d \to \mathbb{Z}$. Also, $\mathbb{R}^d$-pattern complexity is studied alongside with the classical patch-complexity of Delone sets. We point out the fact that sufficiently low $\mathbb{R}^d$-pattern complexity of an $\mathbb{R}^d$-configuration implies the existence of non-trivial annihilators. Moreover, it is shown that if a Meyer set has sufficiently slow patch-complexity growth, then it has a non-trivial annihilator. Finally, a condition for forced periodicity of colored Delone sets of finite local complexity is provided.

  • Open Access

    Preface

    by Daniela Genova, Jarkko Kari

  • Open Access

    On the periodic decompositions of multidimensional configurations

    by Pyry Herva, Jarkko Kari

    We consider $d$-dimensional configurations, that is, colorings of the $d$-dimensional integer grid $\mathbb{Z}^d$ with finitely many colors. Moreover, we interpret the colors as integers so that configurations are functions $\mathbb{Z}^d \to \mathbb{Z}$ of finite range. We say that such function is $k$-periodic if it is invariant under translations in $k$ linearly independent directions. It is known that if a configuration has a non-trivial annihilator, that is, if some non-trivial linear combination of its translations is the zero function, then it is a sum of finitely many periodic functions. This result is known as the periodic decomposition theorem. We prove two different improvements of it. The first improvement gives a characterization on annihilators of a configuration to guarantee the $k$-periodicity of the functions in its periodic decomposition -- for any $k$. The periodic decomposition theorem is then a special case of this result with $k=1$. The second improvement concerns so called sparse configurations for which the number of non-zero values in patterns grows at most linearly with respect to the diameter of the pattern. We prove that a sparse configuration with a non-trivial annihilator is a sum of finitely many periodic fibers where a fiber means a function whose non-zero values lie on a unique line.

  • Open Access

    On Forced Periodicity of Perfect Colorings

    by Pyry Herva, Jarkko Kari

    We study forced periodicity of two-dimensional configurations under certain constraints and use an algebraic approach to multidimensional symbolic dynamics in which d-dimensional configurations and finite patterns are presented as formal power series and Laurent polynomials, respectively, in d variables. We consider perfect colorings that are configurations such that the number of points of a given color in the neighborhood of any point depends only on the color of the point for some fixed relative neighborhood, and we show that by choosing the alphabet suitably any perfect coloring has a non-trivial annihilator, that is, there exists a Laurent polynomial whose formal product with the power series presenting the perfect coloring is zero. Using known results we obtain a sufficient condition for forced periodicity of two-dimensional perfect colorings. As corollaries of this result we get simple new proofs for known results of forced periodicity on the square and the triangular grids. Moreover, we obtain a new result concerning forced periodicity of perfect colorings in the king grid. We also consider perfect colorings of a particularly simple type: configurations that have low abelian complexity with respect to some shape, and we generalize a result that gives a sufficient condition for such configurations to be necessarily periodic. Also, some algorithmic aspects are considered.


  • Open Access

    Expansivity and periodicity in algebraic subshifts

    by Jarkko Kari

    A d-dimensional configuration c : Z^d -> A is a coloring of the d-dimensional infinite grid by elements of a finite alphabet A \subseteq Z. The configuration c has an annihilator if a non-trivial linear combination of finitely many translations of c is the zero configuration. Writing c as a d-variate formal power series, the annihilator is conveniently expressed as a d-variate Laurent polynomial f whose formal product with c is the zero power series. More generally, if the formal product is a strongly periodic configuration, we call the polynomial f a periodizer of c. A common annihilator (periodizer) of a set of configurations is called an annihilator (periodizer, respectively) of the set. In particular, we consider annihilators and periodizers of d-dimensional subshifts, that is, sets of configurations defined by disallowing some local patterns. We show that a (d-1)-dimensional linear subspace S \subseteq R^d is expansive for a subshift if the subshift has a periodizer whose support contains exactly one element of S. As a subshift is known to be finite if all (d-1)-dimensional subspaces are expansive, we obtain a simple necessary condition on the periodizers that guarantees finiteness of a subshift or, equivalently, strong periodicity of a configuration. We provide examples in terms of tilings of Z^d by translations of a single tile.