SATOSHI KOBAYASHI
| Department of Computer and Network Engineering | Professor |
| Cluster I (Informatics and Computer Engineering) | Professor |
Researcher Information
Research Keyword
Field Of Study
Educational Background
Research Activity Information
Award
- Sep. 2022
情報処理学会, コンピュータサイエンス（CS）領域功績賞は，情報処理学会のCS領域の研究会分野において，優秀な研究・技術開発，人材育成，および研究会・研究会運営に貢献したなど，顕著な功績のあったものに贈呈されます．例年，とても著名な研究者が受賞していることが目立ちます．小林の，DNAコンピューティング分野への顕著な研究業績および、数理モデル化と問題解決研究会の運営における顕著な貢献に対して，本賞が授与されました．（受賞の連絡をいただいたのは１１月になります）
コンピュータサイエンス領域功績賞
Japan society - Jul. 2015
1999 年の Top cited article として以下の論文が選出されました。 Yasuo Uemura, Aki Hasegawa, Satoshi Kobayashi, Takashi Yokomori, Tree Adjoining Grammars for RNA Structure Prediction, Theoretical Computer Science, Vol.210, pp.277-303, 1999.
""40th Anniversary of Theoretical Computer Science □ Top Cited Articles: 1975-2014""
Official journal - 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
Paper
- Improvement of the Size of Control Alphabet for Controlled Generation of Unary Strings of Specified Length
Daihei Ise; Satoshi Kobayashi
Last, to appear in Proc. of 17th Latin American Theoretical Informatics Symposium, 2026, Peer-reviwed
International conference proceedings, English - A Necessary and Sufficient Condition for Controlled Generation of Right Linear Grammars with Unknown Behaviors
Daihei Ise; Satoshi Kobayashi
Corresponding, IEICE Transactions on Information and Systems, E108.D, 6, 540-548, 2025, Peer-reviwed
Scientific journal, English - 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 )n2), 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
MISC
- 分子コンピュータ設計のための計算モデル
小林 聡
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 - 分子コンピュータ --- その理論と実験
小林 聡; 榊原 康文; 陶山 明; 横森 貴
サイエンス社, 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
Books and other publications
- 自然計算へのいざない
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
Lectures, oral presentations, etc.
- 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
Courses
- 応用アルゴリズム論
Oct. 2025 - Present - 国際科目（アルゴリズム）
Oct. 2025 - Present - コンピュータサイエンス実験第二
Oct. 2025 - Present - 情報・ネットワーク工学専攻基礎
Apr. 2025 - Present - アルゴリズム論第二
Apr. 2025 - Present - 三大学連携学部・英語科目・アルゴリズム
Apr. 2024 - Present - コンピュータサイエンス実験第二
Oct. 2024 - Mar. 2025 - 国際科目・アルゴリズム
Oct. 2024 - Mar. 2025 - 応用アルゴリズム論
Oct. 2024 - Mar. 2025 - アルゴリズム論第二
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
Research Themes
- 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
Apr. 2019 - 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
Jun. 2012 - Mar. 2017 - 新学術領域「分子ロボティクス」 「知能分子ロボット実現に向けた化学反応回路の設計と構築」（計画研究）
小林 聡
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Principal investigator, In this research project, we presented a design methodology of chemical reaction circuits using DNA for molecular robots with intelligence, and chemically implemented a prototype of a molecular robot in collaboration with other teams in "Molecular Robotics" project. Main results include: the development of high speed computing devices equipped with light responsive artificial nucleotides, implementation of an example of chemical reaction circuit which can adopt effectively to changes of environment, and the development of a high performance 1000-fold amplifier which resolved concentration gap problem between devices in molecular robots, and greatly contributed to the implementation of a prototype of molecular robot. We also developed a design theory of "reactive" chemical reaction circuits and theory of distributed computing, both of which are adequate for molecular robots., 24104003
Jun. 2012 - 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
Apr. 2010 - Mar. 2015 - 分子ロボティクスのための反応系解析アルゴリズムの理論
KOBAYASHI Satoshi; YAMASHITA Masafumi; MURATA Satoshi; SUZUKI Yasuhiro; KOMIYA Ken; KUZUYA Akinori; TAKINOUE Masahiro
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 established a theory of efficiently computing an equilibrium of a complex chemical reaction system, where molecules interact in various ways to produce a large set of assemblies. In this theory, we used hypergraph theory and optimization theory in a unified manner, and succeeded in the recuction of the number of variables which are needed for the computation of chemical equilibrium. The theory was applied to the computation of equilibrium of intearacting nucleic ascid strands. It was also extendedly applied to the approximate and efficient simulation of kinetic folding of an RNA molecule., 22500010
2010 - 2012 - DNA分子複合体を形成するためのハイブリッド型高速配列設計システムの開発
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), DNA Computing is a new computing paradigm in which we construct intended nano-scale structures using Watson-Crick complementarity and compute something. In this research project, we devised efficient analysis algorithms for designing sequences to be assembled into an intended nano-scale structure and developed a system for designing DNA sequences. Research results are three-fold. The first result is the development of the algorithm for evaluating a set of sequences under a simple model where we do not consider concentration of sequences in a test tube. For the case that the sequence set is finite, we devised an efficient algorithm of O(n^<5>) time, where n is the number of states in the automaton defining the given finite set of sequences. The second result is the proposal of a theory of algorithms for evaluating a sequence set under a more precise model where we consider concentration of sequences. The problem of interest can be rephrased in terms of physics as a problem of computing equilibrium states of reaction systems. Since we should deal with a reaction system where the number of its resultant complexes is exponential with respect to the size of input sequences, the equilibria analysis of such reaction systems is computationally intractable. In this research project, we proposed a novel theory for computing equilibria which overcomes the combinatorial explosion problem. In this theory, we fuse graph theory and optimization theory in order to overcome the combinatorial explosion of resultant complexes. Finally, we developed a hybrid-system for designing a set of sequences, where we use a popular sequence design method, called template method, developed by the author, and the first evaluation algorithm proposed in this research project. With this system, we can efficiently design a set of sequences satisfying various design constraints compared to previous systems., 17500192
2005 - 2007 - 効率的な組合せ最適化アルゴリズムの開発と応用
TOMITA Etsuji; TAKAHASHI Haruhisa; NISHINO Tetsuro; KOBAYASHI Satoshi; HOTTA Kazuhiro; WAKATSUKI Mitsuo
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), (1)We are mainly concerned with the maximum clique problem that is very important and is one of the most typical NP hard combinatorial problems. We employed a branch-and-bound algorithm for the problem and established an efficient ordering of vertices to search them. In addition, we developed a new approximate coloring algorithm to give an upper bound of the size of a maximum clique in question in order to bound the search. By combining these techniques, we developed very efficient algorithms for finding a maximum clique. The superiority of our algorithms over the other algorithms were confirmed by extensive computational experiments on random graphs and DIMACS benchmark graphs. (2)We developed an algorithm for generating all the maximal cliques in a graph and proved that it is theoretically optimum and runs very fast in practice. A more efficient algorithm that generates only large maximal cliques was also developed, that is important for practical uses. In addition, efficient algorithms that generate maximal bipartite graphs in a bipartite graph was developed. (3)These algorithms were successfully applied for practical problems in bioinformatics such as a protein side-chain packing problem and a protein threading problem. (4)We obtained new results of algorithmic learning of simple languages via queries, learning of Boolean functions from noisy samples, learning of a certain kind of counter language from positive data, and gave a unified approach for identification in the limit from positive data., 16300001
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 - 分子コンピュータのための確率的計算理論
小林 聡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 萌芽研究, 分子計算は本来確率的であり,分子反応を利用した計算も必然的に確率的にならざるを得ない.本研究では,分子反応のシミュレーションに用いられる技法に着目して,確率的計算理論の足がかりを得ることを目指してきた.DNA分子やRNA分子を利用した分子計算では,入念に設計したDNAやRNA配列を様々に組み合わせて,目的の構造分子を形成することを基本にしている.その際,目的の構造分子の存在確率が最も高くなることが望まれる.ここで,熱力学的には,自由エネルギー値の低い構造分子ほど存在確率が高くなる.そこで,本年度は,配列を様々に組み合わせでできる一本鎖構造分子の集合の中で,熱力学的自由エネルギーが最小になる構造分子を計算する効率的なアルゴリズムを開発した.このアルゴリズムは,配列を正則に組み合わせてできる(一般に無限集合でもよい)配列集合の中から,最小の自由エネルギーの構造をとり得る配列とその二次構造をO(n^8)の計算時間で求める.ここで,nは配列の組み合わせ方を指定する正則言語を表すオートマトンの状態数である.この成果は,Anne Condon(British Columbia大学)らによって未解決とされていた問題を解決したものである.この成果は,配列の設計問題における評価アルゴリズムとして具体的に応用することができる.また,さらに本年度は,準最適な構造も含めて存在確率を分析する計算理論を構築するための計算モデルとして,どのようなものが適切であるかの考察を進めた.そして,セルオートマトンを一般化したグラフ構造を持つセルオートマトンを考案し,構造分子の存在確率を計算するためのモデルとして利用できる可能性があるとの感触を得た.具体的な計算アルゴリズムの開発には至っていないが,そのための足がかりを得ることができた., 13878054
2001 - 2003 - 演繹を基本演算とする超並列分子計算モデルに関する研究
小林 聡
日本学術振興会, 科学研究費助成事業, 奨励研究(A), 本年度は以下の成果が得られた. 1.論理プログラムから実験プロトコルに変換する際に,変数コピーの操作を除去する技術が応用上かなり有効であることをつきとめた.通常論理プログラムを記述する際は,部分的に解の制約を規定しながら記述するために新たな述語を使用することが多いが,これは,実験プロトコルのステップ数を増大させることが非常に多い.この除去方法は,論理プログラムにおける最適化技術の展開操作に類似している. 2.同時に,上記の技術の有効性の数学的に厳密な証明を打ち立てようと試みたところ,多くの困難な問題が持ち上がって来た.当初は,離散化したモデルに確率を導入する予定だったが,かなり抽象化されてしまうために実験結果から遊離してしまう可能性が出て来た.そこで,より現実的なモデルとしてどのようなモデルが適切かを熟考し,化学反応速度論やGillespieらが提案している化学反応の確率的モデルにまで立ち返るべきであるとの判断を得るに至った. 3.上記の考察に基づき,化学反応速度論に基づいてDNA計算で用いられる反応系の性質を計算機科学的視点から分析した.そして,ライゲーション反応に限った場合に,指定時間の指定分子種の濃度をオイラー法により多項式時間で推定できることを示した.これは,ライゲーション反応に限れば,指定ステップ後の目標分子種の濃度は入力分子の濃度や速度パラメータの多項式関数で近似できることを意味している. このように,最適化技術を確立するための足掛かりを得た.しかし,実際に最適化機能付きコンパイラシステムを構築し完成させるまでには至らなかった.しかしながら,購入した計算機やプリンタはコンパイラの作成のための予備実験や成果3のシミュレーションアルゴリズムの実装などに多いに役立った., 11780238
1999 - 2000 - DNA配列の相補性を利用した並列計算の理論
小林 聡
日本学術振興会, 科学研究費助成事業, 萌芽的研究, 本年度は、平成9年度に提案した命題計算をDNA分子を用いて実現する並列計算機構と基礎実験に関する結果をふまえた上で、変数を含むホーン節計算をDNA計算機の基礎計算モデルとして用いることを提案し、実際にDNA分子を用いて各項が変数か定数のみからなるようなホーン節(以下単純ホーン節と呼ぶ)の演鐸計算を実現する実験手法を提案した。本手法では、単純ホーン節における各原子式は、各述語の何番目の引数に相当するかを表現する番地とその引数の内容を区別してDNA分子に符号化される。既に真であると証明された事実(基礎原子式)をホーン節の条件部に従ってライゲーションにより連接した後、変数の等価性をチェックした上で、ホーン節の結論部に相当する新しい基礎原子式を生成する。その際、等価性のチェックと変数の内容の条件部から結論部へのコピーの操作を行うために、一分子内反応(鞭打ちPCR)を利用することが鍵となる。本研究では、理論的結果として、単純ホーン節に制限しても、すべてのNPに属する決定問題が提案した手法により効率良く並列計算できることも示した。今後は、本研究を更に進展させ、ホーン節から実際の実験操作手続きに変換するコンパイラの作成とその際の最適化技術に関する研究を進めいくことを考えている。, 09878059
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 - 文法の近似学習理論と遺伝子構造解析への応用
小林 聡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 我々は既に、形式言語理論の枠組を援用した、核酸配列の構造、あるいは蛋白質の構造を表現するための形式的なモデルを提案してきた。しかし、実際の応用においては、目標とする遺伝子文法が、種々の抽象化やノイズの影響のため、設定した仮説空間に含まれない場合が多い。従って、学習目標とする遺伝子文法が仮説空間に含まれない場合でも、その目標文法の近似文法を学習させる必要性が生じ、そのような近似学習を取り扱える基礎理論を構築することが第一に重要である。 従来の学習理論の枠組では、確率文法の近似的学習など、確率的要素を取り入れた枠組が主流であるが、本研究では、いっさい確率的な要素を組み入れない近似文法学習理論を提案した。特に、我々は、概念の近似理論として近年注目を集めている、ラフ集合理論を文法学習に組み入れ、目標概念を含む最小の仮説、または目標概念に含まれる最大の仮説を極限同定するための必要十分条件を示した。また興味深いことに、そのような近似学習の枠組においては、正データからの学習能力が完全データからの学習能力に等しくなることが示された。 一方、従来から提案してきたRNAの二次構造表現のモデルとしてのTAG^2_の構文解析アルゴリズムの効率化にも成功した。従来の木文法をRNA二次構造表現に目的を絞り込むことによって、O(n^6)からO(n^4)への効率化を達成した。そして、開発したアルゴリズムを実装し、長さ100程度のシュードノットを含むような二次構造の予測に対しても十分対応できることを実験的に検証した。高速な構文解析は効率の良い学習にとっても有効であると考えられ、今後は、RNA二次構造の同定・特徴抽出問題を、上記の近似学習理論のもとで定式化した上で、近似学習アルゴリズムを開発・実装して、構造予測システムを構築してく予定である。, 07780310
1995 - 1995 - 文法学習理論に基づく蛋白質の高次構造予測システムの開発
横森 貴; 小林 聡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 重点領域研究, DNA,RNA,あるいは蛋白質の高次構造を予測するために重要なことは,それらの高次構造を表現するための形式モデルを提案することである.そのために,平成6年度の研究では,まず言語理論の枠組を援用しある種の木文法(tree grammar)に着目した.この木文法は元来自然言語処理の目的で提案されたものであるが,DNA配列などもある目的を持って生成された記号列であるという観点からすると,これらの形式文法を道具立てとしてDNA配列の性質をとらえられる可能性がある.実際,我々の研究から,特にRNAの二次構造に焦点をしぼったとき,この木文法をある方法で修正したモデルがRNA二次構造の表現文法として最適であることが判った.我々はこの文法をタグ付き木文法(TAG^2_)と名付けたが,この文法によって非常に広範な種目に現れる既存のRNA二次構造が,無駄なくかつ無理書く表現できる.実際,生物データからの具体例を幾つか挙げると,HIV-2 gag-pol領域におけるRNA,グループIイントロンに見られるRNA,種々のtRNA,リボゾームRNAなどなどがある.現在,これらの研究知見をもとに,TAG^2_ による各種のRNA二次構造の同定(分類)システムを試作中であり,今後は,蛋白質の高次構造の予測問題などへの応用していく予定である.また,より進んだ研究として,DNA・RNA構造の予測問題をこの木文法に対する学習問題として定式化し,その数理的な解析,および学習アルゴリズムの開発を行なうことが考えられる. 次年度では,本年度における理論的な知見・成果を基に同定・予測システムをより洗練されたものに改良すると同時に,試作された高次構造予測プロトタイプシステムの実験・評価結果をフィードバックすることにより徐々に改良を行ない,より完成度の高いシステムの構築を目指す.役割分担としては,本年度と同様,横森(研究代表者)が主に本研究の理論面の改良を担当し,小林(研究分担者)が高次構造予測システムの改良を担当する., 06249202
1994 - 1994
