Kobayashi SATOSHI (小林 聡)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: competitive_research_funding, Overall Grant Amount: - (direct: 13700000, indirect: 4110000)
In order to develop the foundation for designing molecular computers which can execute various computational functions according to sequences of external control signals, we devised novel computational models with unknown behaviors which can be controlled by external signals, novel DNA devices responsive to external signals, a new sequence design system for finding DNA sequences for temperature dependent DNA devices, and finally collected data and knowledge which are important when using two different DNA devices in a system. The theoretical and experimental research discussions enabled to find an important knowledge that, when we construct a system, we need to partition reactions into reversible and irreversible ones based on their computational functions. Furthermore, the development of the new photo-responsive device makes us distinguish a single base difference of input DNA sequences, which suggests an important improvement in the developed computational models.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Fund Type: -, Overall Grant Amount: - (direct: 31000000, indirect: 9300000)
The area meeting attended by all the area members was held 9 times. The open symposium was held once a year and the final one is planned in July 2017. Research workshops were held 19 times. The area also sponsored the open symposium in two international conferences.
The home page (http://www.molbot.org）continued submitting information about the area, and the news letter was published four times a year.
The area supported the international biomolecular design competition for undergraduate students by sponsoring the domestic preliminary contest five times and writing a textbook, which is planned to be translated to English by the international committee. The workshop for high school students (hirameki-tokimeki science) titled “Make and play with DNA origami” was held twice. A booth was put four times in exhibitions for companies (MEMS and Nano-Micro Business).

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (S), Fund Type: -, Overall Grant Amount: - (direct: 164700000, indirect: 49410000)
In this research project, aiming at developing fundamental techniques to construct molecular robots composed of molecular devices rigorously designed from scratch, which are able to adapt to various environmental changes. The developed technologies based on DNA nano-engineering include
(1) Techniques to fabricate compartments which compose the body of molecular robot containing molecular devices, (2) Techniques to realize interface, which realizes molecular communication across the compartment, (3) Techniques to control the molecular computation in molecular robots and intra-and inter-molecular robot communication, (4) Techniques to design cooperative behaviors of swarm of multiple molecular robots.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 特定領域研究, Fund Type: -, Overall Grant Amount: - (direct: 41500000, indirect: -)
(1)膜計算モデルにおける新しい計算モデルの提案:神経細胞系をモデルとして,膜計算の新しいモデル「Spiking Neural P-Systems」を提案し,受理器と生成器の両タイプにおいてその計算能力の万能性を示した。
(2)平衡状態の効率の良い計算手法の開発:入力分子のサイズに比して会合の結果生成される分子複合体の個数が組合せ論的な爆発をするような反応系に対して,平衡状態を計算するための一般論を構築した。平衡状態計算を系全体の自由エネルギーの最小化問題として定式化し,変数の個数を著しく削減する新しいアルゴリズムを開発した。
(3)細胞並列計算に向けたバクテリアセルオートマトンの実装:細胞を用いたセルオートマトンの実現に向けての第一歩として,細胞内分子反応メカニズムを用いて自律的でプログラム可能なバクテリアコンピュータを開発した。これは世界で初めてバクテリアを用いて計算が実行できたことを証明するものである。
(4)抽象化学反応計算モデルの研究:微分方程式系などでは解析が困難な少数分子の化学反応系の振る舞いについて計算機実験と数理的解析により検討し,特にBelousov-Zhabotinsk (BZ)反応の数理モデルであるBrruselatorとOregonatorについて,分子数が少数になることによる不安定性について解析した。
(5)分子計算シミュレータ:階層構造と接続構造の両方を扱う階層グラフ書換えモデルLMNtalの表現力検証のために,代表的計算モデルのエンコード法の確立と実装を行った。Ambient計算のエンコードにおいては自己調整に基づく分散名前管理方式を実現した。純粋λ計算のエンコードにおいては,膜を活用することで従来手法よりもはるかに簡潔な方法を実現した。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3400000, indirect: -)
We have established a polynomial-time algorithm for exactly learning simple deterministic languages via membership queries, given a representative sample of the target language. This algorithm sophisticatedly employs a polynomial-time algorithm for checking the equivalence of simple deterministic languages that was devised by ourselves previously.
For a real-time deterministic restricted one counter automation (droca) which has exactly one transition rule per one terminal symbol, a polynomial-sized characteristic sample is exactly obtained. Based on this result, we have devised an algorithm for identifying droca's in the limit with polynomial updating time and polynomial number of updates.
We have developed an algorithm for approximately learn certain Boolean functions, called AC^0, from examples of their behavior with possibly attribute and classification noise, provided we are given the upper bound of the noise ratio which is less than 1/2. Subsequently, we devised an algorithm for guessing the upper bound of the noise ratio. Combining these results, we have succeeded in designing and algorithm for approximately learn such functions without any knowledge of the noise ratio in advance.
Some algorithms were devised to identify some subregular languages in the limit from positive samples. Then we gave a unified method to identify some classes of languages in the limit from positive examples.
Algorithms for finding a maximum clique in a graph are important for clustering problems. Then we devised a very fast algorithm for finding a maximum clique together with some extensions. We have successfully applied these algorithms for some practical problems as in bioinformatics, image processing, and so on.