BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jarkko Kari

Jarkko Kari appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.DSFormal Languages and Automata TheoryEmerging Technologiescond-mat.stat-mechmath-phmath.GRmath.MPnlin.CG

Catalog footprint

What is connected

14works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

14 published item(s)

preprint2023arXiv

Expansivity and periodicity in algebraic subshifts

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.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On forced periodicity of perfect colorings

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.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On perfect coverings of two-dimensional grids

We study perfect multiple coverings in translation invariant graphs with vertex set $\mathbb{Z}^2$ using an algebraic approach. In this approach we consider any such covering as a two-dimensional binary configuration which we then express as a two-variate formal power series. Using known results, we conclude that any perfect multiple covering has a non-trivial periodizer, that is, there exists a non-zero polynomial whose formal product with the power series presenting the covering is a two-periodic configuration. If a non-trivial periodizer has line polynomial factors in at most one direction, then the configuration is known to be periodic. Using this result, we find many setups where perfect multiple coverings of infinite grids are necessarily periodic. We also consider some algorithmic questions on finding perfect multiple coverings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Decidability and Periodicity of Low Complexity Tilings

In this paper we study colorings (or tilings) of the two-dimensional grid $\mathbb{Z}^2$. A coloring is said to be valid with respect to a set $P$ of $n\times m$ rectangular patterns if all $n\times m$ sub-patterns of the coloring are in $P$. A coloring $c$ is said to be of low complexity with respect to a rectangle if there exist $m,n\in\mathbb{N}$ and a set $P$ of $n\times m$ rectangular patterns such that $c$ is valid with respect to $P$ and $|P|\leq nm$. Open since it was stated in 1997, Nivat's conjecture states that such a coloring is necessarily periodic. If Nivat's conjecture is true, all valid colorings with respect to $P$ such that $|P|\leq mn$ must be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat's conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle.\\ After that, we prove that the $nm$ bound is multiplicatively optimal for the decidability of the domino problem, as for all $\varepsilon>0$ it is undecidable to determine if there exists a valid coloring for a given $m,n\in \mathbb{N}$ and set of rectangular patterns $P$ of size $n\times m$ such that $|P|\leq (1+\varepsilon)nm$. We prove a slightly better bound in the case where $m=n$, as well as constructing aperiodic SFTs of pretty low complexity.\\ This paper is an extended version of a paper published in STACS 2020.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Addendum to "Tilings problems on Baumslag-Solitar groups"

In our article in MCU'2013 we state the the Domino problem is undecidable for all Baumslag-Solitar groups $BS(m,n)$, and claim that the proof is a direct adaptation of the construction of a weakly aperiodic subshift of finite type for $BS(m,n)$ given in the paper. In this addendum, we clarify this point and give a detailed proof of the undecidability result. We assume the reader is already familiar with the article in MCU'2013.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Algebraic Geometric Approach to Nivat's Conjecture

We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape $D$ in the configuration is at most the size $|D|$ of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes $D$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finite generating sets for reversible gate sets under general conservation laws

It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every permutation of $\{0,1\}^n$ can be implemented as a composition of these gates. Since every bit operation that does not use all of the bits performs an even permutation, we need to use at least one auxiliary bit to perform every permutation, and it is known that one bit is indeed enough. Without auxiliary bits, all even permutations can be implemented. We generalize these results to non-binary logic: For any finite set $A$, a finite gate set can generate all even permutations of $A^n$ for all $n$, without any auxiliary symbols. This directly implies the previously published result that a finite gate set can generate all permutations of $A^n$ when the cardinality of $A$ is odd, and that one auxiliary symbol is necessary and sufficient to obtain all permutations when the cardinality of $A$ is even. We also consider the conservative case, that is, those permutations of $A^n$ that preserve the weight of the input word. The weight is the vector that records how many times each symbol occurs in the word or, more generally, the image of the word under a fixed monoid homomorphism from $A^*$ to a commutative monoid. It turns out that no finite conservative gate set can, for all $n$, implement all conservative even permutations of $A^n$ without auxiliary bits. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of $A^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strongly Universal Reversible Gate Sets

