Jarkko Kari

Jarkko J. Kari is a Finnish mathematician and computer scientist, known for his contributions to the theory of Wang tiles and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku.^[1]

Biography edit

Kari received his Ph.D. in 1990 from the University of Turku; his dissertation, supervised by Arto Salomaa.^[2]

He married Lila Kari, a later mathematics student at Turku; they divorced, and afterwards Lila Kari became a professor of computer science at the University of Western Ontario in Canada.^[3]

Research edit

An aperiodic set of 13 Wang tiles derived from Kari's research

Wang tiles are unit squares with colored markings on each side; they may be used to tesselate the plane, but only with tiles that have matching colors on adjoining edges. The problem of determining whether a set of Wang tiles forms a valid tessellation is undecidable, and its undecidability rests on finding sets of Wang tiles that can only tesselate the plane aperiodically, in such a way that no translation of the plane is a symmetry of the tiling. The first set of aperiodic Wang tiles found, by Robert Berger, had over 20,000 different tiles in it. Kari reduced the size of this set to only 14, by finding a set of tiles that (when used to tile the plane) simulates the construction of a Beatty sequence by Mealy machines.^[4] The same approach was later shown to lead to aperiodic sets of 13 tiles, the minimum known.^[5] Kari has also shown that the Wang tiling problem remains undecidable in the hyperbolic plane,^[6] and has discovered sets of Wang tiles with additional mathematical properties.^[7]

Kari has also used the Wang tiling problem as the basis of proofs that several algorithmic problems in the theory of cellular automata are undecidable. In particular, in his thesis research, he showed that it is undecidable to determine whether a given cellular automaton rule in two or more dimensions is reversible.^[8] For one-dimensional cellular automata, reversibility is known to be decidable, and Kari has provided tight bounds on the size of the neighborhood needed to simulate the reverse dynamics of reversible one-dimensional automata.^[9]

References edit

^ Staff profile Archived 2008-12-05 at the Wayback Machine, U. Turku mathematics department, retrieved 2011-09-09.
^ Jarkko Kari at the Mathematics Genealogy Project
^ Hamalainen, Anna-Liisa (December 1992), "Tytto joka haluaa kaiken" (PDF), Kodin Kuvalehti (in Finnish): 22–24.
^ Kari, Jarkko (1996), "A small aperiodic set of Wang tiles", Discrete Mathematics, 160 (1–3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR 1417578.
^ Culik, Karel; Kari, Jarkko (1997), "On aperiodic sets of Wang tiles", Foundations of Computer Science: Potential — Theory — Cognition, Lecture Notes in Computer Science, vol. 1337, Springer, pp. 153–162, doi:10.1007/BFb0052084.
^ Kari, Jarkko (2007), "The tiling problem revisited", Proceedings of the 5th International Conference on Machines, Computations, and Universality (MCU 2007), Lecture Notes in Computer Science, vol. 4664, Springer, pp. 72–79, doi:10.1007/978-3-540-74593-8_6.
^ Kari, J.; Papasoglu, P. (1999), "Deterministic aperiodic tile sets", Geometric and Functional Analysis, 9 (2): 353–369, doi:10.1007/s000390050090, MR 1692474.
^ Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, vol. 45, pp. 379–385, doi:10.1016/0167-2789(90)90195-U, MR 1094882.
^ Czeizler, Eugen; Kari, Jarkko (2007), "A tight linear bound on the synchronization delay of bijective automata", Theoretical Computer Science, 380 (1–2): 23–36, doi:10.1016/j.tcs.2007.02.052, MR 2330639.