博士（工学）, 東京大学

Doctor of Engineering, The University of Tokyo

RNA/DNA Secondary Structure Analysis

Molecular Computing

Grammatical Inference

Computational Learning Theory

RNA/DNA 二次構造解析

分子計算

文法推論

計算論的学習理論

Informatics, Biological, health, and medical informatics

Informatics, Information theory

01 Oct. 2007
電気通信大学情報工学科, 教授

Mar. 1993
The University of Tokyo, Graduate School, Division of Engineering, 航空学専攻

Mar. 1990
The University of Tokyo, Graduate School, Division of Engineering, 航空学専攻

Mar. 1988
The University of Tokyo, Faculty of Engineering, 航空学科

Apr. 2024 - Mar. 2025
1 類 類長

Sep. 2022
情報処理学会, コンピュータサイエンス（CS）領域功績賞は，情報処理学会のCS領域の研究会分野において，優秀な研究・技術開発，人材育成，および研究会・研究会運営に貢献したなど，顕著な功績のあったものに贈呈されます．例年，とても著名な研究者が受賞していることが目立ちます．小林の，DNAコンピューティング分野への顕著な研究業績および、数理モデル化と問題解決研究会の運営における顕著な貢献に対して，本賞が授与されました．（受賞の連絡をいただいたのは１１月になります）
コンピュータサイエンス領域功績賞
Japan society

Jul. 2015
"40th Anniversary of Theoretical Computer Science – Top Cited Articles: 1975-2014"
Official journal

Sep. 2014
情報処理学会数理モデル化と問題解決研究会
情報処理学会数理モデル化と問題解決研究会「功績賞」, 小林 聡
Japan society, Japan

Mar. 2003
船井情報科学振興賞

May 2002
NGC (New Generation Computing) Distinguished Paper Award

A Proposal of Real-Time DNA Queue Automaton
Masayuki Nakamura; Rio Mizumoto; Daihei Ise; Satoshi Kobayashi
Corresponding, Sep. 2023, Peer-reviwed
International conference proceedings, English

Three step design of DNA sequences for temperature dependent devices
Shunpei Ando; Tatsuro Honda; Satoshi Kobayashi
Corresponding, Poster Abstracts of DNA 29, #2-26, Sep. 2023, Peer-reviwed
International conference proceedings, English

A method to simulate the derivation process of context-free grammars by DNA strand displacements
Naoyuki Hiratsuka; Satoshi Kobayashi
Corresponding, Poster Abstracts of DNA 29, #1-34, Sep. 2023, Peer-reviwed
International conference proceedings, English

Renewable Time-Responsive DNA Circuits with Photo-Responsive Bases
Taien Shimizu; Satoshi Kobayashi
Corresponding, Poster Abstracts of DNA 29, #1-24, Sep. 2023, Peer-reviwed
International conference proceedings, English

Monotone Control of R Systems
Ryutaro Yako; Daihei Ise; Ken Komiya; Kenzo Fujimoto; Satoshi Kobayashi
New Generation Computing, Springer Nature, to appear, 2, 623-657, Jul. 2022, Peer-reviwed
Scientific journal, English

On Monotone Control of Right Linear Grammars with Unknown Behaviors
Daihei Ise; Shigetaka, Nakamura; Ken Komiya; Kenzo Fujimoto; Satoshi Kobayashi
Poster Abstracts of DNA 27, P-D-002, Sep. 2021, Peer-reviwed
International conference proceedings, English

DNA Sequence Search for Temperature Dependent DNA Devices
Takayuki Suzuki; Ken Komiya; Satoshi Kobayashi
Poster Abstracts of DNA 27, P-B-004, Sep. 2021, Peer-reviwed
International conference proceedings, English

Reducing Control Alphabet Size for the Control of Right Linear Grammars with Unknown Behaviors
Nobuya Kimoto; Shigetaka Nakamura; Ken Komiya; Kenzo Fujimoto; Satoshi Kobayashi
Theoretical Computer Scinece, Elsevier, 862, 193-213, 16 Mar. 2021, Peer-reviwed
Scientific journal, English

Monotonically controlling right linear grammars with unknown behaviors to output a target string
Nobuya Kimoto; Ken Komiya; Kenzo Fujimoto; Satoshi Kobayashi
THEORETICAL COMPUTER SCIENCE, 777, 387-408, Jul. 2019, Peer-reviwed
Scientific journal, English

Leak-free Million-fold DNA Amplification with Locked Nucleic Acid and Targeted Hybridization in One Pot
K. Komiya; M. Komori; C. Noda; S. Kobayashi; T. Yoshimura; M. Yamamura
Organic & Biomolecular Chemistry, Royal Society of Chemistry, 17, 23, 5708-5713, 2019, Peer-reviwed
Scientific journal, English

DNA Computing Boosted by a Cationic Copolymer
Naohiko Shimada; Ken Saito; Takafumi Miyata; Hiroki Sato; Satoshi Kobayashi; Atsushi Maruyama
Advanced Functional Materials, Wiley-VCH Verlag, 28, 17, 1707406-6pages, 25 Apr. 2018, Peer-reviwed
Scientific journal, English

Photochemical Acceleration of DNA Strand Displacement by Using Ultrafast DNA Photo-crosslinking
Shigetaka Nakamura; Hirokazu Hashimoto; Satoshi Kobayashi; Kenzo Fujimoto
CHEMBIOCHEM, 18, 20, 1984-1989, Oct. 2017, Peer-reviwed
Scientific journal, English

Engineering multistate DNA molecules: a tunable thermal band-pass filter
John A. Rose; Ken Komiya; Satoshi Kobayashi
MICRO & NANO LETTERS, 11, 10, 595-601, Oct. 2016, Peer-reviwed
Scientific journal, English

Molecular computers for molecular robots as hybrid systems
Masami Hagiya; Nathanael Aubert-Kato; Shaoyu Wang; Satoshi Kobayashi
THEORETICAL COMPUTER SCIENCE, 632, 4-20, Jun. 2016, Peer-reviwed
Scientific journal, English