It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every permutation of $\{0,1\}^n$ can be implemented as a composition of these gates. Since every bit operation that does not use all of the bits performs an even permutation, we need to use at least one auxiliary bit to perform every permutation, and it is known that one bit is indeed enough. Without auxiliary bits, all even permutations can be implemented. We generalize these results to non-binary logic: If $A$ is a finite set of odd cardinality then a finite gate set can generate all permutations of $A^n$ for all $n$, without any auxiliary symbols. If the cardinality of $A$ is even then, by the same argument as above, only even permutations of $A^n$ can be implemented for large $n$, and we show that indeed all even permutations can be obtained from a finite universal gate set. We also consider the conservative case, that is, those permutations of $A^n$ that preserve the weight of the input word. The weight is the vector that records how many times each symbol occurs in the word. It turns out that no finite conservative gate set can, for all $n$, implement all conservative even permutations of $A^n$ without auxiliary bits. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of $A^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Algebraic Geometric Approach to Nivat's Conjecture

We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape D in the configuration is at most the size |D| of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes D.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Statistical Mechanics of Surjective Cellular Automata

Reversible cellular automata are seen as microscopic physical models, and their states of macroscopic equilibrium are described using invariant probability measures. We establish a connection between the invariance of Gibbs measures and the conservation of additive quantities in surjective cellular automata. Namely, we show that the simplex of shift-invariant Gibbs measures associated to a Hamiltonian is invariant under a surjective cellular automaton if and only if the cellular automaton conserves the Hamiltonian. A special case is the (well-known) invariance of the uniform Bernoulli measure under surjective cellular automata, which corresponds to the conservation of the trivial Hamiltonian. As an application, we obtain results indicating the lack of (non-trivial) Gibbs or Markov invariant measures for "sufficiently chaotic" cellular automata. We discuss the relevance of the randomization property of algebraic cellular automata to the problem of approach to macroscopic equilibrium, and pose several open questions. As an aside, a shift-invariant pre-image of a Gibbs measure under a pre-injective factor map between shifts of finite type turns out to be always a Gibbs measure. We provide a sufficient condition under which the image of a Gibbs measure under a pre-injective factor map is not a Gibbs measure. We point out a potential application of pre-injective factor maps as a tool in the study of phase transitions in statistical mechanical models.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Consistency of multidimensional combinatorial substitutions

Multidimensional combinatorial substitutions are rules that replace symbols by finite patterns of symbols in $\mathbb Z^d$. We focus on the case where the patterns are not necessarily rectangular, which requires a specific description of the way they are glued together in the image by a substitution. Two problems can arise when defining a substitution in such a way: it can fail to be consistent, and the patterns in an image by the substitution might overlap. We prove that it is undecidable whether a two-dimensional substitution is consistent or overlapping, and we provide practical algorithms to decide these properties in some particular cases.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Trace Complexity of Chaotic Reversible Cellular Automata

Delvenne, Kůrka and Blondel have defined new notions of computational complexity for arbitrary symbolic systems, and shown examples of effective systems that are computationally universal in this sense. The notion is defined in terms of the trace function of the system, and aims to capture its dynamics. We present a Devaney-chaotic reversible cellular automaton that is universal in their sense, answering a question that they explicitly left open. We also discuss some implications and limitations of the construction.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Undecidable properties of self-affine sets and multi-tape automata

We study the decidability of the topological properties of some objects coming from fractal geometry. We prove that having empty interior is undecidable for the sets defined by two-dimensional graph-directed iterated function systems. These results are obtained by studying a particular class of self-affine sets associated with multi-tape automata. We first establish the undecidability of some language-theoretical properties of such automata, which then translate into undecidability results about their associated self-affine sets.

0 citations0 reviewsNo code linkedOpen access