氏名

ヨコモリ タカシ

横森 貴

職名

教授 (https://researchmap.jp/read0008951/)

所属

(教育学部)

連絡先

メールアドレス

メールアドレス
yokomori@waseda.jp

住所・電話番号・fax番号

住所
〒169-8050新宿区 西早稲田1-6-1
電話番号
03-3202-8373
fax番号
03-5286-1308

URL等

WebページURL

http://www.f.waseda.jp/yokomori/(研究室の概要、および詳細な個人情報)

研究者番号
60139722

本属以外の学内所属

兼担

教育・総合科学学術院(大学院教育学研究科)

研究院(研究機関)/附属機関・学校(グローバルエデュケーションセンター)

学内研究所等

教育総合研究所

兼任研究員 1989年-

ナチュラルコンピュテーション研究所

プロジェクト研究所所長 2000年-2005年

理工学総合研究センター

兼任研究員 1989年-2006年

理工学術院総合研究所(理工学研究所)

兼任研究員 2006年-2018年

学歴・学位

学歴

-1974年 東京大学 理学部 数学
-1979年 東京大学 理学系研究科 相関理化学

学位

理学博士 東京大学

経歴

http://www.f.waseda.jp/yokomori/
における当該項目をご参照ください。

所属学協会

情報処理学会

人工知能学会

日本バイオインフォマティクス学会

Association for Computing Machinery

European Association for Theoretical Computer Science

委員歴・役員歴(学外)

2015年01月-2015年12月Applied Soft Computing 誌 (Elsevier)編集委員
2003年09月-Theoretical Computer Science 誌(Elsevier)編集委員
2000年09月-2003年12月Grammars 誌編集委員
1999年-2010年03月Fundamenta Informaticae 誌編集委員
1999年06月-2001年05月情報処理学会論文誌編集委員会 基礎理論領域主査
1994年05月-1996年10月電子情報通信学会英文誌D編集委員
1986年05月-1994年04月電子情報通信学会論文査読委員
1995年05月-1996年10月情報処理学会論文誌編集委員
2011年09月-Development in Language Theory (International Conference Series)Steering Committee Member
2018年08月-SpringerAdvisory Board of the Springer Natural Computing Book Series

受賞

情報処理学会フェロー

2019年06月授与機関:(社)情報処理学会 

研究分野

キーワード

計算機科学(形式言語理論、計算論的学習理論、分子計算論)、生命情報学

科研費分類

情報学 / 情報基礎学 / 情報基礎理論

研究テーマ履歴

オートマトン・形式言語理論

研究テーマのキーワード:オートマトン、形式文法、形式言語、計算論

個人研究

計算論的学習理論

研究テーマのキーワード:文法推論、帰納的学習、機械学習

個人研究

生命情報学

研究テーマのキーワード:ゲノム配列(DNA, RNA)解析、ゲノム構造予測

個人研究

2002年-2006年自然計算論

研究テーマのキーワード:分子計算モデル、自律的計算、分子プログラミング、化学反応計算

国内共同研究

論文

Decomposition and factorization of chemical reaction transducers

F.Okubo and T.Yokomori

Theoretical Computer Science777p.431 - 4422019年06月-

Computing with Multisets : A Survey on Reaction Automata Theory

T.Yokomori and F.Okubo

Lecture Notes in Computer Science10936p.1 - 112018年07月-

Natural Computing Paradigm ─ A Concise Introduction

T.Yokomori

Journal of Robotics, Networking and Artificial Life5(1)p.6 - 92018年06月-

The computing power of determinism and reversibility in chemical reaction automata

in "Reversibility and Universality"(edited by A.Adamatzky), Springerp.279 - 2982018年-

Morphic Characterizations of Language Families Based on Local and Star Languages

Fundamenta Informaticae154p.323 - 3412017年08月-

DOI

The computational capability of chemical reaction automata

Okubo, Fumiya; Yokomori, Takashi

Natural Computing15(2)p.215 - 2242016年06月-2016年06月 

DOIScopus

詳細

ISSN:15677818

概要:© 2015, Springer Science+Business Media Dordrecht.We propose a new computing model called chemical reaction automata (CRAs) as a simplified variant of reaction automata (RAs) studied in recent literature (Okubo in RAIRO Theor Inform Appl 48:23–38 2014; Okubo et al. in Theor Comput Sci 429:247–257 2012a, Theor Comput Sci 454:206–221 2012b). We show that CRAs in maximally parallel manner are computationally equivalent to Turing machines, while the computational power of CRAs in sequential manner coincides with that of the class of Petri nets, which is in marked contrast to the result that RAs (in both maximally parallel and sequential manners) have the computing power of Turing universality (Okubo 2014; Okubo et al. 2012a). Intuitively, CRAs are defined as RAs without inhibitor functioning in each reaction, providing an offline model of computing by chemical reaction networks (CRNs). Thus, the main results in this paper not only strengthen the previous result on Turing computability of RAs but also clarify the computing powers of inhibitors in RA computation.

The computational capability of chemical reaction automata

Natural Computing15p.215 - 2242016年-

DOI

Finite Automata with Multiset Memory: A New Characterization of Chomsky Hierarchy

Okubo, Fumiya;Yokomori, Takashi

FUNDAMENTA INFORMATICAE138(1-2)p.31 - 442015年-2015年

DOIWoS

詳細

ISSN:0169-2968

The computational capability of chemical reaction automata

Proc. of 20th International Conference on DNA Computing and Molecular Programming, Kyoto, Japan, Lecture Notes in Computer Science, Springer8727p.53 - 662014年-

Recent developments on reaction automata theory: A survey

Series: Mathematics for Industry, vol.9 (Y.Suzuki and M.Hagiya, eds.), SpringerVol.9p.1 - 222014年-

Automata inspired by biochemical reaction (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)

大久保 文哉;小林 聡;横森 貴

数理解析研究所講究録1799p.179 - 1822012年06月-2012年06月 

CiNii

詳細

ISSN:1880-2818

On the Properties of Language Classes of Bounded Reaction Automata

Theoretical Computer ScienceVol.454p.206 - 2212012年-

Reaction Automata

Theoretical Computer ScienceVol.429p.247 - 2572012年-

Morphic Characterizations of Language Families in Terms of Insertion Sytems and Star Languages

Intern. J. of Foundations of Computer ScienceVol.22(No.1)p.247 - 2602011年-

Spiking Neural dP-systems

Fundamenta InformaticaeVol.111p.423 - 4362011年-

On the Hairpin Incompletion

Okubo, Fumiya;Yokomori, Takashi

FUNDAMENTA INFORMATICAE110(1-4)p.255 - 2692011年-2011年

DOIWoS

詳細

ISSN:0169-2968

Spiking Neural dP Systems

Ionescu, Mihai;Paun, Gheorghe;Perez-Jimenez, Mario J.;Yokomori, Takashi

FUNDAMENTA INFORMATICAE111(4)p.423 - 4362011年-2011年

DOIWoS

詳細

ISSN:0169-2968

MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES

Okubo, Fumiya;Yokomori, Takashi

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE22(1)p.247 - 2602011年-2011年

DOIWoS

詳細

ISSN:0129-0541

On spiking neural P systems

Ibarra, Oscar H.;Perez-Jimenez, Mario J.;Yokomori, Takashi

Natural Computing9(2)p.475 - 4912010年-2010年

DOIWoS

詳細

ISSN:1567-7818

SOME REMARKS ON THE HAIRPIN COMPLETION

Manea, Florin;Mitrana, Victor;Yokomori, Takashi

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE21(5)p.859 - 8722010年-2010年

DOIWoS

詳細

ISSN:0129-0541

Membrane Computing Schema: A new approach to computation using string insertion

Algorithmic Bioprocesses, Springerp.293 - 3092009年-

DOI

Two complementary operations inspired by the DNA hairpin formation:completion and reduction

Theoretical Computer Science410p.417 - 4252009年-

Some Remarks on the Hairpin Completion

Proceedings of 12th Intern. Conf. on Automata and Formal Languages2008年05月-

Linearizer and Doubler : Two mappings to unify molecular computing modles based on DNA complementarity

Natural Computing7p.124 - 1432008年-

Representations and Characterizations of Languages in Chomsky Hierarchy by means of Insertion-Deletion Systems

Intern. J. of Foundations of Computer Science19p.859 - 8712008年-

Special Issue on DNA Computing

(edited) C.Mao and T.Yokomori

7(2)2008年-

Special Issue on Spiking Neural P systems

(edited)

Natural Computing7(2)2008年-

Representations and Characterizations of Languages in Chomsky Hierarchy by means of Insertion-Deletion Systems

Proc. of 9th workshop on Descriptional Complexity of Formal Systems, High Tatras, Slovakiap.129 - 1402007年07月-

Spiking Neural P Systems with an Exhaustive Use of Rules

International Journal of Unconventional Computing3(2)p.135 - 1532007年-

DNA Computing

Proc. of 12th International Meeting on DNA Computing, DNA12, Seoul, Korea, June 5-9, 2006; Lecture Notes in Computer Science42872006年11月-

Spiking Neural Psystems

Fundamenta Informaticae71(2,3)p.279 - 3082006年-

Linearizer and Doubler : Two mappings to unify molecular computing modles based on DNA complementarity

Proc. of 11th Intern. Meetings on DNA based computers, London, Ontariop.139 - 1502005年06月-

A simple classification of the volvocine algae by formal languages

Bulletin of Mathematical Biology67p.1339 - 13542005年-

On the Power of Membrane Division in P systems

Theoretical Computer Science324(1)p.61 - 852004年09月-

An Algorithm for Testing Structure Freeness of Biomolecular Sequences

Lecture Notes in Computer Science/SpringerVol. 2950p.266 - 2772004年-

Learning Context-sensitivenes : Toward Understanding Children's Language Learning

Proc. of 7th ICGI (Lecture Notes in Artificial Intellignece) /Springer3264p.53 - 642004年-

On the Computational Power of Insertion-Deletion Systems

Natural Computing/Kluwer AcademicVol.2, Nol.4p.321 - 3362003年-

Polynomial-time identification of very simple grammars from positive data

Theoretical computer scienceVol.298p.179 - 2062003年-

A Magic Pot : Self-assembly computation revisited

Formal and Natural Computing, Lecture Notes in Computer ScienceVol.2300p.418 - 4292002年-

Molecular Computing Paradigm - Toward freedom from Turing's charm

Natural ComputingVol.4, No.1p.333 - 3902002年-

On the Computational Power of Insertion-Deletion Systems

Lecture Notes in Computer Science/SpringerVol.2568p.269 - 2802002年-

分子コンピューティング

日本ソフトウェア科学会2001年07月-

Toward Soft Hardware

Soft Computing/Springer5;22001年05月-

Hairpin Languages

International Journal of Foundations of Computer ScienceVol.12, No.6p.837 - 8472001年-

分子コンピューティング--理論モデルの最前線

Computer Today/サイエンス社No.100, pp.4-112000年11月-

ナチュラルコンピュテーション--生命現象から学ぶ新しい計算パラダイム

情報処理/情報処理学会41;8, pp.925-9312000年08月-

分子計算の理論モデル

数理科学/サイエンス社No.445, pp.8-142000年07月-

Molecular Computation by DNA Hairpin Formation

Science288p.1223 - 12262000年-

On the Universality of Post and Splicing Systems

Theoretical Computer Science/Elsevier231p.157 - 1702000年-

Simulating H systems by P systems

Journal of Universal Computer Science/Springer-Verlag6p.178 - 1932000年-

Computation = Self-assembly + Conformational Change : Toward New Computing Paradigms

Proc. of 4th International Conference on Developments in Language Theory(DLT'99) p.21 - 301999年07月-

Membrane Computing Based on Splicing

Proc. of 5th DIMACS Workshop on DNA based Computers/AMSp.213 - 2271999年06月-

YAC: Yet Another Computation Model of Self-Assembly

Proc. of 5th DIMACS Workshop on DNA based Computers/AMSp.153 - 1671999年06月-

分子コンピューティング—新計算パラダイムの探求

人工知能学会人工知能基礎論研究会資料 SIG-FAI-9804-13; pp.21-301999年03月-

Tree Adjoining Grammars for RNA Structure Prediction

Theoretical Computer Science/Elsevier210p.277 - 3031999年01月-

分子コンピュータ —その理論と実験

Computer Today/サイエンス社16;1, pp.4-131999年01月-

Learning Local Languages and Their Application to DNA Sequence Analysis

IEEE Trans. on PAMI/IEEE20;10p.1067 - 10791998年10月-

Locality, Reversibility and Beyond: Learning Languages from Positive Data

Proc. of 9th Conference on Algorithmic Learning Theory(ALT98), LNAI/Springer-Verlag1501p.191 - 2041998年10月-

DNAコンピュータ:その現状と可能性

情報処理学会 第39回プログラミング・シンポジウムpp.21-301998年01月-

Bio-Computingってなんだろう? — 逆転の発想:分子コンピュータ

bit(共立出版)29;8, pp.34-381997年08月-

DNA-EC : A Model of DNA-Computing Based on Equality Checking

Proc. of 3rd DIMACS Workshop on DNA Based Computersp.334 - 3471997年06月-

DNA Implementation of Simple Horn Clause Computation

Proc. of IEEE Intern. Conference on Evolutionary Computationp.213 - 2171997年04月-

On the Power of Circular Splicing Systems and DNA Computability

Proc. of IEEE Intern. Conference on Evolutionary Computationp.219 - 2241997年04月-

Learning Approximately Regular Languages with Reversible Languages

Theoretical Computer Science174p.251 - 2571997年-

Families of Noncounting Languages and Their Learnability from Positive Data

International J. of Foundations of Computer Science7;4p.309 - 3271996年-

Learning Two-Tape Automata from Queries and Counterexamples

Mathematical Systems Theory29;3p.259 - 2701996年-

On Polynomial-Time Learnability in the Limit of Strictly Deterministic Automata

Machine Learning19;2p.153 - 1791995年-

(1995年以降のみ)

書籍等出版物

ナチュラルコンピューティン・シリーズ:第0巻「自然計算へのいざない」

小林聡・萩谷昌己・横森貴(共編著):

近代科学社2015年 12月-

オートマトン・言語理論(第2版)

森北出版2013年 12月-

Handbook of Natural Computing, Chapter 34: Molecular Computing Machineries — Computing Models and Wet Implementations

Springer2012年 07月-

応用 情報数学

サイエンス社2011年 06月-

ナチュラルコンピューティング・シリーズ:第1巻〜第7巻

シリーズ編集

近代科学社2011年 03月-

基礎 情報数学

サイエンス社2008年 06月-

「バイオインフォマティクス辞典」

(分担執筆)

共立出版2006年 08月-

ハンドブック「プラントミメティックス〜植物に学ぶ〜」

(分担執筆)

NTS出版2006年 08月-

アルゴリズム データ構造 計算論

サイエンス社2005年 03月-

DNAコンピュータ

培風館2001年 12月-

計算論的学習

培風館2001年 10月-

DNAコンピューティング--新しい計算パラダイム

シュプリンガーフェアラーク東京1999年 12月-

例からの学習---計算論的学習理論

オーム社1992年 08月-

オートマトン・言語理論

森北出版1992年 05月-

計算機数学

森北出版1990年-

Probabilistic inference in test tube and its application to the Gene expression profiles

“Formal models, Languages and Applications”(eds. M. Mukund, K. G. Subramanian, K.Rangarajan), series in Machine Perception and Artificial Intelligence,World Scientific,2006年-

Grammatical Inference and Learning

Formal Languages and Applications (eds.Martin-Vide, Mitrana and Paun), Springer2004年-

Approximate Identification and Finite Elasticity

Where Mathematics, Computer Science, Linguistics and Biology Meet/Kluwer Academic2001年 01月-

講演・口頭発表等

Natural Computing Paradigm -- A Concise Introduction

Takashi Yokomori

The 2018 International Conference on Artificial Life and Robotics(ICAROB Society)招待有り2018年02月01日

詳細

国際会議口頭発表(招待・特別)開催地:別府、大分

Introduction to Natural Computing (Tutorial Lecture)

Takashi Yokomori

The 8th Intern. Meeting on DNA Based Computers招待有り2002年06月10日

詳細

国際会議チュートリアル開催地:Sapporo

外部研究資金

科学研究費採択状況

研究種別:

構造的分子計算理論-自律的計算系の解析と設計のための基礎理論

配分額:¥41500000

研究種別:

生体メカニズムに基づく新しい分子計算パラダイムの研究

配分額:¥2300000

研究種別:

文法学習アルゴリズムに基づく蛋白質高次構造予測システムの開発

配分額:¥1500000

研究種別:

文法学習アルゴリズムに基づく蛋白質高次構造予測システムの開発

配分額:¥1600000

研究種別:

概念形成・知識獲得過程の理論化

配分額:¥52900000

研究種別:

ニュ-ラルネットワ-クによる高効率な最大クリ-ク抽出アルゴリズムの開発と評価

配分額:¥2800000

研究種別:特定領域研究

分子プログラミング

2002年-2007年

配分額:¥54500000

研究種別:

反応オートマタ理論に基づく化学反応計算系の基礎的研究

2017年-0月-2020年-0月

配分額:¥2470000

研究種別:

知能分子ロボット実現に向けた化学反応回路の設計と構築

2012年-0月-2017年-0月

配分額:¥190320000

研究種別:

分子プログラミング

配分額:¥54500000

学内研究制度

特定課題研究

生体分子の言語理論的進化モデルの研究

2011年度共同研究者:大久保文哉

研究成果概要:申請者らはここ数年来,分子計算の分野において主に形式言語理論による配列集合に対する特徴付けを研究してきた.その過程において,与えられた記号列から新たな記号列を生成する「ヘアピン・コンプレッション」(HC: hairpin comp...申請者らはここ数年来,分子計算の分野において主に形式言語理論による配列集合に対する特徴付けを研究してきた.その過程において,与えられた記号列から新たな記号列を生成する「ヘアピン・コンプレッション」(HC: hairpin completion)という演算(操作)に注目した.これは核酸配列がヘアピン構造をつくる現象を基本としてモデル化したものである.我々はHC演算を修正した「ヘアピン・インコンプレッション」(HI: hairpin incompletion)とよぶ新しい演算を定義し,この演算の持つ計算能力を解析した.HIは,実際にIn Vitro実験において開発されている“ Whiplash PCR(WPCR)”という制御可能な分子反応操作を忠実にモデル化した演算である. 本研究では「記号列の集合である形式言語とその言語族がHI演算に対してどのような振る舞いを示すか」という視点から,以下の結果を得た([1]).(1) 正則言語との共通集合演算,正則言語との連接演算,および和集合演算に関して閉じて いる言語族はHI演算に関しても閉じている.(2) すべての線形言語を含み,環状順列演算,左微分演算,および代入演算に関して閉じて いる言語族は繰り返しHI演算に関しても閉じている.これらの知見から,例えば与えられたDNA配列の有限集合がWhiplash PCRのようなメカニズムによって進化すると考えるとき,その進化結果は正則言語の範囲内である,と結論つけられる. 一方,本研究では分子反応系を基本とした計算モデルの研究にも着手し,反応オートマトン(RA: Reaction Automata)とよぶ計算モデルを導入し,その計算能力を解析した.RAは化学反応系をモデル化した記号列受理器であり,(従来型のオートマトンと異なり)試験管内や細胞内の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴がある.得られた結果は以下の通りである([2],[3]).(i) RAはチューリング機械と等価な万能計算能力を有する.(ii)空間的に制限されたRAに関しては,線形的限定RAは文脈自由言語族と比較不可能な言語族 を形成し,指数的限定RAの計算能力は文脈依存言語族と一致する.これらの結果は,化学反応による計算/情報処理能力を解明する新しい知見を与える.

生命言語理論に基づく生体分子の進化モデルの研究

2012年度共同研究者:大久保文哉

研究成果概要:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応には反応分子(R), 抑制分子(I), 生成分子(P)の3つが関わるとして抽象化し,これを多重集合の3つ,組a=(R,I,P)で定...申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応には反応分子(R), 抑制分子(I), 生成分子(P)の3つが関わるとして抽象化し,これを多重集合の3つ,組a=(R,I,P)で定式化した.この反応の解釈は『いま考えている分子の多重集合TはRを含むがIは含まないとき,この反応によりTからRが消費され,同時にPが新たに生成される』とみなす.このとき反応aによりTから新たにT'(=T-R+P)が生成される.このような反応aをすべて可能な限り適用するような反応の多重集合をαしたとき,αを極大並列適用とよび,このときの変化を T⇒α T' と表す. このような形式化において,外部からの入力をも受け取りつつ,内部状態が遷移するオートマトンを反応オートマトン(RA: Reaction Automata)として定義した.すなわち,外部入力列a1,...,anがRA:Mによって受理されるとは,指定された状態の多重集合T0から,指定された最終状態の多重集合Fへ至る遷移の系列:T0⇒a1 T1⇒a2 T2 ⇒・・・⇒an Tn⇒・・・⇒Fが存在するときと定義する(ただし,ここでは各遷移における極大並列反応は省略されている).そして,このように受理される入力列全体からなる集合L(M)の数学的性質(計算量)を理論的に解析した.RAは化学反応系をモデル化した記号列受理器であり,(従来型のオートマトンと異なり)試験管内や細胞内の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴がある.得られた結果は以下の通りである. 入力のサイズnをパラメタとしたとき,RAが計算に用いる多重集合のサイズを関数f(n)とする.この時,(i) f(n)が指数関数であるようなRAによって受理される集合の族は,文脈依存言語族CSLに一致する.(ⅱ)f(n)が線形関数であり,かつ空入力動作が許されたRAによって受理される集合族は抽象言語族(AFL)を形成する.(ⅲ) 任意の帰納的可算言語は,f(n)が線形関数のRAによって受理される言語の準同型写像によって表される.(以上,文献[1])さらに,上記の状態遷移関係 ⇒a を逐次的な反応に制限した場合(s-RAと表す)の受理能力を解析した.その結果,(ⅳ)f(n)が線形関数で,空入力動作をもつs-RAによって受理される言語族は,1方向log f(n)空間限定TMによって受理される言語族と一致する.(ⅴ) f(n)が線形関数であるとき,RAとs-RAとはその受理能力は比較不能な関係にある.(以上,文献[2])これらの結果は,化学反応による計算/情報処理能力を解明する新しい知見を与える.

多重集合理論に基づく計算システムの研究

2013年度

研究成果概要:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行って来た.その結果,少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重集合とみなすことにより,計算過程を多重集合の“置き換え系”としてモデル化できる」...申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行って来た.その結果,少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重集合とみなすことにより,計算過程を多重集合の“置き換え系”としてモデル化できる」ことを確認した.これらの知見から,多重集合を計算の作業領域(メモリ領域)とするオートマトン・モデルという着想に至り,これをFinite Automata with Multiset Memory(FAMM)として,定式化した. FAMMは有限個の状態を有し,多重集合をメモリとして使用する記号列受理機構である.よってFAMMは,これまで申請者らが研究してきたReaction Automata(RA)のヴァリアント(変種)としてみなすことができる.より具体的には,FAMMの動作は以下のように説明される.「今、状態がpでありメモリが多重集合Tであるとき,入力テープwから1記号ずつ入力記号aを読み込む.そのとき,遷移規則(p, a, α)→(q,β)が適用されると,次の状態はqとなりメモリーはT'(=T-α+β)への更新される.」与えられた入力列wの先頭から1記号ずつ読み込んでいき,この動作を繰り返して行き,入力をすべて読み終えた後,ある(指定された)最終状態へ遷移するとき,FAMMは入力列wを受理する.このようにして受理される入力列全体の集合が本研究の対象である. FAMMの研究目的は,「メモリとして多重集合のみを許される有限オートマトンの計算能力を解析する」ことである.この研究テーマに関する予想として「多重集合というが概念が情報を保持するデータ構造として極めてシンプルである(すなわち,記号列のような記号の順序情報が保持できない)ことから,FAMMの計算能力は限られている」と思われていた.ところが研究の結果,以下のような興味深い成果が得られている.(1)(制限のない一般形の)FAMMの計算能力はチューリング機械と等価である.(すなわち,  現在の計算機と理論的に同等の能力を有する.)(2) メモリを入力サイズの多項式サイズに制限したFAMMは線形有界オートマトンと等価な計算  能力をもつ(3) 遷移規則の適用モードをハイプリッドにした、制限されたFAMMはプッシュダウンオートマトン  と等価な計算能力をもつ(4) ある定数で抑えられたメモリをもつFAMMは有限オートマトンと等価である.このように,FAMMという形式的枠組みにを用いて,従来から研究が行われている計算モデルであるチューリング機械を中核とするオートマトン理論を再構築することができた.これらの結果は,多重集合による計算/情報処理能力を解明する新しい知見を与えている(文献[1]).

反応オートマトンによる化学反応系の解析

2013年度共同研究者:大久保文哉

研究成果概要:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応は反応分子(R), 抑制分子(I), 生成分子(P)の3つが関わるとして抽象化し,これを多重集合の3つ組a=(R,I,P)で定式化...申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応は反応分子(R), 抑制分子(I), 生成分子(P)の3つが関わるとして抽象化し,これを多重集合の3つ組a=(R,I,P)で定式化した.この3つ組による反応を適用すると,『いま考えている分子の溶液(多重集合)TがRを含みIを含まないとき,この反応によりTからRが消費され,同時にPが新たに生成される』と解釈される.このとき反応aによりTから新たにT'(=T-R+P)が生成される. このような反応aをすべて可能な限り適用するような反応の多重集合をαしたとき,αを極大並列適用とよび,このときの変化を T⇒α T' と表す.このような形式化において,外部からの入力をも受け取りつつ,内部状態が遷移するオートマトンを反応オートマトン(RA: Reaction Automata)として定義した. 本研究では主に,反応規則の適用モードを「(極大並列ではなく)逐次的適用(すなわち,上記のαが1つの反応aの場合)」に焦点をあて,そのときの反応オートマトンの生成能力について考察を行った.すなわち,外部入力列a1,...,anがRA:Mによって受理されるとは,指定された状態の多重集合T0から,指定された最終状態の多重集合Fへ至る遷移の系列:T0⇒a1 T1⇒a2 T2 ⇒・・・⇒an Tn⇒・・・⇒Fが存在するときと定義する(ただし,ここでは各遷移における逐次的に適用される反応規則は省略されている).そして,このように受理される入力列全体からなる集合L(M)をMによって受理される言語とよび,その数学的性質(計算量)を理論的に解析した. RAは化学反応系をモデル化した記号列受理器であり,(従来型のオートマトンと異なり)試験管内や細胞内の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴がある.得られた結果は以下の通りである. 入力のサイズnをパラメタとしたとき,計算に用いる多重集合のサイズが関数s(n)以下であるように制限されたRAをs(n)-限定RAとよぶ.このとき,(i) 言語Lがあるs(n)-限定RAによって受理される必要十分条件は,Lがlog s(n)限定のTuring   Machine (TM)で受理されることである.また,(ⅱ) s(n)が指数関数であるようなs(n)-限定RAによって受理される集合の族は,文脈依存言語族  CSLに一致する,ことが示された.さらに,s(n)-制限というTMの部分クラスを新たに考案し,その計算能力を探究した.このs(n)-制限TM:Mとは,「サイズnの入力を受理するならば,入力途中で読まれた接頭辞の長さをd(

反応オートマトンによる生体化学反応系の構成的解析

2015年度

研究成果概要: 反応オートマトン(RA: Reaction Automaton)は自然計算における計算モデルのひとつである“化学反応系に基づく計算システム”である.本研究においては,反応a=(R,I,P)のうちで抑制分子Iがない場合の... 反応オートマトン(RA: Reaction Automaton)は自然計算における計算モデルのひとつである“化学反応系に基づく計算システム”である.本研究においては,反応a=(R,I,P)のうちで抑制分子Iがない場合のRAをChemical RA(CRA)として定義し,その計算能力について解析し以下の結果をえた.1).空入力モードを許す極大並列適用によるCRAは,チューリング万能計算能力をもつ.2).空入力モードを許す逐次的適用によるCRAは,ペトリネットの計算能力と同等である.(即ち,逐次的適用による計算能力は極大並列適用よりも真に劣る.)3).RAモデルによる計算に関する限り,反応aにおける抑制分子Iの存在の有無は,極大並列適用と逐次的適用とにおいて大きな差異を生じることが示された.

反応オートマトンによる化学反応の構成的解析

2015年度

研究成果概要:FAMMの研究目的は,「メモリとして多重集合のみを許される有限オートマトンの計算能力を解析する」ことである.この研究テーマに関する予想として「多重集合というが概念が情報を保持するデータ構造として極めてシンプルである(すなわち,記号...FAMMの研究目的は,「メモリとして多重集合のみを許される有限オートマトンの計算能力を解析する」ことである.この研究テーマに関する予想として「多重集合というが概念が情報を保持するデータ構造として極めてシンプルである(すなわち,記号列のような記号の順序情報が保持できない)ことから,FAMMの計算能力は限られている」と思われていた.研究の結果,FAMMという形式的枠組みにを用いて,従来から研究が行われている計算モデルであるチューリング機械を中核とするオートマトン理論を再構築することができた.これらの結果は,多重集合による計算/情報処理能力を解明する新しい知見を与えている.

オートマタ理論に基づく生体化学反応系の構成的解析

2016年度

研究成果概要:化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり“化学反応系に基づく計算システム”である.CRAにおいて計算過程が一意的に後戻り可能な計算だけを許すモデルを可...化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり“化学反応系に基づく計算システム”である.CRAにおいて計算過程が一意的に後戻り可能な計算だけを許すモデルを可逆的とよぶ.本研究では,この可逆的CRAに関する計算能力について考察し,以下の結果を得た.(1). 空入力モードを許す可逆的CRAの計算能力はペトリネットの計算能力より真に劣る.(2). 可逆的CRAの計算能力は正規言語のクラスと比較不可能な位置づけにある.以上により,CRAによる可逆的な計算能力の計算量理論における位置づけが解明され,化学反応による可逆的計算の理論的な限界に関する知見を得た.

オートマタ理論に基づく生体科学反応系の構成的解析

2016年度

研究成果概要:化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり“化学反応系に基づく計算システム”である.この計算モデルにおいて,状態遷移が一意にきまる決定性モデルの計算能力...化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり“化学反応系に基づく計算システム”である.この計算モデルにおいて,状態遷移が一意にきまる決定性モデルの計算能力について以下の結果を得た.(1). 決定性CRAの逐次的適用による計算能力は,ペトリネットの計算能力よりも真に劣る.(2). 空入力モードを許す決定性CRAの計算能力は決定性CRAの計算能力以下である.以上により,CRAによる決定性の計算能力の計算量理論における位置づけが解明され,化学反応による決定性計算の理論的な限界に関する知見が得られた.

反応オートマタ理論に基づく化学反応計算系の基礎的研究

2017年度

研究成果概要:Chemical reaction automata (CRAs) arecomputing models with multiset storage based on multiset rewriting introducedi...Chemical reaction automata (CRAs) arecomputing models with multiset storage based on multiset rewriting introducedin Okubo and Yokomori in 2014. A CRA consists of a finite set of reactions (orpairs of multisets called reactants and products, respectively) and an initialmultiset as well as a set of final multisets. Taking an input symbol in the currentconfiguration (multiset) a CRA changes it into a new configuration. Thus, a CRAoffers an automaton-like computing model to investigate the computational   analysis of chemical reactions. On the otherhand, since any (irreversible) Turing machine was proven by Bennett to beeffectively simulated by a reversible Turing machine, reversible computing hasbecome a research field that has been receiving increased attention. In thispaper, we introduce the notions of determinism and reversibility into CRAs, andinvestigate the computational powers of those classes of CRAs in comparisonwith the language classes of Chomsky hierarchy. The computing power ofreversible CRAs involves the physical realization of molecular programming ofchemical reaction networks with DNA strand displacement system implementation,and therefore, it is of great significance to elucidate the computing capabilitiesof both deterministic and reversible CRAs from the theoretical viewpoint ofmolecular computing.

DNAコンピュータの計算モデルの研究

1998年度

研究成果概要: 従来のシリコンベース・ノイマン型コンピュータの計算能力の限界を乗り越えるための研究動向の一つとして、DNAなどのミクロ分子を用いた計算機の研究が進んでいる。本研究ではDNAコンピュータの開発の理論的な基盤を構築するための計算モ... 従来のシリコンベース・ノイマン型コンピュータの計算能力の限界を乗り越えるための研究動向の一つとして、DNAなどのミクロ分子を用いた計算機の研究が進んでいる。本研究ではDNAコンピュータの開発の理論的な基盤を構築するための計算モデルの提案を行った。1994年の科学誌Scienceに発表されたAdlemanによる有向ハミルトンパス問題の分子生物学的解放において用いられた基本的な操作はアニーリング(annealing)、融解(melting)、検知(detection)などであるが、本研究の過程において「これらの基本操作と自己組織(自律)的な性質に基づく計算メカニズム」が実際的な実現可能性からみて最も有力な、かつ有益な計算モデルであろうという知見が得られた。そこで、この視点から研究を続けた結果、『有限個の基本DNA構造分子から、アニーリング・融解・検知操作のみを用いて万能計算能力を実現する(すなわち、チューリング計算可能な)自己組織型の計算モデル:YAC(Yet Another Computation of Self-Assembly)』を提案することができた。この計算モデルは、計算能力の万能性、基本操作の実装における容易性、クラスNPの多項式時間DNA計算可能性、などにおいて優れた特徴をもつと言える。一方、その実装モデルによる計算においては、問題サイズの増大に比例して膨大なDNA分子量を必要とするという問題点が理論的に指摘される。したがって、本計算モデルの基本的枠組みを維持しつつ、かつ現実的な資源量で計算が可能な問題のクラスとその実現方法の探求が、今後の残された重要な課題であると思われる。

構造的分子計算理論-自律的計算系の解析と設計のための基礎理論

2002年度共同研究者:上田和紀, 楠元範明

研究成果概要: 研究実績の概要は以下の3つに分類される.(1) 〈 自律的計算モデルの再考 〉 Adlemanによる有向ハミルトンパス問題(DHPP)に対するDNAを用いた解法を基本として幾つかの自律的計算モデルが提案され,自律的計算系の計算論... 研究実績の概要は以下の3つに分類される.(1) 〈 自律的計算モデルの再考 〉 Adlemanによる有向ハミルトンパス問題(DHPP)に対するDNAを用いた解法を基本として幾つかの自律的計算モデルが提案され,自律的計算系の計算論的な万能性もよく知られているが,一般に,そこでは分子配列の設計という問題が重要な要素を占める.本研究では,長さのみによる分子配列の設計法に関して探究し,有限オートマトンやDHPPなどがそのような簡単な設計によっても解決されることを示した.(2) 〈 挿入・削除システムの解析 〉DNAを用いた計算モデルのひとつとして挿入・削除システムが提案されている.これは特定のDNA配列がある認識部位において挿入されたり,削除される現象をモデル化したものであり,その計算能力は万能であることが知られている.本研究では,このシステムが理論的に万能性を保持しながらどこまで簡約化できるかを探究し,認識部位および挿入・削除記号列の長さが共に1まで簡約化が可能であることを示した.(3)〈 並列計算系による分子計算シミュレータの設計と試作 〉分子計算系における局所的並列性をシリコン上で実装するために,ノードの多重集合,膜とその階層化,リンク,グラフ変換の四概念に基づく新たな計算モデル LMNtal の設計に着手し,基本設計をほぼ完了した.また,Java を用いて試作処理系のコンパイラとランタイムを実装した.LMNtal は 1. 多重集合や会合概念をもった数多くの計算モデルの統合 2. リソースコンシャスな計算の基本モデルなどを目指したモデルであり,今年度は上記に加えて他の計算モデルとの比較検討も進めた.

海外研究活動

研究課題名: 帰納的学習の基礎理論とその生命情報学への応用

2006年03月-2007年03月

機関: ブリティッシュコロンビア大学(カナダ)、セビリア大学(スペイン)、サンテティエンネ大学(フランス)

現在担当している科目

科目名開講学部・研究科開講年度学期
応用数学3教育学部2019春学期
応用数学4教育学部2019秋学期
情報数学3教育学部2019春学期
情報数学4教育学部2019秋学期
数学演習1 L教育学部2019通年
数学演習2 L教育学部2019通年
数学序論2教育学部2019秋学期
情報数学特論II-1大学院教育学研究科2019春学期
情報数学特論II-2大学院教育学研究科2019秋学期