Analog DNA Computing Devices Toward the Control of Molecular Robots
Satoshi Kobayashi; Kazuya Yanagibashi; Ken Komiya; Kenzo Fujimoto; Masami Hagiya
Proc. of Workshop on Self-organization in Swarm of Robotics, CD-ROM, 06 Oct. 2014, Invited
International conference proceedings, English

Molecular Robots with Sensors and Intelligence
Masami Hagiya; Akihiko Konagaya; Satoshi Kobayashi; Hirohide Saito; Satoshi Murata
ACCOUNTS OF CHEMICAL RESEARCH, 47, 6, 1681-1690, Jun. 2014, Peer-reviwed
Scientific journal, English

DNA Domino Toppling: Speeding Up DNA Logic Circuits by Localizing Reaction -- Simulation Study --
Satoshi Kobayashi; Ryohei Nagaswa
Proceedings of 19th International Conference on DNA Computing and Molecular Programming, Arizona State University, 44, 24 Sep. 2013, Peer-reviwed
International conference proceedings, English

Enumeration approach to computing chemical equilibria
Satoshi Kobayashi
THEORETICAL COMPUTER SCIENCE, 499, 51-87, Aug. 2013, Peer-reviwed
Scientific journal, English

Molecular Robotics: A New Paradigm for Artifacts
Satoshi Murata; Akihiko Konagaya; Satoshi Kobayashi; Hirohide Saito; Masami Hagiya
NEW GENERATION COMPUTING, 31, 1, 27-45, Jan. 2013, Peer-reviwed
Scientific journal, English

Enumeration Approach to the Analysis of Interacting Nucleic Acid Strands
Satoshi Kobayashi; Takaya Kawakami
Biomolecular Information Processing: From Logic Systems to Smart Sensors and Actuators, Wiley-VCH, 225-244, 21 Dec. 2012, Peer-reviwed
In book, English

On the properties of language classes defined by bounded reaction automata
Fumiya Okubo; Satoshi Kobayashi; Takashi Yokomori
THEORETICAL COMPUTER SCIENCE, 454, 206-221, Oct. 2012, Peer-reviwed
Scientific journal, English

Reaction automata
Fumiya Okubo; Satoshi Kobayashi; Takashi Yokomori
THEORETICAL COMPUTER SCIENCE, 429, 247-257, Apr. 2012, Peer-reviwed
Scientific journal, English

Molecular computing machineries-computing models and wet implementations
Masami Hagiya; Satoshi Kobayashi; Ken Komiya; Fumiaki Tanaka; Takashi Yokomori
Handbook of Natural Computing, Springer Berlin Heidelberg, 3-4, 1130-1184, 01 Jan. 2012
In book, English

Enumeration Approach to the Analysis of Interacting Nucleic Acid Strands
Takaya Kawakami; Satoshi Kobayashi
Proc. of 17th International Conference on DNA Computing and Molecular Programming, Abstracts of Talks and Posters, 47, Sep. 2011, Peer-reviwed
International conference proceedings, English

Enumeration Approach to the Computational Analysis of High-Dimensional Monomolecular Chemical Master Equation
Satoshi Kobayashi
Proc. of 17th International Conference on DNA Computing and Molecular Programming, Abstracts of Talks and Posters, 52, Sep. 2011, Peer-reviwed
International conference proceedings, English

Efficient and Approximate Simulation Algorithm of Kinetic Folding of an RNA Molecule
Takumi Tanigawa; Satoshi Kobayashi
Proc. of The 2011 International Conference on Parallel and Distributed Processing Techniques and Applications, 706-712, Jul. 2011, Peer-reviwed
International conference proceedings, English

DNA Logic Circuits with a DNA Polymerase and a Nicking Enzyme
Ryo Hirose; Satoshi Kobayashi; Ken Komiya
Proc. of The 2011 International Conference on Parallel and Distributed Processing Techniques and Applications, 713-719, Jul. 2011, Peer-reviwed
International conference proceedings, English

Efficient State Minimization Algorithm of Linear Separation Automata
Yuji Numai; Satoshi Kobayashi
Proc. of PDPTA 2010, 633-639, Jul. 2010, Peer-reviwed
International conference proceedings, English

Theory of Minimizing Linear Separation Automata
Yuji Numai; Yoshiaki Udagawa; Satoshi Kobayashi
IPSJ Transactions on Mathematical Modeling and Its Applications, Information Processing Society of Japan, Vol.3, No.2, 83-91, Mar. 2010, Peer-reviwed, In this paper, we theoretically analyze a certain extension of a finite automaton, called a linear separation automaton (LSA). An LSA accepts a sequence of real vectors, and has a weight function and a threshold sequence at every state, which determine the transition from some state to another at each step. Transitions of LSAs are just corresponding to the behavior of perceptrons. We develop the theory of minimizing LSAs by using Myhill-Nerode theorem for LSAs. Its proof is performed as in the proof of the theorem for finite automata. Therefore we find that the extension to an LSA from the original finite automaton is theoretically natural.
Scientific journal, English

Necessary and Sufficient Conditions for Learning with Correction Queries
Cristina Tirnauca; Satoshi Kobayashi
Theoretical Computer Science, 410, 5145-5157, 2010, Peer-reviwed
Scientific journal, English

State and Threshold Sequence Minimization Algorithm of Linear Separation Automata
Yuji Numai; Yoshiaki Udagawa; Satoshi Kobayashi
IPSJ Transactions on Mathematical Modeling and Its Applications, Information Processing Society of Japan, 3, 3, 67-79, 2010, Peer-reviwed, In this paper, we present a minimization algorithm of the number of states of a linear separation automaton (LSA). An LSA is an extended model of a finite automaton. It accepts a sequence of real vectors, and has a weight and a threshold sequence at every state, which determine the transition from the current state to the next at each step. In our previous paper, we characterized an LSA and the minimum state LSA. The minimum state version for a given LSA M is obtained by the algorithm presented in this paper. Its time complexity is O(( K + k )n²), where K is the maximum number of threshold values assigned to each weight, k is the maximum number of edges going out from a state of M, and n is the number of states in M. Moreover, we discuss the minimization of a threshold sequence at each state.
Scientific journal, English

