Jarkko J. Kari es un matemático e informático finlandés , conocido por sus contribuciones a la teoría de los mosaicos de Wang y los autómatas celulares . Kari es actualmente profesora en el Departamento de Matemáticas de la Universidad de Turku . [1]
Biografía
Kari recibió su Ph.D. en 1990 de la Universidad de Turku; su disertación, dirigida por Arto Salomaa . [2]
Se casó con Lila Kari , una estudiante de matemáticas posterior en Turku; se divorciaron y luego Lila Kari se convirtió en profesora de informática en la Universidad de Western Ontario en Canadá . [3]
Investigar
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/9/94/Wang_13_tiles.svg/220px-Wang_13_tiles.svg.png)
Los mosaicos Wang son cuadrados unitarios con marcas de colores en cada lado; pueden usarse para teselar el plano, pero solo con mosaicos que tengan colores iguales en los bordes contiguos. El problema de determinar si un conjunto de mosaicos de Wang forma una teselación válida es indecidible , y su indecidibilidad se basa en encontrar conjuntos de mosaicos de Wang que solo puedan teselar el plano de forma aperiódica , de tal manera que ninguna traslación del plano sea una simetría del plano. embaldosado. El primer juego de baldosas aperiódicas de Wang encontradas, por Robert Berger, tenía más de 20.000 baldosas diferentes. Kari redujo el tamaño de este conjunto a solo 14, al encontrar un conjunto de mosaicos que (cuando se usa para colocar el plano en mosaico) simula la construcción de una secuencia Beatty por máquinas Mealy . [4] Posteriormente se demostró que el mismo enfoque conducía a conjuntos aperiódicos de 13 mosaicos, el mínimo conocido. [5] Kari también ha demostrado que el problema de los mosaicos de Wang sigue siendo indecidible en el plano hiperbólico , [6] y ha descubierto conjuntos de mosaicos de Wang con propiedades matemáticas adicionales. [7]
Kari también ha utilizado el problema del mosaico de Wang como base para las pruebas de que varios problemas algorítmicos en la teoría de los autómatas celulares son indecidibles. En particular, en su investigación de tesis, mostró que es indecidible determinar si una determinada regla de autómata celular en dos o más dimensiones es reversible . [8] Para los autómatas celulares unidimensionales, se sabe que la reversibilidad es decidible, y Kari ha proporcionado límites estrictos en el tamaño del vecindario necesario para simular la dinámica inversa de los autómatas unidimensionales reversibles. [9]
Referencias
- ^ Perfil del personal Archivado el 5 de diciembre de 2008 en Wayback Machine , Departamento de matemáticas de la Universidad de Turku, consultado el 9 de septiembre de 2011.
- ^ Jarkko Kari en el Proyecto de genealogía de las matemáticas
- ^ Hamalainen, Anna-Liisa (diciembre de 1992), "Tytto joka haluaa kaiken" (PDF) , Kodin Kuvalehti (en finlandés): 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), "Sobre conjuntos aperiódicos de mosaicos de Wang", Fundamentos de la informática: potencial - Teoría - Cognición , Lecture Notes in Computer Science , 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 Universalality (MCU 2007) , Lecture Notes in Computer Science, 4664 , Springer, págs. 72-79, doi : 10.1007 / 978-3-540-74593-8_6.
- ^ Kari, J .; Papasoglu, P. (1999), "Conjuntos de mosaicos aperiódicos deterministas", Análisis geométrico y funcional , 9 (2): 353–369, doi : 10.1007 / s000390050090 , MR 1692474.
- ^ Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Autómatas celulares: teoría y experimento (Los Alamos, NM, 1989) , Physica D: Nonlinear Phenomena , 45 , pp. 379-385, doi : 10.1016 / 0167-2789 (90) 90 195-U , MR 1094882.
- ^ Czeizler, Eugen; Kari, Jarkko (2007), "Un límite lineal estrecho en el retardo de sincronización de los autómatas biyectivos", Informática teórica , 380 (1–2): 23–36, doi : 10.1016 / j.tcs.2007.02.052 , MR 2330639.
enlaces externos
- Página de inicio personal de Jarkko Kari