Name

YOKOMORI, Takashi

Official Title

Professor

Affiliation

(School of Education)

Contact Information

Mail Address

Mail Address
yokomori@waseda.jp

Address・Phone Number・Fax Number

Address
1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, JAPAN
Phone Number
+81-3-3202-8373
Fax Number
+81-3-3207-8857

URL

Web Page URL

http://www.f.waseda.jp/yokomori/

Grant-in-aids for Scientific Researcher Number
60139722

Sub-affiliation

Sub-affiliation

Faculty of Education and Integrated Arts and Sciences(Graduate School of Education)

Research Council (Research Organization)/Affiliated organization(Global Education Center)

Affiliated Institutes

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

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

理工学総合研究センター

兼任研究員 1989-2006

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

兼任研究員 2006-2018

教育総合研究所

兼任研究員 1989-

Educational background・Degree

Educational background

-1974 University of Tokyo Faculty of Science Department of Mathematics
-1979 University of Tokyo Graduate School, Division of Science fundamental science

Degree

Doctor of Science, University of Tokyo

Career

Refer to URL: http://www.f.waseda.jp/yokomori/
for the details.

Academic Society Joined

Information Processing Society of Japan

The Japanese Society for Artificial Intelligence

Japanese Society for Bioinformatics

Association for Computing Machinery

European Association for Theoretical Computer Science

OfficerCareer(Outside the campus)

2015/01-2015/12Applied Soft Computing (Elsevier)Editor
2003/09-Theoretical Computer Science (Elsevier)Editor
2000/09-2003/12GrammarsEditor
1999/09-2010/03Fundamenta Informaticae (IOS Press)Editor
1999/06-2001/05Information Processing Socity of JapanEditor-in-Chief, Fundamental Area
1994/05-1996/10The Institute of Electronics, Information and Communication EngineersEditor for Area D
1986/05-1994/04The Institute of Electronics, Information and Communication EngineersReviewer
1995/05-1996/10Information Processing Society of JapanEditor
2011/09-Development in Language Theory (International Conference Series)Steering Committee Member
2018/08-SpringerAdvisory Board of the Springer Natural Computing Book Series

Award

Fellow

2019/06Conferment Institution:Information Processing Society of Japan

Research Field

Keywords

Compuer Science(Formal Language Theory, Computational Learning Theory, Molecular Computing Theory), Bioinformatics

Grants-in-Aid for Scientific Research classification

Informatics / Principles of Informatics / Theory of informatics

Research interests Career

Theory of Automata and Formal Languages

Current Research Theme Keywords:automaton, formal grammar, formal language, computing theory

Individual research allowance

Computational Learning Theory

Current Research Theme Keywords:Grammatical Inference, Inductive Learning, Machine Learning

Individual research allowance

Bioinformatics

Current Research Theme Keywords:Genome Sequence Analysis, Genome Structure Prediction

Individual research allowance

2002-2006Natural Computing Theory

Current Research Theme Keywords:Molecular Computing Models, Self-assembly Computation, Molecular Programming, Computing by Chemical Reaction

Cooperative Research within Japan

Paper

Decomposition and factorization of chemical reaction transducers

F.Okubo and T.Yokomori

Theoretical Computer Science 777p.431 - 4422019/06-

Computing with Multisets : A Survey on Reaction Automata Theory

T.Yokomori and F.Okubo

Lecture Notes in Computer Science 10936p.421 - 4312018/07-

Natural Computing Paradigm ─ A Concise Introduction

T.Yokomori