Applying Symmetric Enumeration Method to One-Dimensional Assembly of Rotatable Tiles
Satoshi Kobayashi
ALGORITHMIC BIOPROCESSES, 159-183, 2009, Peer-reviwed
International conference proceedings, English

A Software Tool for Analyzing Combinatorial Hybridization Reaction Systems
Satoshi Kobayashi
Proc. of 14th International Meeting on DNA Based Computing, to appear, Jun. 2008, Peer-reviwed
International conference proceedings, English

Symmetric Enumeration Method: A New Approach to Computing Equilibria
Satoshi Kobayashi
Technical Report of Dept. of Computer Science, University of Electro-Communications, CS08, 01, Mar. 2008
Research institution, English

Exact and Efficient Equilibrium State Analysis of Interacting RNA Molecules
Satoshi Kobayashi
Proc. of 6th Asia Paciffic Bioinformatics Conference, P93, 2008
International conference proceedings, English

Stochastically Approximating Tree Grammars by Regular Grammars and Its Application to Faster ncRNA Family Annotation
Kazuya Ogasawara; Satoshi Kobayashi
Proc. of LATA' 2007, 461-472, 2007, Peer-reviwed
International conference proceedings, English

A Characterization of Language Classes Learnable with Correction Queries
Cristina Tirnauca; Satoshi Kobayashi
Proc. of TAMC'2007, 398-407, 2007, Peer-reviwed
International conference proceedings, English

Stochastic Regular Approximation of Tree Grammars and Its Application to Faster ncRNA Family Annotation
Kazuya Ogasawara; Satoshi Kobayashi
IPSJ Transaction on Bioinformatics, Information Processing Society of Japan (IPSJ), 48, SIG17, 19-29, 2007, Peer-reviwed, Tree Adjoining Grammar (TAG) is a useful grammatical tool to model RNA secondary structures containing pseudoknots, but its time complexity for parsing is not small enough for the practical use. Recently, Weinberg and Ruzzo proposed a method of approximating stochastic context free grammar by stochastic regular grammar and applied it to faster genome annotation of non-coding RNA families. This paper proposes a method for extending their idea to stochastic approximation of TAGs by regular grammars. We will also report some preliminary experimental results on how well we can filter out non candidate parts of genome sequences by using obtained approximate regular grammars.
Scientific journal, English

Stochastically Approximating Tree Grammars by Regular Grammars and Its Application to Faster ncRNA Family Annotation
Kazuya Ogasawara; Satoshi Kobayashi
1st International Conference on Language and Automata Theory and Applications, 461-472, 2007, Peer-reviwed
International conference proceedings, English

A New Approach to Computing Equilibrium State of Combinatorial Hybridization Reaction Systems
Satoshi Kobayashi
2007 2ND BIO-INSPIRED MODELS OF NETWORKS, INFORMATION AND COMPUTING SYSTEMS (BIONETICS), CD-ROM, 312-317, 2007
International conference proceedings, English

A New Approach to Computing Equilibrium State of Combinatorial Chemical Reaction Systems
Satoshi Kobayashi
Technical Report of Dept. of Computer Science, Univ. of Electro Communications, CS06, 01, Nov. 2006
Research institution, English

Efficient algorithm for testing structure freeness of finite set of biomolecular sequences
Atsushi Kijima; Satoshi Kobayashi
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3892, 171-180, 2006, Peer-reviwed
International conference proceedings, English

Probabilistic Inference in Test Tube and Its Application to Gene Expression Profiles
Y. Sakakibara; T. Yokomori; S. Kobayashi; A. Suyama
Formal Models, Languages And Applications (edited by Subramanian et al.), World Scientific Pub., 304-319, 2006, Peer-reviwed
Scientific journal, English

A grammatical approach to the alignment of structure-annotated strings
S Seki; S Kobayashi
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E88D, 12, 2727-2737, Dec. 2005, Peer-reviwed
Scientific journal, English

Efficient Algorithms for Testing Structure Freeness of Finite Set of Biomolecular Sequences
Atsushi Kijima; Satoshi Kobayashi
Preliminary Proceedings of 11th International Meeting on DNA Computing, 278-288, 2005, Peer-reviwed
International conference proceedings, English

An algorithm for testing structure freeness of biomolecular sequences
S Kobayashi; T Yokomori; Y Sakakibara
ASPECTS OF MOLECULAR COMPUTING, 2950, 266-277, 2004, Peer-reviwed
Scientific journal, English

Testing Structure Freeness of Regular Sets of Biomolecular Sequences
Satoshi Kobayashi
Preliminary Proceedings of 10th International Meeting on DNA Based Computers, 395-404, 2004, Peer-reviwed
International conference proceedings, English

Evaluating Biomolecular Sequences Using Hydrogen Bond Network Graph
Kazuya Nagatsu; Atsushi Kijima; Satoshi Kobayashi
Preliminary Proceedings of 10th International Meeging on DNA Based Computers, 441, 2004, Peer-reviwed
International conference proceedings, English

Efficient learning of k-reversible context-free grammars from positive structural examples
S Seki; S Kobayashi
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS, 3264, 285-287, 2004, Peer-reviwed
Scientific journal, English

On template method for DNA sequence design
S Kobayashi; T Kondo; M Arita
DNA COMPUTING, 2568, 205-214, 2003, Peer-reviwed
Scientific journal, English

DNA sequence design using templates
M Arita; S Kobayashi
NEW GENERATION COMPUTING, 20, 3, 263-277, 2002, Peer-reviwed
Scientific journal, English

A Magic Pot : Self-assembly computation revisited
Takashi Yokomori; Yasubumi Sakakibara; Satoshi Kobayashi
418-429, 2002, Peer-reviwed
International conference proceedings, English

