この記事は、ハワイ大学のビヨーン・ヒュース-ハンセン教授（Prof. Bjørn Kjos-Hanssen）のオートマトン複雑性に関する最新の研究について、日本の読者向けに概要をまとめたものである。

1. 目的
オートマトン複雑性に関する研究の目的は、特定の文字列を受領するオートマトンで、できるだけ状態数が少なく、その文字列と同じ長さの他の文字列をできるだけ受領しないオートマトンの効率のよい検索方法を見つけることである。言い換えれば、コルモゴロフ構造関数の考え方によるモデル選択をオートマトン上でより効率よく行うことである。
コルモゴロフ構造関数については歴史の項目で後述する。
モデル選択とは、自然界にある文字列でモデル化できるものが発見されたときに、背景となっているその文字列を生成する仕組みをオートマトンでモデル化することを指す。その文字列を受理し、他の文字列をできるだけ受理しないオートマトンを考えることができれば、そのオートマトンがモデルとして適切だと推測することができる。

2. オートマトン複雑性分野の歴史
オートマトン複雑性分野は近年研究の始まった分野であり、新規性が期待される。
当分野の主な歴史は、以下の通りである。

1960年代末 コルモゴロフ複雑性（Kolmogorov Complexity）
チューリングマシンにおける文字列の複雑性をそれに最適なプログラムの長さで定義
1973年 コルモゴロフ構造関数（Kolmogorov Structure Function）
文字列に対してプログラムとそのプログラムが受領する文字列の数を対応付ける関数で、文字列のモデリングの適切さを測る
2001年 ShallitとWangによるオートマトン複雑性（Automatic Complexity by Shallit and Wang）
コルモゴロフ複雑性を、オートマトンに拡張。オートマトンでの複雑性をその文字列を受領し、他の同じ長さの文字列を受領しないオートマトンの最小の状態数で定義
2014年 Vereshchagin のオートマトン複雑性上での構造関数（Vereshchagin structure function for Automatic complexity）
オートマトン上での構造関数を、オートマトンの状態数と特定の文字列を受領するその状態数のオートマトンが受領する最小の文字列数の対応として定義

3. 当研究に期待される成果
現在、文字列に対する最適なモデルの推測の効率のよいアルゴリズムは発見されていないが、この研究によって、より正確に効率よく推測できるようになる。

4. 当分野において期待されるインパクト
オートマトン複雑性上での構造関数の計算速度の向上が期待されている。

5. 諸科学において期待されるインパクト
構造関数はco-NP問題であるため、未解決問題であるP=NP、co-NP=NPなどの問題についての理解を深めることができる。

当研究は現在進行中で、公開時期は未定である。
引き続きビヨーン教授の最新の情報に注目していただきたい。

小林 佐保，千葉大学 理学部 数学・情報数理学科
Saho Kobayashi, Undergraduate, Department of Mathematics and Informatics, Faculty of Science, Chiba University