Journal of Robotics, Networking and Artificial Life 5(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 Informaticae 154p.323 - 3412017/08-

DOI

Detail

Outline:New morphic characterizations in the form of a noted Chomsky-Schu¨tzenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h(Tk ∩FR) for some 2-star language FR, an extended 2-star language Tk and a weak coding h. (ii)Each λ-freecontext-freelanguage L canbeexpressedas L = h(Dn∩FL) forsome2-local language FL and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h(Bn ∩FL), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.

The computational capability of chemical reaction automata

Okubo, Fumiya; Yokomori, Takashi

Natural Computing 15(2) p.215 - 2242016/06-2016/06

DOIScopus

Detail

ISSN:15677818

Outline:© 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 Computing 15p.215 - 2242016-

DOI

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

Okubo, Fumiya;Yokomori, Takashi

FUNDAMENTA INFORMATICAE 138(1-2) p.31 - 442015-2015

DOIWoS

Detail

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, Springer 8727p.53 - 662014-

Recent developments on reaction automata theory: A survey

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

Automata inspired by biochemical reaction (New Trends in Algorithms and Theory of Computation)

Okubo Fumiya;Kobayashi Satoshi;Yokomori Takashi

RIMS Kokyuroku 1799p.179 - 1822012/06-2012/06

CiNii

Detail

ISSN:1880-2818

On the Properties of Language Classes of Bounded Reaction Automata

Theoretical Computer Science Vol.454p.206 - 2212012-

Reaction Automata

Theoretical Computer Science Vol.429p.247 - 2572012-

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

Intern. J. of Foundations of Computer Science Vol.22(No.1) p.247 - 2602011-

Spiking Neural dP-systems

Fundamenta Informaticae Vol.111p.423 - 4362011-

On the Hairpin Incompletion

Okubo, Fumiya;Yokomori, Takashi

FUNDAMENTA INFORMATICAE 110(1-4) p.255 - 2692011-2011

DOIWoS

Detail

ISSN:0169-2968

Spiking Neural dP Systems

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

FUNDAMENTA INFORMATICAE 111(4) p.423 - 4362011-2011

DOIWoS

Detail

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 SCIENCE 22(1) p.247 - 2602011-2011

DOIWoS

Detail

ISSN:0129-0541

On spiking neural P systems

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

Natural Computing 9(2) p.475 - 4912010-2010

DOIWoS

Detail

ISSN:1567-7818

SOME REMARKS ON THE HAIRPIN COMPLETION

Manea, Florin;Mitrana, Victor;Yokomori, Takashi

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 21(5) p.859 - 8722010-2010

DOIWoS

Detail

ISSN:0129-0541

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

Algorithmic Bioprocesses, Springer p.293 - 3092009-

DOI

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

Theoretical Computer Science 410p.417 - 4252009-

Some Remarks on the Hairpin Completion

Proceedings of 12th Intern. Conf. on Automata and Formal Languages 2008/05-

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

Natural Computing 7p.124 - 1432008-

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

Intern. J. of Foundations of Computer Science 19p.859 - 8712008-

Special Issue on DNA Computing

(edited) C.Mao and T.Yokomori

Natural Computing 7(2) 2008-

Special Issue on Spiking Neural P systems

(edited)

Natural Computing 7(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, Slovakia p.129 - 1402007/07-

Spiking Neural P Systems with an Exhaustive Use of Rules

International Journal of Unconventional Computing 3(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 Science 42872006/11-

Spiking Neural Psystems

Fundamenta Informaticae 71(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, Ontario p.139 - 1502005/06-

A simple classification of the volvocine algae by formal languages

Bulletin of Mathematical Biology 67p.1339 - 13542005-

On the Power of Membrane Division in P systems

Theoretical Computer Science 324(1) p.61 - 852004/09-

An Algorithm for Testing Structure Freeness of Biomolecular Sequences

Lecture Notes in Computer Science/Springer Vol. 2950p.266 - 2772004-

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

Proc. of 7th ICGI (Lecture Notes in Artificial Intellignece) /Springer 3264p.53 - 642004-

On the Computational Power of Insertion-Deletion Systems

Natural Computing/Kluwer Academic Vol.2, Nol.4p.321 - 3362003-

Polynomial-time identification of very simple grammars from positive data

Theoretical computer science Vol.298p.179 - 2062003-

A Magic Pot : Self-assembly computation revisited

Formal and Natural Computing, Lecture Notes in Computer Science Vol.2300p.418 - 4292002-

Molecular Computing Paradigm - Toward freedom from Turing's charm

Natural Computing Vol.4, No.1p.333 - 3902002-

On the Computational Power of Insertion-Deletion Systems

Lecture Notes in Computer Science/Springer Vol.2568p.269 - 2802002-

分子コンピューティング

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

Toward Soft Hardware

Soft Computing/Springer 5;22001/05-

Hairpin Languages

International Journal of Foundations of Computer Science Vol.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

Science 288p.1223 - 12262000-

On the Universality of Post and Splicing Systems

Theoretical Computer Science/Elsevier 231p.157 - 1702000-

Simulating H systems by P systems

Journal of Universal Computer Science/Springer-Verlag 6p.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/AMS p.213 - 2271999/06-

YAC: Yet Another Computation Model of Self-Assembly

Proc. of 5th DIMACS Workshop on DNA based Computers/AMS p.153 - 1671999/06-

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

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

Tree Adjoining Grammars for RNA Structure Prediction

Theoretical Computer Science/Elsevier 210p.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/IEEE 20;10p.1067 - 10791998/10-

Locality, Reversibility and Beyond: Learning Languages from Positive Data

Proc. of 9th Conference on Algorithmic Learning Theory(ALT98), LNAI/Springer-Verlag 1501p.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 Computers p.334 - 3471997/06-

DNA Implementation of Simple Horn Clause Computation

Proc. of IEEE Intern. Conference on Evolutionary Computation p.213 - 2171997/04-

On the Power of Circular Splicing Systems and DNA Computability

Proc. of IEEE Intern. Conference on Evolutionary Computation p.219 - 2241997/04-

Learning Approximately Regular Languages with Reversible Languages

Theoretical Computer Science 174p.251 - 2571997-

Families of Noncounting Languages and Their Learnability from Positive Data

International J. of Foundations of Computer Science 7;4p.309 - 3271996-

Learning Two-Tape Automata from Queries and Counterexamples

Mathematical Systems Theory 29;3p.259 - 2701996-

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

Machine Learning 19;2p.153 - 1791995-

(Only since 1995)

Books And Publication

オートマトン・言語理論(第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-

Lecture And Oral

Natural Computing Paradigm -- A Concise Introduction

Takashi Yokomori

The 2018 International Conference on Artificial Life and Robotics(ICAROB Society (ALife Robotics Corporation Ltd.))Invitation Yes2018/02/01

Detail

International conferenceOral presentation(invited, special)Venue:Peppu, Oita

Outline: Natural computing (NC), a main theme in this talk, is an emerging area of research that investigates computing techniques and models inspired by nature on one hand, and it also investigates phenomena taking place in nature in terms of computational methodologies on the other hand. Thus, research in NC congenitally has interdisciplinary flavor, which bridges between computer science and various disciplines of natural science. Because of its interdisciplinary nature, NC connects and covers a broad spectrum of fundamental research fields including biology, chemistry, physics, medical science, and so forth. In this talk, we give a concise introduction to the new paradigm of NC. Specifically, we give an overview of selected topics of the field from theory to experiments, while the stress is primarily put on theoretical achievements in computing paradigms such as molecular computing and chemical computing.

Introduction to Natural Computing (Tutorial Lecture)

Takashi Yokomori

The 8th Intern. Meeting on DNA Based ComputersInvitation Yes2002/06/10

Detail

International conferenceTutorialVenue:Sapporo

Research Grants & Projects

Grant-in-aids for Scientific Research Adoption Situation

Research Classification:

Development and Evaluations of Efficient Algorithms for Finding a Maximum Clique Based upon Nueral Networks

Allocation Class:¥2800000

Research Classification:

Design and Implementation of Chemical Reaction Circuits for Molecular Robots with Intelligence

2012/-0-2017/-0

Allocation Class:¥190320000

On-campus Research System

Special Research Project

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

1998

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

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

2002Collaborator:上田和紀, 楠元範明

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

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

2011Collaborator:大久保文哉

Research Results Outline:申請者らはここ数年来,分子計算の分野において主に形式言語理論による配列集合に対する特徴付けを研究してきた.その過程において,与えられた記号列から新たな申請者らはここ数年来,分子計算の分野において主に形式言語理論による配列集合に対する特徴付けを研究してきた.その過程において,与えられた記号列から新たな記号列を生成する「ヘアピン・コンプレッション」(HC: hairpin completion)とい...申請者らはここ数年来,分子計算の分野において主に形式言語理論による配列集合に対する特徴付けを研究してきた.その過程において,与えられた記号列から新たな記号列を生成する「ヘアピン・コンプレッション」(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の計算能力は文脈依存言語族と一致する.これらの結果は,化学反応による計算/情報処理能力を解明する新しい知見を与える.

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

2012Collaborator:大久保文哉

Research Results Outline:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応には反応分子(R), 抑制分子(I), 生成分子(申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応には反応分子(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

Research Results Outline:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行って来た.その結果,少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行って来た.その結果,少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重集合とみなすことにより,計算過程を多重集合の“置き換え系”としてモデル化できる」ことを確認した.こ...申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行って来た.その結果,少数分子を扱う分子反応系は一般に「分子をふくむ溶液を多重集合とみなすことにより,計算過程を多重集合の“置き換え系”としてモデル化できる」ことを確認した.これらの知見から,多重集合を計算の作業領域(メモリ領域)とするオートマトン・モデルという着想に至り,これを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]).

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

2013Collaborator:大久保文哉

Research Results Outline:申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応は反応分子(R), 抑制分子(I), 生成分子(P申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応は反応分子(R), 抑制分子(I), 生成分子(P)の3つが関わるとして抽象化し,これを多重集合の3つ組a=(R,I,P)で定式化した.この3つ組に...申請者らはここ数年来,化学反応系をモデル化した計算システムの理論的解析を行っている.一般に,化学反応は反応分子(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

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

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

2015

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

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

2016

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

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

2016

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

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

2017

Research Results Outline:Chemical reaction automata (CRAs) arecomputing models with multiset storageChemical reaction automata (CRAs) arecomputing models with multiset storage based on multiset rewriting introducedin Okubo a...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.

Foreign Countries Research Activity

Research Project Title: 帰納的学習の基礎理論とその生命情報学への応用

2006/03-2007/03

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

Lecture Course

Course TitleSchoolYearTerm
Applied Mathematics 3School of Education2019spring semester
Applied Mathematics 4School of Education2019fall semester
Informatics3School of Education2019spring semester
Informatics4School of Education2019fall semester
Seminar in Mathematics 1 LSchool of Education2019full year
Seminar in Mathematics 2 LSchool of Education2019full year
Introduction to Mathematics 2School of Education2019fall semester
Special Studies in Information Science and Mathematics II-1Graduate School of Education2019spring semester
Special Studies in Information Science and Mathematics II-2Graduate School of Education2019fall semester