Multiple splicing systems and the universal computability
S Kobayashi; Y Sakakibara
THEORETICAL COMPUTER SCIENCE, 264, 1, 3-23, Aug. 2001, Peer-reviwed
Scientific journal, English

Formal properties of PA-matching
S Kobayashi; Mitrana, V; G Paun; G Rozenberg
THEORETICAL COMPUTER SCIENCE, 262, 1-2, 117-131, Jul. 2001, Peer-reviwed
Scientific journal, English

Approximate Identification and Finite Elasticity
Satoshi Kobayashi; Yasubumi Sakakibara; Takashi Yokomori
Where Mathematics, Computer Science, Linguistics and Biology Meet, Kluwer Academic Pub., 169-189, 2001, Peer-reviwed
Scientific journal, English

Sticker Systems with Complex Structures
Yasubumi Sakakibara; Satoshi Kobayashi
Soft Computing, 5, 114-120, 2001, Peer-reviwed
Scientific journal, English

Concentration Prediction of Ligation Reaction Systems
Satoshi Kobayashi
Romanian Journal of Information Science and Technology, 4, 101-109, 2001, Peer-reviwed
Scientific journal, English

Horn Clause Computation by Self Assembly of DNA Molecules
H. Uejima; M. Hagiya; S. Kobayashi
Proc. of 7th International Meeting on DNA Based Computers, 63-74, 2001, Peer-reviwed
International conference proceedings, English

Concentration Prediction of Pattern Reaction Systems
S. Kobayashi
Pre-Proc. of Workshop on Multiset Processing, CDMTS Research Report Series（Univ. of Auckland）, 140, 112-123, Aug. 2000, Peer-reviwed
International conference proceedings, English

Iterated transductions and efficient learning from positive data: A unifying view
S Kobayashi
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, 1891, 157-170, 2000, Peer-reviwed
Scientific journal, English

On the universality of Post and splicing systems
C Ferretti; G Mauri; S Kobayashi; T Yokomori
THEORETICAL COMPUTER SCIENCE, 231, 2, 157-170, Jan. 2000, Peer-reviwed
Scientific journal, English

Horn clause computation with DNA molecules
S Kobayashi
JOURNAL OF COMBINATORIAL OPTIMIZATION, 3, 2-3, 277-299, Jul. 1999, Peer-reviwed
Scientific journal, English

Tree adjoining grammars for RNA structure prediction
Y Uemura; A Hasegawa; S Kobayashi; T Yokomori
THEORETICAL COMPUTER SCIENCE, 210, 2, 277-303, Jan. 1999, Peer-reviwed
Scientific journal, English

Learning local languages and their application to DNA sequence analysis
T Yokomori; S Kobayashi
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 20, 10, 1067-1079, Oct. 1998, Peer-reviwed
Scientific journal, English

Locality, reversibility, and beyond: Learning languages from positive data
T Head; S Kobayashi; T Yokomori
ALGORITHMIC LEARNING THEORY, 1501, 191-204, 1998, Peer-reviwed
Scientific journal, English

Learning approximately regular languages with reversible languages
S Kobayashi; T Yokomori
THEORETICAL COMPUTER SCIENCE, 174, 1-2, 251-257, Mar. 1997, Peer-reviwed
Scientific journal, English

DNA implementation of simple Horn clause computation
S Kobayashi; T Yokomori; G Sampei; K Mizobuchi
PROCEEDINGS OF 1997 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '97), 213-217, 1997, Peer-reviwed
International conference proceedings, English

On the power of circular splicing systems and DNA computability
T Yokomori; S Kobayashi; C Ferretti
PROCEEDINGS OF 1997 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '97), 219-224, 1997, Peer-reviwed
International conference proceedings, English

Identifiability of subspaces and homomorphic images of zero-reversible languages
S Kobayashi; T Yokomori
ALGORITHMIC LEARNING THEORY, 1316, 48-61, 1997, Peer-reviwed
Scientific journal, English

Families of Noncounting Languages and their Learnability from Positive Data
Satoshi Kobayashi; Takashi Yokomori
International Journal of Foundation of Computer Science, 7, 4, 309-327, 1996, Peer-reviwed
Scientific journal, English

DNA Splicing Systems and Post Systems
Claudio Ferretti; Satoshi Kobayashi
Proc. of Pacific Symp. on Biocomputing, 288-299, 1996, Peer-reviwed
International conference proceedings, English

IDENTIFYING STRATEGIES USING DECISION LISTS FROM TRACE INFORMATION
S KOBAYASHI
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E78D, 5, 545-552, May 1995, Peer-reviwed
Scientific journal, English

DNA Evolutionary Linguistics and RNA Structure Modeling
Takashi Yokomori; Satoshi Kobayashi
Proc. of IEEE Symp. on Intelligence in Neural and Biological Systems, IEEE, 38-45, 1995, Peer-reviwed
International conference proceedings, English

Approximately Learning Regular Languages with respect to Reversible Languages, A Rough Set Based Analysis
Satoshi Kobayashi; Takashi Yokomori
Proc. of 2nd Annual Joint Conference on Information Sciences, 91-94, 1995, Peer-reviwed
International conference proceedings, English

On Approximately Identifying Concept Classes in the Limit
Satoshi Kobayashi; Takashi Yokomori
Proc. of 6th Workshop on Algorithmic Learning Theory, 997, 298-312, 1995, Peer-reviwed
International conference proceedings, English

Grammatically Modeling and Predicting RNA Secondary Structures
Yasuo Uemura; Aki Hasegawa; Satoshi Kobayashi; Takashi Yokomori
Proc. of 6th Genome Informatics Workshop, 67-76, 1995, Peer-reviwed
International conference proceedings, English

Learning Local Languages and Its Application to Protein alpha-chain Identification
Takashi Yokomori; Nobuyuki Ishida; Satoshi Kobayashi
Proc. 27th Hawaii Intern. Conf. System Sci., 113-122, 1994, Peer-reviwed
International conference proceedings, English

