6 Search Results for "Kari, Jarkko"

Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.11
Von Neumann Regularity, Split Epicness and Elementary Cellular Automata

Authors: Ville Salo

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
We show that a cellular automaton on a mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that von Neumann regularity is decidable condition, and we decide it for all elementary CA.
Cite as

Ville Salo. Von Neumann Regularity, Split Epicness and Elementary Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 11:1-11:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{salo:OASIcs.AUTOMATA.2021.11,
  author =	{Salo, Ville},
  title =	{{Von Neumann Regularity, Split Epicness and Elementary Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{11:1--11:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.11},
  URN =		{urn:nbn:de:0030-drops-140209},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.11},
  annote =	{Keywords: cellular automata, elementary cellular automata, von Neumann regularity, split epicness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.12
Decidability in Group Shifts and Group Cellular Automata

Authors: Pierre Béaur and Jarkko Kari

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.
Cite as

Pierre Béaur and Jarkko Kari. Decidability in Group Shifts and Group Cellular Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beaur_et_al:LIPIcs.MFCS.2020.12,
  author =	{B\'{e}aur, Pierre and Kari, Jarkko},
  title =	{{Decidability in Group Shifts and Group Cellular Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.12},
  URN =		{urn:nbn:de:0030-drops-127206},
  doi =		{10.4230/LIPIcs.MFCS.2020.12},
  annote =	{Keywords: group cellular automata, group shifts, symbolic dynamics, decidability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.14
Decidability and Periodicity of Low Complexity Tilings

Authors: Jarkko Kari and Etienne Moutot

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this paper we study low-complexity colorings (or tilings) of the two-dimensional grid ℤ². A coloring is said to be of low complexity with respect to a rectangle if there exists m,n∈ℕ such that there are no more than mn different rectangular m× n patterns in it. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. Suppose we are given at most nm rectangular patterns of size n× m. If Nivat’s conjecture is true, one can only build periodic colorings out of these patterns - meaning that if the m× n rectangular patterns of the coloring are among these mn patterns, it must be periodic. The main contribution of this paper proves that there exists at least one periodic coloring build from these patterns. 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. Finally, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. The results also extend to other convex shapes in place of the rectangle.
Cite as

Jarkko Kari and Etienne Moutot. Decidability and Periodicity of Low Complexity Tilings. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kari_et_al:LIPIcs.STACS.2020.14,
  author =	{Kari, Jarkko and Moutot, Etienne},
  title =	{{Decidability and Periodicity of Low Complexity Tilings}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.14},
  URN =		{urn:nbn:de:0030-drops-118752},
  doi =		{10.4230/LIPIcs.STACS.2020.14},
  annote =	{Keywords: Nivat’s conjecture, domino problem, decidability, low pattern complexity, 2D subshifts, symbolic dynamics}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.68
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties

Authors: Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.
Cite as

Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dennunzio_et_al:LIPIcs.MFCS.2019.68,
  author =	{Dennunzio, Alberto and Formenti, Enrico and Grinberg, Darij and Margara, Luciano},
  title =	{{Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.68},
  URN =		{urn:nbn:de:0030-drops-110126},
  doi =		{10.4230/LIPIcs.MFCS.2019.68},
  annote =	{Keywords: Cellular Automata, Symbolic Dynamics, Complex Systems}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2016.4
Tutorial on Cellular Automata and Tilings (Tutorial)

Authors: Jarkko Kari

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Cellular automata (CA) are massively parallel systems where a regular grid of finite symbols is updated according to a synchronous application of the same local update rule everywhere. A closely related concept is that of Wang tiles where a local relation between neighboring symbols determines allowed combinations of symbols in the grid. In this tutorial we start with classical results on cellular automata, such as the Garden-of-Eden theorems, the Curtis-Hedlund-Lyndon-theorem and the balance property of surjective cellular automata. We then discuss Wang tiles and, in particular, the concept of aperiodicity and the undecidability of the domino problem. The domino problem is the decision problem to determine if a given Wang tile set admits any valid tilings of the grid. We relate Wang tiles to cellular automata, and establish a number of undecidability results for cellular automata.
Cite as

Jarkko Kari. Tutorial on Cellular Automata and Tilings (Tutorial). In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kari:LIPIcs.STACS.2016.4,
  author =	{Kari, Jarkko},
  title =	{{Tutorial on Cellular Automata and Tilings}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.4},
  URN =		{urn:nbn:de:0030-drops-57054},
  doi =		{10.4230/LIPIcs.STACS.2016.4},
  annote =	{Keywords: cellular automata, wang tiles, decision problems, dynamics}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.RTA.2013.1
Pattern Generation by Cellular Automata (Invited Talk)

Authors: Jarkko Kari

Published in: LIPIcs, Volume 21, 24th International Conference on Rewriting Techniques and Applications (RTA 2013)

Abstract
A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply by constants 3 and 3/2 in base 6. We discuss the connections of these automata to some difficult open questions in number theory, and we pose several further questions concerning pattern generation in cellular automata.
Cite as

Jarkko Kari. Pattern Generation by Cellular Automata (Invited Talk). In 24th International Conference on Rewriting Techniques and Applications (RTA 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 21, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kari:LIPIcs.RTA.2013.1,
  author =	{Kari, Jarkko},
  title =	{{Pattern Generation by Cellular Automata}},
  booktitle =	{24th International Conference on Rewriting Techniques and Applications (RTA 2013)},
  pages =	{1--3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-53-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{21},
  editor =	{van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2013.1},
  URN =		{urn:nbn:de:0030-drops-40490},
  doi =		{10.4230/LIPIcs.RTA.2013.1},
  annote =	{Keywords: cellular automata, pattern generation, Z-numbers}
}
  • Refine by Author
  • 4 Kari, Jarkko
  • 1 Béaur, Pierre
  • 1 Dennunzio, Alberto
  • 1 Formenti, Enrico
  • 1 Grinberg, Darij
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Models of computation
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Computability

  • Refine by Keyword
  • 3 cellular automata
  • 2 decidability
  • 2 symbolic dynamics
  • 1 2D subshifts
  • 1 Cellular Automata
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2020
  • 1 2013
  • 1 2016
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact