Name Jarkko Kari | Role Mathematician | |
 | ||
Snakes and cellular automata reductions and inseparability results 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.
Contents
- Snakes and cellular automata reductions and inseparability results jarkko kari
- Biography
- Research
- References
Biography
Kari received his Ph.D. in 1990 from the University of Turku; his dissertation, supervised by Arto Salomaa.
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.
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. The same approach was later shown to lead to aperiodic sets of 13 tiles, the minimum known. Kari has also shown that the Wang tiling problem remains undecidable in the hyperbolic plane, and has discovered sets of Wang tiles with additional mathematical properties.
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. 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.