Learning Concatenations of Locally Testable Languages from Positive Data
Satoshi Kobayashi; Takashi Yokomori
Proc. of 5th Workshop on Alogrithmic Learning Theory, 407-422, 1994, Peer-reviwed
International conference proceedings, English

An Extended Rough Set Theory Toward Approximate Learning of Formal Languages
Satoshi Kobayashi; Takashi Yokomori
Proc. of 3rd International Workshop on Rough Sets and Soft Computing, 482-489, 1994, Peer-reviwed
International conference proceedings, English

Inductive Learning of Regular Sets from Examples: A Rough Set Approach
Takashi Yokomori; Satoshi Kobayashi
Proc. of 3rd International Workshop on Rough Sets and Soft Computing, 570-577, 1994, Peer-reviwed
International conference proceedings, English

Modeling RNA Secondary Structures Using Tree Grammars
Satoshi Kobayashi; Takashi Yokomori
Proceedings of Genome Informatics Workshop V, 29-38, 1994, Peer-reviwed
International conference proceedings, English

ALGORITHMS FOR FINDING THE LARGEST SUBTREE WHOSE COPIES COVER ALL THE LEAVES
T AKUTSU; S KOBAYASHI; K HORI; S OHSUGA
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E76D, 6, 707-710, Jun. 1993, Peer-reviwed
Scientific journal, English

木パターン上の決定リストの学習とその推論制御への応用
小林聡; 大須賀節雄; 堀浩一
人工知能学会誌, 8, 6, 810-818, 1993, Peer-reviwed
Scientific journal, Japanese

LEARNING DECISION LISTS OVER TREE PATTERNS AND ITS APPLICATION
S KOBAYASHI; K HORI; S OHSUGA
IJCAI-93, VOLS 1 AND 2, 995-1000, 1993, Peer-reviwed
International conference proceedings, English

Learning Strategies Using Decision Lists
Satoshi Kobayashi
Proc. of 4th Workshop on Algorithmic Learning Theory, 744, 370-383, 1993, Peer-reviwed
International conference proceedings, English

A Similarity Measure for DNA Sequence Analysis Based on Locality
Takashi Yokomori; Satoshi Kobayashi
Proc. of Genome Informatics Workshop, Japanese Society for Bioinformatics, 4, 283-292, 1993, Peer-reviwed, We propose a simple string similarity measure and apply it to the problem of DNA sequence analysis, more specifically, to the problem of analysing molecular evolution. This measure is based on a "local feature" that was motivated from a theoretical characterization on DNA splicing sequences.
We demonstrate the usefulness of the proposed measure by presenting an experimental result which concerns evolutionary molecular analysis. This sheds new light on the other types of DNA sequence analysis such as protein classification, motif identification.
International conference proceedings, English

情報保存的な問題領域におけるトレースからの問題分割戦略の獲得
小林聡; 大須賀節雄; 堀浩一
人工知能学会誌, 7, 6, 1009-1017, 1992, Peer-reviwed
Scientific journal, Japanese

トレースを利用した戦略の獲得と知識の分類手法
小林聡; 大須賀節雄; 堀浩一; 山内平行
電子情報通信学会論文誌, 電子情報通信学会情報・システムソサイエティ, J74-D-II, 8, 1043-1051, 1991, Peer-reviwed
Scientific journal, Japanese

分子コンピュータ設計のための計算モデル
小林 聡
2019, 計測と制御, 58, 4, 241-246, Japanese, Peer-reviwed, Introduction scientific journal

分子計算の理論モデル
小林 聡; 榊原康文; 横森 貴
サイエンス社, 2000, 数理科学，サイエンス社, 38, 445(7月号), 8-14, Japanese, Introduction other, 0386-2240, 40002001550, AN00125207

Inductive Inference of Formal Languages ("Recent Dvelopments in the Theory and Applications of Machine Learning")
SAKAKIBARA Yasubumi; KOBAYASHI Satoshi; Yasubumi Sakakibara; Satoshi Kobayashi; Dept. of Information Sciences Tokyo Denki University; Dept. of Information Sciences Tokyo Denki University
形式言語の学習理論に関する研究は, 計算論的学習理論と名のつく研究分野が定着する以前から始まる. そこでは, 肯定的な結果もあれば否定的結果も存在したが, いずれにせよ言語(文法)の学習という知的活動に対する数理的理解の着実なる前進の歴史であったといえる. さて, コンピュータ(機械)が学習するということに対する明確な定義の一つをValiantは次のように与えている [Valiant 84]:「コンピュータにプログラミングによって陽にプログラムを与える以外の方法によって, コンピュータがプログラムを獲得すること」. さらにこのような機械学習において, 帰納的推論とは, 「与えられた個々の事実から一般的な規則を導き出す推論」と定義される. これを本稿の主題である形式言語の帰納的推論(文法推論)に当てはめてみると, 「言語の正しい例(言語に属する文, 正の例)と正しくない例(言語に属さない文, 負の例)から, その言語の文法規則を, 陽にプログラムとして与えることなしに, 獲得すること」となる. 本稿では, 正則言語と文脈自由言語の学習研究に焦点を絞り, 最新の成果をまとめて解説する. 正則言語も文脈自由言語も正負の例を用いるだけでは効率良く同定することは困難であることが知られている. そこで, まず最初にこの困難に立ち向かうために, 種々の最適化問題で実際的な成功を収めている遺伝的アルゴリズムを適用する意欲的な試みを紹介する. 次に, 正例からの正則言語の学習とその周辺に関する最近の理論的進展について報告する. そして最後に, 文脈自由言語と正則言語の学習アルゴリズムを遺伝子情報解析に適用した応用例を紹介する., 人工知能学会, 01 Sep. 1999, Journal of Japanese Society for Artificial Intelligence, 14, 5, 781-789, Japanese, 0912-8085, 110002808746, AN10067140

URL

分子コンピュータ --- その理論と実験
小林 聡; 榊原 康文; 陶山 明; 横森 貴
サイエンス社, 1999, Computer Today, 16, 89, 4-13, Japanese, Introduction other, 0289-3509, 40004513961, AN10012218

