Category Archives: research

group

Covering the computable sets

I participated in the workshop on Algorithmic Randomness in Singapore and the conference on Computability, Complexity and Randomness.

With host Frank Stephan and fellow participant Sebastiaan Terwijn we wrote a paper entitled Covering the recursive sets which appeared in Lecture Notes in Computer Science, Conference on Computability in Europe, 2015, and has now been published in Annals of Pure and Applied Logic.

20160929_115658

ビヨーン教授の最新研究の概要

この記事は、ハワイ大学のビヨーン・ヒュース-ハンセン教授(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

Cornell_University,_Ho_Plaza_and_Sage_Hall

The Complexity Option Game

2014 M.A. graduate Malihe Alikhani completed her Master’s project on American option pricing and optimal stopping for success runs. She participated in the Cornell Summer School in Probability 2014.

Her project constitutes one of the parts of the new paper Pricing Complexity Options, which appeared in
Algorithmic Finance, 2015.

Entry at IOS Press

The best version of the paper is at arxiv.org

The ideas are implemented in the Complexity Option Game!

20140517_165751

Graduate Program in Logic

The Department of Mathematics at University of Hawaii at Manoa has long had an informal graduate program in logic, lattice theory, and universal algebra going back to Alfred Tarski’s student William Hanf.
Starting in 2016, things are getting a little more formal.

We intend the following course rotation (repeating after two years):

Semester Course number Course title
Fall 2015 MATH 649B Graduate Seminar
Spring 2016 MATH 649* Applied Model Theory
Fall 2016 MATH 654* Graduate Introduction to Logic
Spring 2017 MATH 657 Computability and Complexity

*Actual course numbers may vary.

Faculty who may teach in the program

David A. Ross, Professor
Bjørn Kjos-Hanssen, Professor
Mushfeq Khan, Temporary Assistant Professor 2014-2017
Achilles Beros, Temporary Assistant Professor 2015-2017

Documentation for the structure function calculator

$h^*_x(m)=q$ means that in order to have at most $\text{(alphabet size)}^{m}$ accepting paths of length $n=|x|$, we need $q$ states.

Rules

  • We are considering single-run complexity where the automaton must proceed to a fresh state except
    that there is one state that may be repeated.
  • Thus: the automaton need not be deterministic; a run may be abandoned midway;
  • the run can start before we get to the run-state;
  • runs that are of less than maximal length of their “flavor” (such as 322023 which is shorter than 20322023 in the given example) do count (they are in any case insignificant for statistical model selection purposes); runs of less than maximal length for their size-of-flavor (such as 2311322 for size 3) do count; in general any subrun of a run counts.

The provided example comes from a series of codons in part of a messenger RNA (mRNA) molecule whose genetic code is $$AUG\, ACG\, GAG\, CUU\, CGG\, AGC\, UAG$$
encoded as
$$x=012032202311322023102$$
which has length $n=21$ and is a string from the alphabet $\{0,1,2,3\}$ which has size $b=4$. There is a run of length $r=8$ from the subalphabet $j=\{0,2,3\}$, namely an occurrence of 20322023. The corresponding automaton has $q=n+1-r=21+1-8=14$ many states and accepts $|j|^r=3^8$ many strings of length $n$. When $3^8\le b^m$ we can then assert that $h^*(m)\le q$. Thus
$$
6561 = 3^8\le 4^m
$$
Note
$$
(4^2,4^3,4^4,4^5,4^6,4^7)= (16, 64, 256, 1024, 4096, 16384)
$$
So $h^*(7)\le 14$.

The longest unary ($|j|=1$) run is of length $r=2$. This gives $q=n+1-r=20$ and only one string is accepted so $h^*(m)\le 20$ for all $m$.

The longest binary ($|j|=2$) run is of length $r=4$. This gives $q=n+1-r=18$ and when $2^4\le 4^m$ (i.e., $2\le m$), we can assert $h^*(m)\le q$. So $h^*(2)\le 18$.

What can we say about $h^*(6)$? $4^6=4096$ and
$(3^4,3^5,3^6,3^7,3^8)=(81, 243, 729, 2187, 6561)$. So
$$3^8\le 4^7\Longrightarrow h^*(7)\le 22-8=14$$
$$3^7=2187\le 4^6=4096\Longrightarrow h^*(6)\le 22-7=15$$
$$3^6= 729\le 4^5 = 1024\Longrightarrow h^*(5)\le 22-6=16$$
$$3^5= 243\le 4^4 = 256\Longrightarrow h^*(4)\le 22-5=17$$
$$3^4= 81 \le 4^4 = 256(\Longrightarrow h^*(4)\le 22-4=18)$$
$$3^3= 27\le 4^3 = 64\Longrightarrow h^*(3)\le 22-3=19$$
So we cannot obtain $h^*(3)\le 18$ by a partial ternary run, but we can obtain it because $h^*(2)\le 18$ because of the binary run.

Note
$$3^r\le 4^1\Longrightarrow r\le 1$$
$$2^r\le 4^1\Longrightarrow r\le 2$$
So a binary run of length 2 narrows it down to $4^1$.
And this corresponds to
$$q=n+1-r=21+1-2=20,$$
so $h^*(1)\le 20$.

Some examples of “inversion” (different explanation for the string depending on whether the subalphabet, or the size of the subalphabet, is taken into account):
21112
212220
020001
211120
1333030
32322131
201011311
1010113303
01210312303