ヤルコ・カリ

ヤルッコ・J・カリはフィンランドの数学者、コンピュータ科学者であり、ワングタイル理論とセルオートマトン理論への貢献で知られています。カリは現在、トゥルク大学数学科の教授です。^[1]

バイオグラフィー

カリは1990年にトゥルク大学で博士号を取得した。論文はアルト・サロマアの指導を受けた。^[2]

彼は後にトゥルクで数学を学ぶことになるリラ・カリと結婚したが、離婚し、その後リラ・カリはカナダのウェスタンオンタリオ大学でコンピュータサイエンスの教授になった。^[3]

研究

ワングタイルは各辺に色のついたマークが付いた単位正方形で、平面をモザイク状に並べるのに使用できますが、隣接する辺の色が一致するタイルでのみ使用できます。ワングタイルのセットが有効なモザイク状になるかどうかを決定する問題は決定不能であり、その決定不能性は、平面を非周期的にモザイク状に並べることしかできないワングタイルのセットを見つけることにかかっています。つまり、平面を平行移動してもタイルの対称性にならないような方法です。ロバート・バーガーによって発見された最初の非周期的なワングタイルのセットには、20,000を超える異なるタイルが含まれていました。カリは、（平面をタイル状に並べるのに使用した場合）ミーリーマシンによるビーティ列の構築をシミュレートするタイルのセットを見つけることで、このセットのサイズをわずか14にまで減らしました。 [ ^4]後に、同じアプローチが、最小の13タイルの非周期セットにつながることが示されました。^{[5]カリはまた、王タイル問題が}双曲面上では決定不可能なままであることを示し、^[6]追加の数学的性質を持つ王タイルの集合を発見した。^[7]

カリはまた、ワンのタイリング問題を、セルオートマトン理論におけるいくつかのアルゴリズム問題が決定不可能であることの証明の基礎として用いた。特に、彼は学位論文研究において、2次元以上のセルオートマトン規則が可逆的であるかどうかを判断することは決定不可能であることを示した。^[8] 1次元セルオートマトンの場合、可逆性は決定可能であることが知られており、カリは可逆的な1次元オートマトンにおける逆ダイナミクスをシミュレートするために必要な近傍のサイズに厳密な境界を与えた。^[9]

参考文献

^ スタッフプロフィール Archived 2008-12-05 at the Wayback Machine、U. Turku 数学部、2011-09-09 取得。
^ 数学系譜プロジェクトの Jarkko Kari
^ ハライネン、アンナ＝リーサ (1992 年 12 月)、「Tytto joka haluaa kaiken」(PDF)、Kodin Kuvalehti (フィンランド語): 22–24。
^ カリ、ヤルッコ (1996)、「ワンタイルの小さな非周期的集合」、離散数学、160 (1–3): 259–264、doi :10.1016/0012-365X(95)00120-L、MR 1417578。
^ Culik, Karel; Kari, Jarkko (1997)、「Wang タイルの非周期的集合について」、コンピュータサイエンスの基礎: 潜在的 - 理論 - 認知、コンピュータサイエンスの講義ノート、vol. 1337、Springer、pp. 153–162、doi :10.1007/BFb0052084。
^ Kari, Jarkko (2007)、「タイル問題の再考」、第 5 回国際機械・計算・普遍性会議 (MCU 2007) の議事録、コンピュータサイエンスの講義ノート、vol. 4664、Springer、pp. 72–79、doi :10.1007/978-3-540-74593-8_6。
^ Kari, J.; Papasoglu, P. (1999)、「決定論的非周期タイルセット」、幾何学および機能分析、9 (2): 353–369、doi :10.1007/s000390050090、MR 1692474。
^ Kari, Jarkko (1990)、「2D セルラーオートマトン可逆性は決定不能」、セルラーオートマトン: 理論と実験 (Los Alamos, NM, 1989)、Physica D: 非線形現象、vol. 45、pp. 379–385、doi :10.1016/0167-2789(90)90195-U、MR 1094882。
^ Czeizler, Eugen; Kari, Jarkko (2007)、「全単射オートマトン同期遅延の厳密な線形境界」、理論計算機科学、380 (1–2): 23–36、doi : 10.1016/j.tcs.2007.02.052、MR 2330639。

外部リンク

ヤッコ・カリの個人ホームページ

[1] スタッフプロフィール Archived 2008-12-05 at the Wayback Machine、U. Turku 数学部、2011-09-09 取得。

[2] 数学系譜プロジェクトの Jarkko Kari

[3] ハライネン、アンナ＝リーサ (1992 年 12 月)、「Tytto joka haluaa kaiken」(PDF)、Kodin Kuvalehti (フィンランド語): 22–24。

[4] カリ、ヤルッコ (1996)、「ワンタイルの小さな非周期的集合」、離散数学、160 (1–3): 259–264、doi :10.1016/0012-365X(95)00120-L、MR 1417578。

[5] Culik, Karel; Kari, Jarkko (1997)、「Wang タイルの非周期的集合について」、コンピュータサイエンスの基礎: 潜在的 - 理論 - 認知、コンピュータサイエンスの講義ノート、vol. 1337、Springer、pp. 153–162、doi :10.1007/BFb0052084。

[6] Kari, Jarkko (2007)、「タイル問題の再考」、第 5 回国際機械・計算・普遍性会議 (MCU 2007) の議事録、コンピュータサイエンスの講義ノート、vol. 4664、Springer、pp. 72–79、doi :10.1007/978-3-540-74593-8_6。

[7] Kari, J.; Papasoglu, P. (1999)、「決定論的非周期タイルセット」、幾何学および機能分析、9 (2): 353–369、doi :10.1007/s000390050090、MR 1692474。

[8] Kari, Jarkko (1990)、「2D セルラーオートマトン可逆性は決定不能」、セルラーオートマトン: 理論と実験 (Los Alamos, NM, 1989)、Physica D: 非線形現象、vol. 45、pp. 379–385、doi :10.1016/0167-2789(90)90195-U、MR 1094882。

[9] Czeizler, Eugen; Kari, Jarkko (2007)、「全単射オートマトン同期遅延の厳密な線形境界」、理論計算機科学、380 (1–2): 23–36、doi : 10.1016/j.tcs.2007.02.052、MR 2330639。

バイオグラフィー

研究

参考文献

外部リンク

関連するトピック

フィンランドの

数学者

コンピュータ科学者

ワングタイル