形式言語の帰納的学習
榊原康文; 小林聡
1999, 人工知能学会論文誌, 14, 21-29, Japanese, Introduction other

ラフ集合理論とその応用
中村昭; 津本周作; 田中博; 小林聡
1996, 人工知能学会誌, 11, 2, 35-41, Japanese, Introduction other

計算論的言語理論と DNA 計算
横森貴; 小林聡
1996, 情報処理, 37, 10, 929-934, Japanese, Introduction other

ラフ集合--その理論と応用-3-ラフ集合と意志決定
横森 貴; 小林 聡
サイエンス社, Sep. 1994, 数理科学, 32, 9, p76-83, Japanese, 0386-2240, 40002000981, AN00125207

ラフ集合と意思決定
横森貴; 小林聡
サイエンス社, 1994, 数理科学, 375, 76-83, Japanese, Introduction other, 10004745861

自然計算へのいざない
Scholarly book, Japanese, Editor, 近代科学社, 30 Nov. 2015

DNA Computing and Molecular Programming, 20th International Conference
Scholarly book, English, Editor, Springer Verlag, 22 Sep. 2014

Grammatical Inference: Algorithms and Applications, 8th International Colloquium, ICGI 2006
Yasubumi Sakakibara; Satoshi Kobayashi; Kengo Sato; Tetsuro Nishino; Etsuji Tomita, Eds
English, Editor, Springer-Verlag, Sep. 2006

Recent Advances in Formal Languages and Applications
J. Brzozowski; J. Gruska; T. Head; D. Pixton; L. Ilie; J. Kari; S. Kobayashi; H.-J. Kreowski; R. Klempien-Hinrichs; S. Kuske; M. Ogihara; F. Otto; H. Petersen; S. Wintner; H.-C. Yen
English, Joint work, Chapter 8, Mathematical Foundations of Learning Theory, Springer-Verlag, 2006

計算論的学習
榊原康文; 小林聡; 横森貴
Japanese, Joint work, 第２章 極限における学習, 培風館, 2001

DNA Computing --- New Computing Paradigms
Takashi Yokomori; Yasubumi Sakakibara; Satoshi Kobayashi
Japanese, Joint translation, 第７章～第１１章, Springer-Verlag Tokyo, 1999

DNA分子による FIFO データ構造の実装方法の提案
中村 雅之; 小林聡
Oral presentation, Japanese, 情報処理学会 数理モデル化と問題解決研究会
09 Mar. 2023
09 Mar. 2023- 10 Mar. 2023

未知の振る舞いを持つ制御付き右正則文法の生成能力について
伊勢大平; 小林 聡
Oral presentation, Japanese, 電子情報通信学会技術研究報告，コンピュ―テーション, Domestic conference
08 Mar. 2021

未知の振る舞いを持つ正則文法に対する制御システムの信号数の削減
木元達哉; 小林 聡
Oral presentation, Japanese, 電子情報通信学会技術研究報告 コンピュテーション, Domestic conference
2019

反応システムの制御における信号数の削減
矢光隆太郎; 小林 聡
Oral presentation, Japanese, 電子情報通信学会技術研究報告 コンピュ―テーション, Domestic conference
2019

Hill型の融解曲線をもつDNA塩基配列の設計
池田 亮太; 小林 聡; 小宮 健
Oral presentation, Japanese, 情報処理学会バイオ情報学研究会, Domestic conference
2019

未知の振る舞いを持つ正則文法とその制御
木元達哉; 小宮健; 藤本健造; 小林 聡
Oral presentation, Japanese, 電子情報通信学会コンピューテーション研究会, Domestic conference
26 Oct. 2018

反応システムの制御によるブール関数の計算
矢光隆太郎; 小宮健; 藤本健造; 小林聡
Oral presentation, Japanese, 電子情報通信学会コンピューテーション研究会, Domestic conference
26 Oct. 2018

Toward Design and Analysis of Analog Computing Chemical Reaction Circuits
Daiki Matsuwaki; Satoshi Kobayashi
Poster presentation, English, Chem-Bio Informatics Society(CBI) Annual Meeting 2015, Chem-Bio Informatics Society, Tokyo, Domestic conference
28 Oct. 2015

Toward Efficient Computation of Chemical Equilibria of Interacting Nucleic Acid Strands Including Pseudoknots
Mizuki Yokoshima; Satoshi Kobayashi
Poster presentation, English, Chem-Bio Informatics Society(CBI) Annual Meeting 2015, Chem-Bio Informatics Society, Tokyo, Domestic conference
28 Oct. 2015

On Time Responsive DNA Analog Computing Devices
Satoshi Kobayashi; Kazuya Yanagibashi
Poster presentation, English, International conference
28 Oct. 2014

Reaction Graphs Controlled by External Signals
Youji Hasegawa; Satoshi Kobayashi
Poster presentation, English, CBI 学会全国大会, International conference
28 Oct. 2014

鎖置換反応ダイナミクスを利用したアナログコンピュータの構築に向けて
小林聡
Oral presentation, Japanese, 分子ロボティクス研究会, 人工知能学会 分子生物情報研究会, 電気通信大学， 東京, Domestic conference
09 May 2014

分子ロボットに知性は実現できるか -計算論的立場から-
小林 聡
Invited oral presentation, Japanese, 第５１回分子生物情報研究会（SIGMBI）, 人工知能学会
Nov. 2013

グラフによる分子種の数え上げと化学反応系の解析
小林 聡
Invited oral presentation, Japanese, 「細胞を創る」研究会5.0, 細胞を創る研究会
Nov. 2013

分子ロボティクス --- 感覚と知能を備えた分子ロボットの創成 ---
小林 聡
Invited oral presentation, Japanese, 計測自動制御学会 システム・情報部門 学術講演会 2012 (SSI2012), 計測自動制御学会
Nov. 2013

Progress in Enumeration Approach to Computing Chemical Equilibrium of Interacting Nucleic Acid Strands
Satoshi Kobayashi
Poster presentation, English, CBI学会２０１４年大会, Domestic conference
28 Oct. 2013

DNA を用いた組み合わせ回路の高速化について
小林 聡; 長沢亮平; 廣瀬亮
Oral presentation, Japanese, 情報処理学会,第92回数理モデル化と問題解決研究会
Mar. 2013

知能を実現する化学反応回路の構築を目指して
小林 聡
Invited oral presentation, Japanese, 生命医薬情報学連合大会 2012, CBI, JSBi 学会
Oct. 2012

仮想核酸配列インタラクション反応系の平衡状態解析
松本典子; 小林聡
Oral presentation, Japanese, 情報処理学会研究報告,「数理モデル化と問題解決（MPS）」
2011

Enumeration Approach to the Analysis of Complex Chemical Reaction Systems
Satoshi Kobayashi
Invited oral presentation, English, The 16th International Conference on DNA Computing and Molecular Programming, Hong Kong, International conference
Jun. 2010

Enumeration of Structures and Efficient Analysis of Complicated Chemical Reaction Systems
Satoshi Kobayashi
Invited oral presentation, English, International Conference on Unconventional Computation, Tokyo, International conference
Jun. 2010

Minimization Algorithm of Linear Separation Automata
Yuji Numai; Yoshiaki Udagawa; Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Report
Mar. 2010

RNAインタラクション反応の線形な2次構造レベルでの解析アルゴリズム
川上貴也; 小林 聡
Oral presentation, Japanese, 情報処理学会研究報告
Mar. 2010

Theory of Minimizing Linear Separation Automata
Yuji Numai; Yoshiaki Udagawa; Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Report
Dec. 2009

線形分離オートマトンを用いたパターン識別手法の理論的基礎について
沼井裕二; 小林聡
Oral presentation, Japanese, IPSJ SIG Technical Report
Mar. 2009

RNA フォールディングシミュレーションのための新しいアルゴリズム
谷川拓己; 小林聡
Oral presentation, Japanese, IPSJ SIG Technical Report
Mar. 2009

On State-Merging Strategies of RPNI Algorithm that Guarantee Identifiability in the Limit
Yuji Numai; Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Report
2008

A General Framework for Efficient Equilibrium State Analysis of Hybridization Reaction Systems
Satoshi Kobayashi
Public symposium, English, Workshop on Algorithmic Bioprocesses, Lorenz Center, Leiden University, Leiden
Dec. 2007

組合せ爆発を内包する化学反応系の平衡状態計算
Satoshi Kobayashi
Oral presentation, Japanese, 情報処理学会 研究報告
Sep. 2007

Stochastic Regular Approximation of Tree Grammars and Its Application to Faster ncRNA Family Annotation
Kazuya Ogasawara; Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Reports
2007

Tree Grammars for RNA Secondary Structure Analysis
Satoshi Kobayashi
Invited oral presentation, English, The 1st International Symposium on Languages in Biology and Medicine, The 1st International Symposium on Languages in Biology and Medicine, International conference
Nov. 2005

Efficient Tree Grammatical Modeling of RNA Secondary Structures from Alignment Data
Takashi Takakura; Hiroki Asakawa; Shinnosuke Seki; Satoshi Kobayashi
Public symposium, English, Proc. of RECOMB 2005, Boston, USA
2005

A Grammatical Approach to the Alignment of SA-Strings
Shinnosuke Seki; Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Report
2005

Efficiently Evaluating Structure Freeness of Biomolecular Sequences
Satoshi Kobayashi; Kazuya Nagatsu; Atsushi Kijima
Oral presentation, English, Proc. of SICE'2004, Hokkaido
2004

Hierarchical Alignment of RNA Secondary Structures Including Pseudoknots
Shinnosuke Seki; Atsushi Kijima; Satoshi Kobayashi; Gen-ichi Sanpei
Oral presentation, English, Proc. of Genome Informatics 2004,
2004

Efficient Alignment Method for RNA Secondary Structures Including Pseudoknots
Shinnosuke Seki; Atsushi Kijima; Satoshi Kobayashi; Gen-ichi Sanpei
Oral presentation, English, IPSJ SIG Technical Report
2004

Algorithms for Evaluating Sequence Sets for DNA Computing
Satoshi Kobayashi
Oral presentation, English, IPSJ SIG Technical Report
2004

バルジ・内部ループを形成しない DNA 配列セットの設計
奥田 耕平; 小林 聡
Oral presentation, Japanese, 情報処理学会 数理モデル化と問題解決 研究報告
2002

Learning Locally Testable Languages and Its Application to Protein Identification
Satoshi Kobayashi; Yasuo Uemura
Invited oral presentation, English, Workshop on Language Modeling of Biological Data, Invited, Pensylvania Univ., International conference
Feb. 2001

Modeling RNA Secondary Structures using Tree Grammars and Its Application to RNA Secondary Structure Prediction
Yasuo Uemura; Satoshi Kobayashi
Invited oral presentation, English, Workshop on Language Modeling of Biological Data, Pensylvania Univ., International conference
Feb. 2001

Modeling RNA Secondary Structures using Tree Grammars and Its Application to RNA Secondary Structure Prediction
Yasuo Uemura; Satoshi Kobayashi
Invited oral presentation, English, Workshop on Language Modeling of Biological Data, Workshop on Language Modeling of Biological Data, at Pensylvania Univ., Pensylvania Univ., International conference
Feb. 2001

DNA コンピューティング --- その概観と理論的研究
小林聡
Invited oral presentation, Japanese, 第45回システム制御情報学会研究講演会講演論文集，チュートリアル講演
2001

確率計算システムとしての分子反応系について
小林 聡
Oral presentation, Japanese, 「新しい計算パラダイムシンポジウム2000」論文集，数理モデル化と問題解決研究会，情報処理学会
2000

制御付き離散事象システムの学習について
石田 信行; 小林 聡
Oral presentation, Japanese, 人工知能学会基礎論研究会
Sep. 1999

DNA分子を用いたホーン節の計算について (A Note on Horn Clause Computation with DNA Molecules)
小林 聡
Oral presentation, Japanese, 人工知能学会基礎論研究会
Mar. 1999

応用アルゴリズム論
Oct. 2025 - Mar. 2026

国際科目（アルゴリズム）
Oct. 2025 - Mar. 2026

コンピュータサイエンス実験第二
Oct. 2025 - Mar. 2026

情報・ネットワーク工学専攻基礎
Apr. 2025 - Sep. 2025

アルゴリズム論第二
Apr. 2025 - Sep. 2025

コンピュータサイエンス実験第二
Oct. 2024 - Mar. 2025

国際科目・アルゴリズム
Oct. 2024 - Mar. 2025

応用アルゴリズム論
Oct. 2024 - Mar. 2025

三大学連携学部・英語科目・アルゴリズム
Apr. 2024 - Sep. 2024

アルゴリズム論第二
Apr. 2024 - Sep. 2024

情報・ネットワーク工学専攻基礎
Apr. 2024 - Sep. 2024

コンピュータサイエンス実験第二
Oct. 2023 - Mar. 2024

応用アルゴリズム論
Oct. 2023 - Mar. 2024

Computer Algorithms
Oct. 2023 - Mar. 2024

アルゴリズム論第二
Apr. 2023 - Sep. 2023

情報・ネットワーク工学専攻基礎
Apr. 2023 - Sep. 2023
The University of Electro-Communications

Computer Algorithms
Oct. 2022 - Mar. 2023
The University of Electro-Communications

Advanced Communication Engineering and Informatics IV
電気通信大学

Advanced Communication Engineering and Informatics IV
The University of Electro-Communications

Advanced Communication Engineering and Informatics IV
The University of Electro-Communications

人工知能学会

情報処理学会

Construction of Theory and Design Principle of Molecular Computing Systems Realizing Functional Multiplicity by Control Signal Sequences
Satoshi Kobayashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (B), Principal investigator, 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., 19H04204
01 Apr. 2019 - 31 Mar. 2022

Support and publicity of molecular robotics
Hagiya Masami; MURATA Satoshi; SAITO Hirohide; KOBAYASHI Satoshi; FUJIMOTO Kenzo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Tokyo, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), 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)., 24104001
28 Jun. 2012 - 31 Mar. 2017

新学術領域「分子ロボティクス」 「知能分子ロボット実現に向けた化学反応回路の設計と構築」（計画研究）
小林 聡
Principal investigator
28 Jun. 2012 - 31 Mar. 2017

Development of molecular robotics based on DNA nanoengineering
MURATA Satoshi; KUZUYA Akinori; TAKINOUE Masahiro; SEKIYAMA Kosuke; NOMURA Shin-ichiro; FUJIMOTO Kenzo; TAKEUCHI Shyoji; KOBAYASHI Satoshi; KAWAMATA Ibuki; MORITA Masamune; HAMADA Shogo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Tohoku University, Grant-in-Aid for Scientific Research (S), 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., 22220001
01 Apr. 2010 - 31 Mar. 2015

分子ロボティクスのための反応系解析アルゴリズムの理論
2010 - 2012

DNA分子複合体を形成するためのハイブリッド型高速配列設計システムの開発
2005 - 2007

効率的な組合せ最適化アルゴリズムの開発と応用
2004 - 2006

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

Studies on Efficient Learning Algorithms from Examples
TOMITA Etsuji; WAKATSUKI Mitsuo; NISHINO Tetsuro; KOBAYASHI Satoshi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 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., 13680435
2001 - 2003

分子コンピュータのための確率的計算理論
2001 - 2003

演繹を基本演算とする超並列分子計算モデルに関する研究
1999 - 2000

DNA配列の相補性を利用した並列計算の理論
1997 - 1998

文法学習アルゴリズムに基づく蛋白質高次構造予測システムの開発
横森 貴; 小林 聡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 重点領域研究, DNA、RNA、あるいは蛋白質の高次構造の予測を行なうために最も重要なのは、それらの高次構造を表現するためのモデルを提案することである。我々は既に、形式言語理論の枠組を援用した、核酸配列の構造、あるいは蛋白質の構造を表現するための形式的なモデルを提案してきた。特に、RNAの二次構造をモデル化するための文法として、木文法TAG^2_を提案した。この木文法は、RNAの二次構造の中でも特に、その遺伝子の制御等への関わりが指摘され重要視されているシュードノット構造を含むような複雑な二次構造も柔軟に表現できることが検証されている。 この文法TAG^2_の学習アルゴリズムを開発する上でまず重要な問題となるのは、その構文解析アルゴリズムの計算量であった。すなわち、従来の木文法の構文解析アルゴリズムでは、時間計算量がO^(n^6)のものが知られているが、実際に実装して二次構造予測や同定に使用してみたところ、非常に遅く、長さ50程度の文字列の認識に対して、1時間以上かかってしまい、効率の良い実際的な学習アルゴリズムの開発は困難に思われた。 そこで、我々は、TAG^2_がRNA二次構造の表現という目的に特化されている点に注目して、より高速な構文解析アルゴリズムの開発を目指した。その結果、O^(n^4)のアルゴリズムを開発し、長さ50程度の配列に対しては、100倍以上の高速化が達成されることを実験的に検証した。またさらに、この開発されたアルゴリズムを用いて、シュードノット構造を含むことが知られているようなRNA配列の二次構造予測を行ったところ、非常に良い精度で、生物学的に知られている構造に合致することが実験的に確認された。 現在は、上記研究と並行して行っていた、近似学習理論の新しい枠組に関する研究成果を土台にして、TAG^2_の学習アルゴリズム・システムの開発・実装を進めている。, 07249201
1995 - 1995

文法の近似学習理論と遺伝子構造解析への応用
1995 - 1995

文法学習理論に基づく蛋白質の高次構造予測システムの開発
1994 - 1994

PC member of International Conference on DNA Computers and Molecular Programming
Peer review, Apr. 2023 - Sep. 2023