Updated on 2024/04/23

写真a

 
YOKOMORI, Takashi
 
Affiliation
Faculty of Education and Integrated Arts and Sciences
Job title
Professor Emeritus
Degree
Doctor of Science, ( University of Tokyo )

Research Experience

  •  
     
     

    For the details, visit the URL (http://www.f.waseda.jp/yokomori/).

  •  
     
     

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

Education Background

  • 1974.04
    -
    1979.03

    University of Tokyo   Graduate School, Division of Science   fundamental science  

  • 1970.04
    -
    1974.03

    University of Tokyo   Faculty of Science   Department of Mathematics  

Committee Memberships

  • 2019.03
    -
    Now

    Journal of Membrane Computing  Advisory Board member

  • 2018.08
    -
    Now

    Springer:  Advisory Board of the Springer Natural Computing Book Series

  • 2003.09
    -
    Now

    Theoretical Computer Science (Elsevier)  Editor

  • 2011.09
    -
    2024.03

    Development in Language Theory (International Conference Series)  Steering Committee Member

  • 2015.01
    -
    2015.12

    Applied Soft Computing (Elsevier)  Editor

  • 1999.09
    -
    2010.03

    Fundamenta Informaticae (IOS Press)  Editor

  • 2000.09
    -
    2003.12

    Grammars  Editor

  • 1999.06
    -
    2001.05

    Information Processing Socity of Japan  Editor-in-Chief, Fundamental Area

  • 1999.06
    -
    2001.05

    情報処理学会  論文誌編集委員会 基礎理論領域主査

  • 1995.05
    -
    1996.10

    Information Processing Society of Japan  Editor

  • 1995.05
    -
    1996.10

    情報処理学会  論文誌編集委員

  • 1994.05
    -
    1996.10

    The Institute of Electronics, Information and Communication Engineers  Editor for Area D

  • 1994.05
    -
    1996.10

    電子情報通信学会  英文誌D編集委員

  • 1986.05
    -
    1994.04

    The Institute of Electronics, Information and Communication Engineers  Reviewer

  • 1986.05
    -
    1994.04

    電子情報通信学会  論文査読委員

▼display all

Professional Memberships

  • 1980
    -
    Now

    Information Processing Society of Japan

  • 2000
    -
    2021

    Japanese Society for Bioinformatics

  • 1997
    -
    2021

    Association for Computing Machinery

  • 1987
    -
    2021

    The Japanese Society for Artificial Intelligence

  • 1985
    -
    2018

    European Association for Theoretical Computer Science

Research Areas

  • Theory of informatics   Computer Science, Theory of Computing, Natura Computing

Research Interests

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

Awards

  • Fellow

    2018.06   Information Processing Society of Japan  

 

Papers

  • Corrigendum: “On the computing powers of L-reductions of insertion languages” (Theoretical Computer Science (2021) 862 (224–235), (S030439752030668X), (10.1016/j.tcs.2020.11.029))

    Fumiya Okubo, Takashi Yokomori

    Theoretical Computer Science   920   113  2022.06

     View Summary

    The authors regret that the proof for Theorem 4 in the article “On the computing powers of [Formula presented]-reductions of insertion languages” was incomplete, which was pointed out by Kaoru Fujioka, Fukuoka Women's University, Japan. The proof needs some supplementary corrections for constructing the insertion system γ and [Formula presented]. Specifically, in the proof (on page 231), 1. line 4: Correct as [Formula presented], we construct the following rules: [Formula presented] 3. after line 11: Insert the following: • If there exists a rule

    DOI

    Scopus

  • Theory of reaction automata: a survey

    Takashi Yokomori, Fumiya Okubo

    Journal of Membrane Computing   3   63 - 85  2021.03  [Refereed]

    Authorship:Corresponding author

    DOI

    Scopus

    2
    Citation
    (Scopus)
  • On the computing powers of L-reduction of insertion languages

    F.Okubo, T.Yokomori

    Theoretical Computer Science   862   224 - 235  2020.11  [Refereed]

     View Summary

    © 2020 We investigate the computing power of the following language operation %: Given two languages L1 over Σ and L2 over Γ with Γ⊂Σ, we consider the language operation L1%L2={u0u1⋯un|∃u=u0v1u1⋯vnun∈L1 and ∃vi∈L2(1≤∀i≤n)}. In this case we say that L(=L1%L2) is the L2-reduction of L1. This is extended to the language families as follows: L1%L2={L1%L2|L1∈L1,L2∈L2}. Among many works concerning Dyck-reductions, for the family of recursively enumerable languages RE, it was shown that LIN%{EQ}=RE (Jantzen & Petersen, 1994) with EQ={xnx‾n|n∈N} and that min-LIN%{D2}=RE (Hirose & Okawa, 1996, and Latteux & Turakainen, 1990), where LIN and min-LIN are the families of linear and minimal linear context-free languages, respectively. In this paper, we show that each recursively enumerable language L can be represented in the form L=K%D, for some K∈INS30 and a Dyck language D, where INS⁎0 (INS30) denotes the family of insertion languages (insertion languages where the maximum length of the string to be inserted is 3). We can refine it as INS⁎0%{D2}=RE, where D2 denotes the Dyck language over binary alphabet. For context-free languages, we show that INS30%F=CF, where F is the family of finite sets. This also derives that INS⁎0%{MIR}=CF with MIR={xx‾R|x∈{0,1}⁎}. Further, for regular languages, it is shown that each regular language R can be represented in the form R=K%F, for some K∈INS20 and a finite set F={abb‾a‾|a∈V}. We also present some results which characterize the computability and properties of L in the framework of L2-reduction of L1. It is intriguing to note that, from the DNA computing point of view, the notion of L-reduction is naturally motivated by a molecular biological functioning well-known as DNA(RNA) splicing occurring in most eukaryotic genes.

    DOI

    Scopus

    1
    Citation
    (Scopus)
  • Decomposition and factorization of chemical reaction transducers

    F.Okubo, T.Yokomori

    Theoretical Computer Science   777   431 - 442  2019.06  [Refereed]

  • Natural Computing Paradigm - A Concise Introduction

    Takashi Yokomori

    JOURNAL OF ROBOTICS NETWORKING AND ARTIFICIAL LIFE   5 ( 1 ) 6 - 9  2018.06  [Refereed]

     View Summary

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

  • The computing power of determinism and reversibility in chemical reaction automata

    F.Okubo, T.Yokomori

    in "Reversibility and Universality"   (edited by A.Adamatzky), Springer   279 - 298  2018  [Refereed]

    Authorship:Corresponding author

  • Computing with Multisets: A Survey on Reaction Automata Theory

    Takashi Yokomori, Fumiya Okubo

    SAILING ROUTES IN THE WORLD OF COMPUTATION   10936   421 - 431  2018  [Refereed]

    Authorship:Lead author

    DOI

    Scopus

    1
    Citation
    (Scopus)
  • Morphic Characterizations of Language Families Based on Local and Star Languages

    Fumiya Okubo, Takashi Yokomori

    FUNDAMENTA INFORMATICAE   154 ( 1-4 ) 323 - 341  2017  [Refereed]

     View Summary

    New morphic characterizations in the form of a noted Chomsky-Schutzenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following:
    (i) Each lambda-free regular language R can be expressed as R = h(T-k boolean AND F-R) for some 2-star language F-R, an extended 2-star language T-k and a weak coding h.
    (ii) Each lambda-free context-free language L can be expressed as L = h (D-n boolean AND F-L) for some 2-local language F-L and a projection h.
    (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language F-L and a weak coding h such that L = h (B-n boolean AND F-L), where D-n and B-n are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively.
    These characterizations improve or shed new light on the previous results.

    DOI

    Scopus

    4
    Citation
    (Scopus)
  • The computational capability of chemical reaction automata

    Fumiya Okubo, Takashi Yokomori

    NATURAL COMPUTING   15 ( 2 ) 215 - 224  2016.06  [Refereed]

     View Summary

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

    DOI

    Scopus

    18
    Citation
    (Scopus)
  • Finite Automata with Multiset Memory: A New Characterization of Chomsky Hierarchy

    Fumiya Okubo, Takashi Yokomori

    FUNDAMENTA INFORMATICAE   138 ( 1-2 ) 31 - 44  2015  [Refereed]

     View Summary

    This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data.
    We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-boundedFAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy.

    DOI

    Scopus

    3
    Citation
    (Scopus)
  • Recent developments on reaction automata theory: A survey

    F.Okubo, T.Yokomori

    Series: Mathematics for Industry, vol.9 (Y.Suzuki and M.Hagiya, eds.), Springer   Vol.9   1 - 22  2014  [Refereed]

    Authorship:Corresponding author

  • The computational capability of chemical reaction automata

    F.Okubo, T.Yokomori

    Proc. of 20th International Conference on DNA Computing and Molecular Programming, Kyoto, Japan, Lecture Notes in Computer Science, Springer   8727   53 - 66  2014  [Refereed]

    Authorship:Corresponding author

     View Summary

    © Springer International Publishing Switzerland 2014. We propose a new computing model called chemical reaction automata (CRAs) as a simplified variant of reaction automata (RAs) studied in recent literature ([7–9]).We show that CRAs in maximally parallel manner are computationally equivalent to Turing machines, while the computational power of CRAs in sequential manner coincides with that of the class of Petri nets, which is in marked contrast to the result that RAs (in both maximally parallel and sequential manners) have the computing power of Turing universality ([7, 8]). Intuitively, CRAs are defined as RAs without inhibitor functioning in each reaction, providing an offline model of computing by chemical reaction networks (CRNs).Thus, the main results in this paper not only strengthen the previous result on Turing computability of RAs but also clarify the computing powers of inhibitors in RA computation.

    DOI

    Scopus

    3
    Citation
    (Scopus)
  • Automata inspired by biochemical reaction (New Trends in Algorithms and Theory of Computation)

    Okubo Fumiya, Kobayashi Satoshi, Yokomori Takashi

    RIMS Kokyuroku   1799   179 - 182  2012.06

    CiNii

  • Reaction Automata

    F.Okubo, S.Kobayashi, T.Yokomori

    Theoretical Computer Science   Vol.429   247 - 257  2012  [Refereed]

    Authorship:Corresponding author

     View Summary

    Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy. © 2012 Elsevier B.V. All rights reserved.

    DOI

    Scopus

    17
    Citation
    (Scopus)
  • On the Properties of Language Classes of Bounded Reaction Automata

    Fujiya Okubo, Takashi Yokomori

    Theoretical Computer Science   Vol.454   206 - 221  2012  [Refereed]

    Authorship:Corresponding author

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

    Fumiya Okubo, Takashi Yokomori

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   22 ( 1 ) 247 - 260  2011.01  [Refereed]

    Authorship:Corresponding author

     View Summary

    Insertion systems have a unique feature in that only string insertion are allowed, which is in marked contrast to a variety of the conventional computing devices based on string rewriting. This paper will mainly focus on those systems whose insertion operations are performed in a context-free fashion, called context-free insertion systems, and obtain several characterizations of language families with the help of other primitive languages (like star languages) as well as simple operations (like projections, weak-codings). For each k >= 1, a language L is a k-star language if L = F(+) for some finite set F with the length of each string in F is no more than k. The results of this kind have already been presented in [10] by Paun et al., while the purpose of this paper is to prove enhanced versions of them.
    Specifically, we show that each context-free language L can be represented in the form L = h(L(gamma)boolean AND F(+)), where gamma is an insertion system of weight (3, 0) (at most three symbols are inserted in a context-free manner), h is a projection, and F(+) is a 2-star language. A similar characterization can be obtained for recursively enumerable languages, where insertion systems of weight (3, 3) and 2-star languages are involved.

    DOI

    Scopus

    5
    Citation
    (Scopus)
  • Spiking Neural dP Systems

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

    FUNDAMENTA INFORMATICAE   111 ( 4 ) 423 - 436  2011  [Refereed]

     View Summary

    We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which "read" strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.

    DOI

    Scopus

    13
    Citation
    (Scopus)
  • On the hairpin incompletion

    Fumiya Okubo, Takashi Yokomori

    Fundamenta Informaticae   110 ( 1-4 ) 255 - 269  2011  [Refereed]

     View Summary

    Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.

    DOI

    Scopus

  • Spiking Neural dP Systems

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

    FUNDAMENTA INFORMATICAE   111 ( 4 ) 423 - 436  2011  [Refereed]

     View Summary

    We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which "read" strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.

    DOI

    Scopus

    13
    Citation
    (Scopus)
  • SOME REMARKS ON THE HAIRPIN COMPLETION

    Florin Manea, Victor Mitrana, Takashi Yokomori

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   21 ( 5 ) 859 - 872  2010.10  [Refereed]

    Authorship:Last author

     View Summary

    We consider several problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center disjoint k-locally testable languages in the strict sense. This result completes two results from [3] and [11]. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.

    DOI

    Scopus

    11
    Citation
    (Scopus)
  • On spiking neural P systems

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

    NATURAL COMPUTING   9 ( 2 ) 475 - 491  2010.06  [Refereed]

     View Summary

    This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants. A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems and the capability these models have to generate certain classes of languages. Further, by making a slight modification to the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.

    DOI

    Scopus

    8
    Citation
    (Scopus)
  • Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

    Florin Manea, Victor Mitrana, Takashi Yokomori

    THEORETICAL COMPUTER SCIENCE   410 ( 4-5 ) 417 - 425  2009.02  [Refereed]

     View Summary

    We consider two complementary operations: Hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: Hairpin completion, in: Proc. Transgressive Computing, 2006, pp. 216-228] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also Studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations. (C) 2008 Elsevier B.V. All rights reserved.

    DOI

    Scopus

    27
    Citation
    (Scopus)
  • Membrane Computing Schema: A New Approach to Computation Using String Insertions

    Mario J. Perez-Jimenez, Takashi Yokomori

    ALGORITHMIC BIOPROCESSES     293 - +  2009  [Refereed]

     View Summary

    In this paper, we introduce the notion of a membrane computing schema for string objects. We propose a computing schema for a membrane network (i.e., tissue-like membrane system) where each membrane performs unique type of operations at a time and sends the result to others connected through the channel. The distinguished features of the computing models obtained from the schema are:1. only context-free insertion operations are used for string generation,2. some membranes assume filtering functions for structured objects (molecules),3. generating model and accepting model are obtained in the same schema, and both are computationally universal,4. several known rewriting systems with universal computability can be reformulated by the membrane computing schema in a uniform manner.The first feature provides the model with a simple uniform Structure which facilitates it biological implementation of the model, while the second feature suggests further feasibility of the model in terms of DNA complementarity.Through the third and fourth features, one may have a unified view of a variety of existing rewriting systems with Turing computability in the framework of membrane computing paradigm.

    DOI

    Scopus

  • Representations and characterizations of languages in chomsky hierarchy by means of insertion-deletion systems

    Gheorghe Paun, Mario J. Perez-Jimenez, Takashi Yokomori

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE   19 ( 4 ) 859 - 871  2008.08  [Refereed]

    Authorship:Last author

     View Summary

    Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability and characterizations or representations of languages in Chomsky hierarchy were obtained in this framework.
    In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Schutzenberger representation of context-free languages, i.e., in the form L = h(L(gamma)boolean AND D), where 7 is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages - this time using insertion systems of weight (3, 0) and star languages.

  • Doubler and linearizer: An approach toward a unified theory for molecular computing based on DNA complementarity

    Kaoru Onodera, Takashi Yokomori

    Natural Computing   7 ( 1 ) 125 - 143  2008.03  [Refereed]

     View Summary

    Two specific mappings called doubler f d and linearizer f e are introduced to bridge between two kinds of languages. Specifically, f d maps string languages into (double-stranded) molecular languages, while f e performs the opposite mapping. Using these mappings, we obtain new characterizations for the families of sticker languages and of Watson-Crick languages, which lead to not only a unified view of the two families of languages but also provide a helpful view on the computational capability of DNA complementarity. Furthermore, we introduce a special type of a projection f pr which is composed of f d and a projection in the usual sense. We show that any recursively enumerable language L can be expressed as f pr(L m) for a minimal linear language L m. This result can be strengthened to L = f p(L s), for a specific form of minimal linear language L s, which provides a simple morphic characterization for the family of recursively enumerable languages. © Springer Science+Business Media B.V. 2007.

    DOI

    Scopus

    1
    Citation
    (Scopus)
  • Special Issue on Spiking Neural P systems

    M.Ionescu, G.Paun, T.Yokomori

    Natural Computing   7 ( 2 )  2008

  • Special Issue on DNA Computing

    C.Mao, T.Yokomori

    Natural Computing   7 ( 2 )  2008

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

    K.Onodera, T.Yokomori

    Natural Computing   7   124 - 143  2008  [Refereed]

    Authorship:Corresponding author

  • Erratum to "Polynomial-time identification of very simple grammars from positive data" [Theoret. Comput. Sci. 298 (2003) 179-206]

    YOKOMORI T.

    Theor. Comput. Sci.   377   282 - 283  2007

    DOI CiNii

    Scopus

    3
    Citation
    (Scopus)
  • Spiking neural P systems with an exhaustive use of rules

    Mihai Ionescu, Gheorghe Paun, Takashi Yokomori

    INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING   3 ( 2 ) 135 - 153  2007  [Refereed]

     View Summary

    We consider spiking neural P systems with a new type of rule application: whenever a rule is enabled in a neuron, it is used in an exhaustive manner, i.e., as many times as possible for the number of spikes from that neuron. Thus, also the number of spikes produced at a time in that neuron can be arbitrarily large; all produced spikes are transmitted to neighboring neurons through synapses. A result is associated with a computation as usual, in the form of the number of time units elapsed between the first two steps when the Output neuron spikes. In this framework, we prove the computational completeness of Our systems, both as number generating devices and as number accepting devices. Several research topics are also pointed out.

  • DNA Computing

    C.Mao, T.Yokomori

    Proc. of 12th International Meeting on DNA Computing, DNA12, Seoul, Korea, June 5-9, 2006; Lecture Notes in Computer Science   4287  2006.11  [Invited]

  • Spiking neural P systems

    Mihai Ionescu, Gheorghe Paun, Takashi Yokomori

    FUNDAMENTA INFORMATICAE   71 ( 2-3 ) 279 - 308  2006.06  [Refereed]

     View Summary

    This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated.

  • Probabilistic inference in test tube and its application to the Gene expression profiles, in “Formal models, Languages and Applications

    Y.Sakakibara, S.Kobayashi, A.Suyama, T.Yokomori

    Formal models, Languages and Applications”(eds. M. Mukund, K. G. Subramanian, K. Rangarajan), series in Machine Perception and Artificial Intelligence   66   304 - 319  2006  [Refereed]

    Authorship:Last author

  • A simple classification of the volvocine algae by formal languages

    H Yoshida, T Yokomori, A Suyama

    BULLETIN OF MATHEMATICAL BIOLOGY   67 ( 6 ) 1339 - 1354  2005.11  [Refereed]

     View Summary

    There are several explanations of why certain primitive multicellular organisms aggregate in particular forms and why their constituent cells cooperate with one another to a particular degree. Utilizing the framework of formal language theory, we have derived one possible simple classification of the volvocine algae-one of the primitive multicells-for some forms of aggregation and some degrees of cooperation among cells. The volvocine algae range from the unicellular Chlamydonionas to the multicellular Volvox globator, which has thousands of cells. The classification we use in this paper is based on the complexity of Parikh sets of families on Chomsky hierarchy in formal language theory. We show that an alga with almost no space closed to the environment, e.g., Gonium pectorale, can be characterized by PsFIN, one with a closed space and no cooperation, e.g., Eudorina elegans, by PsCF, and one with a closed space and cooperation, e.g., Volvox globator, by Ps lambda SC. This classification should provide new insights into the necessity for specific forms and degrees of cooperation in the volvocine algae. (c) 2005 Society for Mathematical Biology. Published by Elsevier Ltd. All rights reserved.

    DOI

    Scopus

    4
    Citation
    (Scopus)
  • On the power of membrane division in P systems

    G Paun, Y Suzuki, H Tanaka, T Yokomori

    THEORETICAL COMPUTER SCIENCE   324 ( 1 ) 61 - 85  2004.09  [Refereed]

     View Summary

    First, we consider P systems with active membranes, hence with the possibility that the membranes can be divided, with non-cooperating evolution rules (the objects always evolve separately). These systems are known to be able to solve NP-complete problems in linear time. Here we give a normal form theorem for such systems: their computational universality is preserved even if only the elementary membranes are divided. The possibility of solving SAT in linear time is preserved only when non-elementary membranes may also be divided under the influence of objects in their region.
    Second, we consider a slight generalization, namely, we allow that a membrane can produce by division both a copy of itself and a copy of a membrane with a different label; again, only elementary membranes may be divided. In this case, we prove that the hierarchy on the maximal number of membranes present in the system collapses: three membranes at a time are sufficient in order to characterize the recursively enumerable sets of vectors of natural numbers. This result is optimal, two membranes are shown not to be sufficient.
    Third, we consider P systems with cooperating rules (several objects may evolve together). Making use of this powerful feature, we show that many NP-complete problems can be solved in linear time in a quite uniform way (by systems which are very similar to each other), using only elementary membranes division (and not further ingredients, such as electrical charges). The degree of cooperation is minimal: two objects at a time. (C) 2004 Elsevier B.V. All rights reserved.

    DOI

    Scopus

    41
    Citation
    (Scopus)
  • Learning mild context-sensitiveness: Toward understanding children's language learning

    L Becerra-Bonache, T Yokomori

    GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS   3264   53 - 64  2004  [Refereed]

    Authorship:Last author

     View Summary

    The aim of this paper is to try to understand the process of children's language acquisition by using the theory of inference of formal grammars. Toward this goal, we introduce an extension of Marcus External Contextual grammars which constitutes a Mildly Context-Sensitive language family, and study their learnability in the limit from positive data. Finally, we briefly indicate our future research direction.

  • An algorithm for testing structure freeness of biomolecular sequences

    S Kobayashi, T Yokomori, Y Sakakibara

    ASPECTS OF MOLECULAR COMPUTING   2950   266 - 277  2004  [Refereed]

     View Summary

    We are concerned with a problem of checking the structure freeness of S+ for a given set S of DNA sequences. It is still open whether or not there exists an efficient algorithm for this problem. In this paper, we will give an efficient algorithm to check the structure freeness of S+ under the constraint that every sequence may form only linear secondary structures, which partially solves the open problem.

  • Polynomial-time identification of very simple grammars from positive data

    T Yokomori

    THEORETICAL COMPUTER SCIENCE   298 ( 1 ) 179 - 206  2003.04  [Refereed]

    Authorship:Lead author

     View Summary

    This paper concerns a subclass of simple deterministic grammars, called very simple grammars, and studies the problem of identifying the subclass in the limit from positive data. The class of very simple languages forms a proper subclass of simple deterministic languages and is incomparable to the class of regular languages. This class of languages is also known as the class of left Szilard languages of context-free grammars.
    After providing some properties of very simple languages, we show that the class of very simple grammars is polynomial-time identifiable in the limit from positive data in the following sense. That is, we show that there effectively exists an algorithm that, given a target very simple grammar G(*) over alphabet Sigma, identifies a very simple grammar G equivalent to G(*) in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(m), and the total number of prediction errors made by the algorithm is bounded by O(n), where n is the size of G(*), m = Max{N\Sigma\+1, \Sigma\(3)} and N is the total length of all positive data provided. (C) 2002 Elsevier Science B.V. All rights reserved.

  • On the computational power of insert ion-deletion systems

    A Takahara, T Yokomori

    DNA COMPUTING   2568   269 - 280  2003  [Refereed]

     View Summary

    Gene insertion and deletion are basic phenomena found in DNA processing or RNA editing in molecular biology. The genetic mechanism and development based on these evolutionary transformations have been formulated as a formal system with two operations of insertion and deletion, called insertion-deletion systems ([1], [2]).
    We investigate the generative power of insertion-deletion systems (InsDel systems), and show that the family (INS1DEL11)-D-1 is equal to the family of recursively enumerable languages. This gives a positive answer to an open problem posed in [2] where it was conjectured to be negative.

  • On the computational power of insert ion-deletion systems

    A Takahara, T Yokomori

    DNA COMPUTING   2568   269 - 280  2003  [Refereed]

     View Summary

    Gene insertion and deletion are basic phenomena found in DNA processing or RNA editing in molecular biology. The genetic mechanism and development based on these evolutionary transformations have been formulated as a formal system with two operations of insertion and deletion, called insertion-deletion systems ([1], [2]).
    We investigate the generative power of insertion-deletion systems (InsDel systems), and show that the family (INS1DEL11)-D-1 is equal to the family of recursively enumerable languages. This gives a positive answer to an open problem posed in [2] where it was conjectured to be negative.

  • Molecular Computing Paradigm - Toward freedom from Turing's charm

    T.Yokomori

    Natural Computing   Vol.4, No.1   333 - 390  2002  [Invited]

    Authorship:Lead author

  • A Magic Pot : Self-assembly computation revisited

    T.Yokomori, Y.Sakakibara, S. Kobayashi

    Formal and Natural Computing, Lecture Notes in Computer Science   Vol.2300   418 - 429  2002  [Invited]

    Authorship:Lead author

  • Toward Soft Hardware

    G. Paun, T. Yokomori

    Soft Computing/Springer   5;2  2001.05

    Authorship:Last author

  • Special Issue on Molecular Computing (edited)

    G.Paun, T.Yokomori

    Soft Computing   5 ( 2 )  2001

    Authorship:Last author

  • Approximate Identification and Finite Elasticity

    S.Kobayashi, Y,Sakakibara, T.Yokomori

    ``Where Mathematics, Computer Science, Linguistics and Biology Meet'' (C.Martin-Vide and V.Mitrana, Eds.), Kluwer Academic Pub.     169 - 189  2001  [Refereed]

    Authorship:Last author

  • Hairpin languages

    Gheorghe Pǎun, Grzegorz Rozenberg, Takashi Yokomori

    International Journal of Foundations of Computer Science   12 ( 6 ) 837 - 847  2001  [Refereed]

     View Summary

    Molecules with hairpin structure(s) form a natural extension of linear non-branched molecules, and they have been already used in experimental work in DNA computing. In this paper we introduce and investigate classes of string languages (hence languages modeling the sets of linear DNA molecules), consisting of strings which can (fold on itself and) form hairpins. We classify the complexity of these classes using language-theoretic techniques. We also discuss a further use of hairpin molecules in DNA computing. © 2001 World Scientific Publishing Company.

    DOI

    Scopus

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

    情報処理/情報処理学会   41 ( 8 ) 925 - 931  2000.08  [Refereed]  [Invited]

    Authorship:Lead author

  • Molecular computation by DNA hairpin formation

    K Sakamoto, H Gouzu, K Komiya, D Kiga, S Yokoyama, T Yokomori, M Hagiya

    SCIENCE   288 ( 5469 ) 1223 - 1226  2000.05  [Refereed]

     View Summary

    Hairpin formation by single-stranded DNA molecules was exploited in a DNA-based computation in order to explore the feasibility of autonomous molecular computing. An instance of the satisfiability problem, a famous hard combinatorial problem, was solved by using molecular biology techniques. The satisfiability of a given Boolean formula was examined autonomously, on the basis of hairpin formation by the molecules that represent the formula. This computation algorithm can test several clauses in the given formula simultaneously, which could reduce the number of Laboratory steps required for computation.

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

    T.Yokomori

    Developments in Language Theory     32 - 43  2000  [Refereed]  [Invited]

    Authorship:Lead author

  • Simulating H systems by P systems

    G.Paun, T.Yokomori

    Journal of Universal Computer Science/Springer-Verlag   6   178 - 193  2000  [Refereed]

  • On the universality of Post and splicing systems

    C Ferretti, G Mauri, S Kobayashi, T Yokomori

    THEORETICAL COMPUTER SCIENCE   231 ( 2 ) 157 - 170  2000.01  [Refereed]

     View Summary

    In search for a universal splicing system, in this paper we present a Post system universal for the class of Post systems, and we discuss its translation into an extended splicing system with multiplicity. We also discuss the complexity of the resulting universal splicing system, comparing our result with recent known results about the translation of universal Turing machines into splicing systems. (C) 2000 Elsevier Science B.V. All rights reserved.

  • YAC: Yet Another Computation Model of Self-Assembly

    T.Yokomori

    Proc. of 5th DIMACS Workshop on DNA based Computers/AMS     153 - 167  1999.06  [Refereed]

    Authorship:Lead author

    CiNii

  • Membrane Computing Based on Splicing

    G.Paun, T.Yokomori

    Proc. of 5th DIMACS Workshop on DNA based Computers/AMS     213 - 227  1999.06  [Refereed]

    Authorship:Last author

    CiNii

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

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

    Authorship:Lead author

    CiNii

  • Algorithmic Learning Theory (edited)

    O.Watanabe, T.Yokomori

    Lecture Notes in Artificial Intelligence   1720  1999

    Authorship:Last author

  • Tree adjoining grammars for RNA structure prediction

    Y Uemura, A Hasegawa, S Kobayashi, T Yokomori

    THEORETICAL COMPUTER SCIENCE   210 ( 2 ) 277 - 303  1999.01  [Refereed]

     View Summary

    In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm. (C) 1999-Elsevier Science B.V. All rights reserved.

  • 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  1998.10  [Refereed]

     View Summary

    This paper concerns an efficient algorithm for learning in the limit a special type of regular languages called strictly locally testable languages from positive data, and its application to identifying the protein alpha-chain region in amino acid sequences. First, we present a linear time algorithm that, given a strictly locally testable language, learns (identifies) its deterministic finite state automaton in the limit from only positive data. This provides us with a practical and efficient method for learning a specific concept domain of sequence analysis. We then describe several experimental results using the learning algorithm developed above. Following a theoretical observation which strongly suggests that a certain type of amino acid sequences can be expressed by a locally testable language, we apply the learning algorithm to identifying the protein alpha-chain region in amino acid sequences for hemoglobin. Experimental scores show an overall success rate of 95 percent correct identification for positive data, and 96 percent for negative data.

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

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

  • Locality, reversibility, and beyond: Learning languages from positive data

    T Head, S Kobayashi, T Yokomori

    ALGORITHMIC LEARNING THEORY   1501   191 - 204  1998  [Refereed]

     View Summary

    In algorithmic learning theory fundamental roles:are played by the family of languages that are locally testable in the strict sense and by the family of reversible languages. These two families are shown to be the first two members of an infinite sequence of families of regular languages the members of which are learnable in the limit from positive data only. A uniform procedure is given for deciding, for each regular language R and each of our specified families, whether R belongs to the family.: The approximation of arbitrary regular languages by languages belonging to these families is discussed. Further, we will:give a uniform scheme for learning these families from positive data. Several research problems are also suggested.

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

    T.Yokomori, S.Kobayashi

    Proc. of 3rd DIMACS Workshop on DNA Based Computers     334 - 347  1997.06  [Refereed]

    Authorship:Lead author

    CiNii

  • Learning approximately regular languages with reversible languages

    S Kobayashi, T Yokomori

    THEORETICAL COMPUTER SCIENCE   174 ( 1-2 ) 251 - 257  1997.03  [Refereed]

     View Summary

    In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.

  • Identifiability of Subspaces and Homomorphic Images of Zero-Reversible Languages

    S.Kobayashi, T.Yokomori

    Lecture Notes in Artificial Intelligence   1316   48 - 61  1997  [Refereed]

    Authorship:Last author

  • 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  [Refereed]

     View Summary

    From a biological motivation of interactions between linear and circular DNA sequences, we propose a new type of splicing models called circular H systems and show that they have the same computational power as Turing machines. It is also shown that there effectively exists a universal circular H system which can stimulate any circular H system with the same terminal alphabet, which strongly suggests a feasible design for a DNA computer based on circular splicing.

  • 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  [Refereed]

     View Summary

    In this paper, we propose a method for biologically implementing simple Boolean formulae. This method enables us to compute logical consequences of a given set of simple Horn clauses in parallel and takes advantage of potentially huge number of molecular CPUs of DNA computers. Further, we show that the method is nicely applied to the parallel implementation of a grammatical recognition algorithm which is based on 'dynamic programming.'

  • The Forth International Workshop on Rough Sets and Machine Discovery (RSMD96), edited

    S.Tsumoto, S.Kobayashi, T.Yokomori, H.Tanaka, A.Nakamura

       1996.11

  • 計算論的言語理論とDNA計算

    横森貴, 小林聡

    情報処理   37 ( 10 ) 929 - 934  1996.10  [Refereed]  [Invited]

    Authorship:Lead author

  • Learning two-tape automata from queries and counterexamples

    T Yokomori

    MATHEMATICAL SYSTEMS THEORY   29 ( 3 ) 259 - 270  1996.05  [Refereed]

     View Summary

    We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of Sigma*, a 2-tape DFA over an alphabet Sigma accepts a subset of Sigma* x Sigma*, and therefore, it can specify a binary relation on Sigma*. In [3] Angluin showed that the class of deterministic finite automata (DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from a minimally adequate teacher (MAT).
    In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any language L accepted by an unknown 2-tape DFA M, learns from MAT a two-tape nondeterministic finite automaton (2-tape NFA) M' accepting L in time polynomial in n and l, where n is the size of M and l is the maximum length of any counterexample provided during the learning process.

  • Predicting and Learning RNA Secondary Structures

    HASEGAWA Aki, UEMURA Yasuo, KOBAYASHI Satoshi, YOKOMORI Takashi

    GI   7   222 - 223  1996

     View Summary

    It is of great significance to develop an efficient software system for higher-level structural prediction in RNA/protein sequences. Speaking of RNA secondary structure prediction, it is inevitably required that a prediction system must have an ability to deal with so-called "pseudoknot" structures, one of the most typical and important constructs found in vivo, while no effective system is yet reported for predicting RNA secondary structures involving in pseudoknots.<BR>We are developing prediction systems for RNA secondary structures thatcan handle pseudo-knots in an elegant manner, where the developing systems are constructed based on the following two ways.

    DOI CiNii

  • Families of Noncounting Languages and Their Learnability from Positive Data

    S.Kobayashi, T.Yokomori

    International J. of Foundations of Computer Science   7;4   309 - 327  1996  [Refereed]

  • ON POLYNOMIAL-TIME LEARNABILITY IN THE LIMIT OF STRICTLY DETERMINISTIC AUTOMATA

    T YOKOMORI

    MACHINE LEARNING   19 ( 2 ) 153 - 179  1995.05  [Refereed]

     View Summary

    This paper deals with the polynomial-time learnability of a language class in the limit from positive data, and discusses the learning problem of a subclass of deterministic finite automata (DFAs), called strictly deterministic antomata (SDAs), in the framework of learning in the limit from positive data. We first discuss the difficulty of Pitt's definition in the framework of learning in the limit from positive data, by showing that any class of languages with an infinite descending chain property is not polynomial-time learnable in the limit from positive data. We then propose new definitions for polynomial-lime learnability in the limit from positive data. We show in our new definitions that the class of SDAs is iteratively, consistently polynomial-time learnable in the limit from positive data. In particular, we present a learning algorithm that learns any SDA M in the limit from positive data, satisfying the properties that (i) the time for updating a conjecture is at most O(lm), (ii) the number of implicit prediction errors is at most O(ln), where l is the maximum length of all positive data provided, m is the alphabet size of M and n is the size of M, (iii) each conjecture is computed from only the previous conjecture and the current example, and (iv) at any stage the conjecture is consistent with the sample set seen so far. This is in marked contrast to the fact that the class of DFAs is neither learnable in the limit from positive data nor polynomial-time learnable in the limit.

  • Grammatically Modeling and Predicting RNA Secondary Structures

    UEMURA Yasuo, HASEGAWA Aki, KOBAYASHI Satoshi, YOKOMORI Takashi

    GI   6   67 - 76  1995

     View Summary

    Tree Adjunct Grammar for RNA (TAG2RNA) is a new grammatical device to model RNA secondary structures including pseudoknots. An efficient parsing algorithm for this grammar is developed, and applied to some computational problems concerning RNA secondary structures. With this parser, we first try to predict secondary structures of RNA sequences which are known to form pseudoknots structures, and show prediction results which nicely match the known structures. Further, a (-1) frameshift grammar is constructed based on a biological observation that a (-1) frameshift might be caused from some structural features of RNA sequences. The proposed grammar is used to find candidate sequences for (-1) frameshift in Human spumaretrovirus gag and pol genes.

    DOI CiNii

  • Special Issue on Algorithmic Learning Theory (edited)

    S.Arikawa, S.Miyano, T.Yokomori

    Theoretical Computer Science   137 ( 1 )  1995

  • Special Issue on Algorithmic Learning Theory (edited)

    T.Yokomori

    IEICE Transactions on Information Systems   E78-D ( 5 )  1995

    Authorship:Lead author

  • Genome Informatics Workshop 1995 (edited)

    M.Hagiya, S.Miyano, K.Nakai, A.Suyama, T.Yokomori, T.Takagi

    Genome Informatics Series, Universal Academy Press   6  1995

  • DNA Evolutionary Linguistics and RNA Structure Modeling : A Computational Approach

    T.Yokomori, S.Kobayashi

    Proc.of 1st International IEEE Symposium on Intelligence in Neural and Biological Systems     38 - 45  1995

    Authorship:Lead author

  • Approximately Learning Regular Languages with respect to Reversible Languages : A Rough Set Based Analysis

    S.Kobayashi, T.Yokomori

    Proc. of 2nd Annual Joint Conference on Information Sciences     91 - 94  1995  [Refereed]

    Authorship:Last author

  • On Approximately Identifying Concept Classes in the Limit

    S.Kobayashi, T.Yokomori

    Lecture Notes in Artificial Intelligence   997   298 - 312  1995  [Refereed]

    Authorship:Last author

  • Learning Local and Recognizable ω-Languages and Monadic Logic Programs

    A.Saoudi, T.Yokomori

    Computational Learning Theory: Proc. of EuroCOLT'93     157 - 169  1994  [Refereed]

    Authorship:Last author

  • Learning Concatenations of Locally Testable Languages from Positive Data

    S.Kobayashi, T.Yokomori

    Lecture Notes in Artificial Intelligence   872   407 - 422  1994  [Refereed]

    Authorship:Last author

  • Inductive Inference of Monogenic Pure Context-free Languages

    N.Tanida, T.Yokomori

    Lecture Notes in Artificial Intelligence   872   560 - 573  1994  [Refereed]

    Authorship:Last author

  • Inductive Learning of Regular Sets from Examples : A Rough Set Approach

    T.Yokomori, S.Kobayashi

    Proc.of 3rd International Workshop on Rough Sets and Soft Computing     570 - 577  1994  [Refereed]

    Authorship:Lead author

  • An Extended Rough Set Theory Toward Approximate Learning of Formal Languages

    S.Kobayashi, T.Yokomori

    Proc.of 3rd International Workshop on Rough Sets and Soft Computing     481 - 489  1994  [Refereed]

    Authorship:Last author

  • Modeling RNA Secondary Structures Using Tree Grammars

    S.Kobayashi, T.Yokomori

    Proc.of 5th Genome Informatics Workshop     29 - 38  1994  [Refereed]

    Authorship:Last author

  • Learning Nondeterministic Finite Automata from Queries and Counterexamples

    T.Yokomori

    Machine Intelligence 13 (Machine Intelligence and Inductive Learning) (Furukawa, Michie and Muggleton, Eds.), Oxford Univ. Press     169 - 189  1994  [Refereed]

    Authorship:Lead author

  • Algorithmic Learning Theory (edited)

    K.Jantke, S.Kobayashi, E.Tomita, T.Yokomori

    Lecture Notes in Artificial Intelligence   744  1993

  • On Learning Systolic Languages

    T.Yokomori

    Lecture Notes in Artificial Intelligence   743   41 - 52  1993  [Refereed]

    Authorship:Lead author

  • A Similarity Measure for DNA Sequence Analysis Based on Locality

    T.Yokomori, S.Kobayashi

    Proc. of 4th Genome Informatics Workshop   4   283 - 292  1993  [Refereed]

    Authorship:Lead author

     View Summary

    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.<BR>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.

    DOI CiNii

  • Polynomial-Time MAT Learning of C-deterministic Context-free Grammars

    H.Shirakawa, T.Yokomori

    Transactions of Information Processing Society of Japan   34 ( 3 ) 380 - 390  1993  [Refereed]

    Authorship:Corresponding author

     View Summary

    This paper concerns the learning of context-free grammars, and introduces a subclass which we call context-deterministic (c-deterministic) grammars. The corresponding language class properly contains the classes or regular languages and of even linear languages, and is incomparable to the classes or simple deterministic languages and of one-counter languages. We show that the class of c-deterministic grammars is learnable in polynomial time from (extended) minimally adequate teacher (MAT). which gives a generalization of the corresponding results on regular languages in Ref 3) and even-linear languages in Ref.9).

    CiNii

  • Polynomial-Time Identification of Strictly Regular Languages in the limit

    N.Tanida, T.Yokomori

    IEICE Transaction on Inform. System   E75-D ( 1 ) 125 - 132  1992  [Refereed]

    Authorship:Corresponding author

  • Inductive Inference of 0L Languages

    T.Yokomori

    ``Lindenmayer Systems''(Rozenberg and Salomaa, Eds.), Springer-Verlag     115 - 132  1992  [Refereed]

    Authorship:Lead author

  • 計算論的言語理論とDNA計算

    横森貴, 篠原武

    情報処理   32 ( 3 ) 226 - 235  1991.03  [Refereed]  [Invited]

    Authorship:Lead author

  • Special Issue on A lgorithmic Learning Theory (edited)

    S.Arikawa, K.Jantke, T.Yokomori

    New Generation Computing   6 ( 3 )  1991

  • Algorithmic Learning Theory (edited)

    S.Arikawa, S.Goto, S.Ohsuga, T.Yokomori

    Ohmsha and Springer-Verlag    1990

  • Learning Context-free Languages Revisited

    T.Yokomori

    Proc. of Japan -Czechoslovak Symposium on Theoretical Foundation of Knowledge Information Processing     93 - 101  1989  [Refereed]

    Authorship:Lead author

  • Learning Context-free Languages Efficiently

    T.Yokomori

    Lecture Notes in Computer Science   397   104 - 123  1989  [Refereed]

    Authorship:Lead author

  • Inductive Inference of Context-free Languages Based on Context-free Expressions

    T.Yokomori

    International J. of Computer Mathematics   24   115 - 140  1988  [Refereed]

    Authorship:Lead author

  • On Purely Morphic Characterizations of Context-free Languages

    T.Yokomori

    Theoretical Computer Science   51   301 - 308  1987  [Refereed]

    Authorship:Lead author

    DOI CiNii

    Scopus

    3
    Citation
    (Scopus)
  • Set Abstraction-An Extension of All Solutions Predicates in Log ic Programming Languages

    T.Yokomori

    New Generation Computing   5 ( 3 ) 227 - 248  1987  [Refereed]

    Authorship:Lead author

  • On Analogical Query Processing in Logic Database

    T.Yokomori

    Proc. of International Conference on Very Large Data Base     376 - 383  1986  [Refereed]

    Authorship:Lead author

  • Logic Program Forms

    T.Yokomori

    New Generation Computing   4 ( 3 ) 305 - 319  1986  [Refereed]

    Authorship:Lead author

  • Representation Theorems and Primitive Predicates for Logic Prog rams

    T.Yokomori

    Bulletin of Informatics and Cybernetics   22 ( 1-2 ) 19 - 37  1986  [Refereed]

    Authorship:Lead author

  • Graph-Controlled Systems---An Extension of 0L-Systems

    T.Yokomori

    ''The Book of L''(Rozenberg and Salomaa, Eds.), Springer-Verlag     461 - 471  1986  [Refereed]

    Authorship:Lead author

  • Some Characterization Theorems for Tree Adjunct Languages

    T.Yokomori, A.K.Joshi

       1985.10

    Authorship:Lead author

  • AND-OR Queuing in Extended Concurrent Prolog

    J.Tanaka, T.Yokomori, M.Kishishita

    Lecture Notes in Computer Science   221   156 - 167  1985  [Refereed]

  • A Note on the Set Abstraction in Logic Programming Language

    T.Yokomori

    Proc. of International Conference on Fifth Generation Computer Systems'84     333 - 340  1984  [Refereed]

    Authorship:Lead author

  • An Inverse Homomorphic Characterizations of Full Principal AFL

    T.Yokomori, D.Wood

    Information Sciences   33   209 - 215  1984  [Refereed]

    Authorship:Lead author

  • Semi-linearity, Parikh-boundedness and Tree Adjunct Languages

    T.Yokomori, A.K.Joshi

    Information Processing Letters   17 ( 3 ) 137 - 143  1983  [Refereed]

    Authorship:Lead author

  • A Three-restricted Normal Form Theorem for ET0L Languages

    T.Yokomori, D.Wood, K.-J.Lange

    Information Processing Letters   14 ( 3 ) 97 - 100  1982  [Refereed]

    Authorship:Lead author

  • Linguistic Similarity Test Method Based on Fuzzy Relations

    T.Yokomori

    Behaviormetrika   9 ( 9 ) 81 - 92  1981  [Refereed]

    Authorship:Lead author

     View Summary

    In this paper we present new methods for testing linguistic similarity using the concept of fuzzy relation. By applying a fuzzy clustering technique, we show that the problem of testing linguistic similarity can be regarded as a clustering problem under fuzzy conditions, and give some methods of measuring the similarity of natural languages.

    DOI CiNii

  • A Note on the Equivalence Problem for a Class of Unary L-systems

    T.Yokomori

    Trans. of the IECE Japan   E64 ( 8 ) 551 - 552  1981  [Refereed]

    Authorship:Lead author

  • Stability and Noise in Lindenmayer Systems

    T.Yokomori

    Trans. of the IECE Japan   E63 ( 4 ) 258 - 261  1980  [Refereed]

    Authorship:Lead author

  • Stochastic Characterizations of E0L Languages

    T.Yokomori

    Information and Control   45 ( 1 ) 26 - 33  1980  [Refereed]

    Authorship:Lead author

▼display all

Books and Other Publications

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

    小林聡, 萩谷昌己, 横森貴

    近代科学社  2015.12

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

    森北出版  2013.12

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

    M.Hagiya, S.Kobayashi, K.Komiya, F.Tanaka, T.Yokomori

    Springer  2012.07

  • 応用 情報数学

    サイエンス社  2011.06

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

    シリーズ編集

    近代科学社  2011.03

  • 基礎 情報数学

    サイエンス社  2008.06

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

    分担執筆

    NTS出版  2006.08

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

    分担執筆

    共立出版  2006.08

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

    サイエンス社  2005.03

  • Grammatical Inference and Learning

    Formal Languages and Applications (eds.Martin-Vide, Mitrana and Paun), Springer  2004

  • DNAコンピュータ

    培風館  2001.12

  • 計算論的学習

    培風館  2001.10

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

    横森貴

    Computer Today/サイエンス社  2000.11

  • 分子計算の理論モデル

    横森貴

    数理科学/サイエンス社  2000.07

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

    シュプリンガーフェアラーク東京  1999.12

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

    横森貴

    bit/共立出版  1997.08

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

    オーム社  1992.08

  • オートマトン・言語理論

    森北出版  1992.05

  • 計算機数学

    森北出版  1990

▼display all

Presentations

  • 「自然計算研究の最前線とその将来」

    横森貴  [Invited]

    情報科学技術フォーラム(第13回FIT) 

    Presentation date: 2014

  • Introduction to Natural Computing,(Tutorial Lecture)

    T.Yokomori  [Invited]

    8th Intern. Meeting on DNA Based Computers 

    Presentation date: 2002.06

  • DNAコンピューティング

    横森貴  [Invited]

    日本ソフトウェア科学会(チュートリアル講演) 講習会資料シリーズNo.31 

    Presentation date: 2001.07

  • Computational Linguistics for DNA Evolution and RNA Structure Modeling

    T.Yokomori  [Invited]

    Presentation date: 1995.03

  • Analogical Reasoning as Probabilistic Reasoning

    T.Yokomori

    Presentation date: 1986.03

  • A Formal Language Theoretic Approach to Logic Programming Languages

    T.Yokomori

    Presentation date: 1984.10

▼display all

Research Projects

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

    Project Year :

    2017.04
    -
    2020.03
     

     View Summary

    生命活動は生体化学反応によって維持されている.その生体化学反応における情報処理メカニズムを形式化して理解するために,我々は多重集合をベースとした計算モデルとして反応オートマトン(Reaction Automaton:RA)を提案した.この多重集合はこれまで脇役的な存在であったが,近年になって離散的状態空間における情報処理モデルの研究が盛んになるにつれて,特に化学系・生物系の計算モデルにおいてその重要性が注目されている.従来,化学反応系の研究は常微分方程式系を用いた手法が一般的であった.他方,反応系に関わる分子数と分子種の数が比較的少数である場合,状態空間を離散的な多重集合とみなす計算モデルが有効である.この離散的アプローチでは少分子系の振る舞いに関する構成的な解析が可能となり,反応系の動作機構がアルゴリズムとして理解できる(すなわち,化学反応がプログラミング可能となる)という利点を有する.本研究における目的は,分子レベルでの化学反応系の振る舞いを解析するために,多重集合をベースとする構成的な離散的計算モデルを構築し,そこで得られる計算論的な知見をもとに,最終的に化学反応に基づく反応プログラミング技法を確立する事である.本年度の研究実績は以下のとおりである.(1). Chemical Reaction Automata(CRA)を拡張した記号列変換器にまで拡張したChemical Reaction Transducers(CRT)を新たに導入し,その記号列変換器としての能力を表現定理として特徴付ける結果を得た.詳細な説明は【現在までの進捗状況】に譲る.(2).提案したReaction Automata Theory(RAT)の重要性に鑑み,RATに関するサーベイ論文を招待論文として発表して,化学反応計算分野の研究者への広報活動を行った.CRAモデルはDNAなど生体ナノ高分子による実装の可能性がIn Vitro実験において示されており,現実的な側面において重要である.そこで生体内での高分子による反応物の変化推移プロセスをモデル化するために,CRAモデルを拡張した記号列変換器としての形式システムChemical Reaction Transducers(CRT)を提案した.CRTは,多重集合の状態遷移によってC『入力列に対してそれをある目的にそって処理して出力する“化学反応による記号列変換システム”』である.より具体的には,CRTはCRAに出力アルファベットΔを付加して,各反応を4項組 (a,R,P,b)として定義した.ここで,(R,P)はCRA の反応規則であり,aは入力分子を,bは出力分子を表す.そしてこのモデルに関する計算能力を解析し,以下の結果を得た.(1).CRTを(分子種の個数に関して)より簡単な二つのCRT(TとT')で実現できる場合を考察した.これには,CRTの分解(Decomposition)と分割(Factorization) という2つの概念を導入し,CRTが分解可能であるための十分条件を示した.また,CRTの分割に関しては「CRTは二つのa-transducerと固定された関数とに分割できる」という表現定理を導くことができた.(a-transducerとは有限状態をもつ変換器であり,CRTをより簡単化したものである.)(2).我々が2012年に発表した反応オートマトン理論は,徐々に学界での知名度を得ているが,さらなる広報活動が必要である.そのため,国際誌上でのサーベイ論文の発表を行った.当初は成果発表のための海外出張を予定していたが,新型コロナウィルス等の社会情勢の急変もあり,予期しない業務(オンライン授業の準備等)に忙殺された.そのため研究計画の進捗はやや遅れ気味である.本研究の最終目的を考慮すると,RA/CRAモデルを拡張した“化学反応による記号列変換システム”が重要な役割を演じると思われる.すなわち,RA Transducer(RAT)や(前述の)CRTを基本とする「化学反応ネットワークによる化学反応プログラム」という概念の形式モデルを提案し,その実現手法である“化学反応プログラミング”を実装する方法を探究する.本年度は(不安定な現在の社会状況下における不確定性はあるが)以下の,昨年度に掲げた諸課題を,今後の研究テーマとして推進したい:①上述した拡張モデルRAT/CRTを基本的な形式モデルとするが,より簡潔なモデルを基本要素とするネットワークによる計算モデルを考察する.また,確率的要素など必要に応じて変形や拡張を行い各々のモデルを補強していく.そして,それらのもつ情報処理能力を解析する.②生体内の化学反応回路の動的平衡状態などを始めとする高度な生体維持機能のメカニズムを解明するために,細胞内の生体分子群を“構造をもつ要素からなる多重集合”として抽象化したモデルを解析する.③上述のモデルの解析結果をもとに,化学反応に基づくプログラミング技法の基礎的考察を行う

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

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research

    Project Year :

    2012.06
    -
    2017.03
     

    Kobayashi Satoshi, Yokomori Takashi, Imura Junichi, Hayami Ken, Yannick Rondelez

     View Summary

    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

  • 分子プログラミング

    科学研究費助成事業(東京大学)  科学研究費助成事業(特定領域研究)

    Project Year :

    2002
    -
    2007
     

     View Summary

    本研究領域の目標は,主としてDNA分子によって作られた分子システムのためのシステマティックな設計論を確立することである.本研究領域の研究項目は多岐に渡っており,その研究成果も膨大であるため、本研究領域の主目的である,分子計算のための計算分子と分子反応の設計論および応用に関係する研究成果の中から,領域全体を通して主要なものを取捨選択し簡潔にまとめると,以下のようになる.1.計算分子(DNA配列)の設計論(1-1)望ましくない構造を作らない配列の設計(1-2)望ましい構造を作る配列の設計(1-3)自在に構造変化する配列の設計(1-4)構造変化の数理モデルと実験的検証2.分子反応の設計論(2-1)反応の並列化(2-2)反応の精密化(2-3)進化のための反応3.計算論的ナノテクノロジー応用(3-1)DNAナノ構造の高信頼アセンブリ(3-2)4*4DNAタイルによるバイナリカウンタの実現(3-3)ヘアピンとバルジによる並行計算(3-4)光ライゲーションによる耐熱性DNAナノ構造体の構築4.合成生物学応用(4-1)in vitro論理演算素子,発振素子の構築(4-2)in vivo論理演算素子の構築(4-3)大腸菌を用いたバクテリアコンピュータの開発(4-4)WetTDGAによるaaRSの基質改変(1),(2)は基礎的な設計技術に関する理論および実験であり、主として研究期間の前半の成果である.特に(1)の配列設計は, DNAを計算分子とするすべての分子計算に共通した基礎的成果である。(3),(4)は,分子プログラミングの次世代の展開として重要視されている計算論的ナノテクノロジーおよび合成生物学への応用研究であり,研究期間の後半の成果である

  • 分子プログラミング

    科学研究費助成事業(東京大学)  科学研究費助成事業(特定領域研究)

    Project Year :

    2002
    -
    2007
     

     View Summary

    本研究領域の目標は,主としてDNA分子によって作られた分子システムのためのシステマティックな設計論を確立することである.本研究領域の研究項目は多岐に渡っており,その研究成果も膨大であるため、本研究領域の主目的である,分子計算のための計算分子と分子反応の設計論および応用に関係する研究成果の中から,領域全体を通して主要なものを取捨選択し簡潔にまとめると,以下のようになる.
    1.計算分子(DNA配列)の設計論(1-1)望ましくない構造を作らない配列の設計(1-2)望ましい構造を作る配列の設計(1-3)自在に構造変化する配列の設計(1-4)構造変化の数理モデルと実験的検証
    2.分子反応の設計論(2-1)反応の並列化(2-2)反応の精密化(2-3)進化のための反応
    3.計算論的ナノテクノロジー応用(3-1)DNAナノ構造の高信頼アセンブリ(3-2)4*4DNAタイルによるバイナリカウンタの実現(3-3)ヘアピンとバルジによる並行計算(3-4)光ライゲーションによる耐熱性DNAナノ構造体の構築
    4.合成生物学応用(4-1)in vitro論理演算素子,発振素子の構築(4-2)in vivo論理演算素子の構築(4-3)大腸菌を用いたバクテリアコンピュータの開発(4-4)WetTDGAによるaaRSの基質改変
    (1),(2)は基礎的な設計技術に関する理論および実験であり、主として研究期間の前半の成果である.特に(1)の配列設計は, DNAを計算分子とするすべての分子計算に共通した基礎的成果である。(3),(4)は,分子プログラミングの次世代の展開として重要視されている計算論的ナノテクノロジーおよび合成生物学への応用研究であり,研究期間の後半の成果である.

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

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research

    Project Year :

    1990
    -
    1991
     

    TOMITA Etsuji, YOKOMORI Takashi, TAKEDA Mitsuo, TAKAHASHI Haruhisa

     View Summary

    1. Given a graph of n nodes, we have devised an 0(n^3)-time algorithm NMCLIQ for finding a near-maximum clique. We have confirmed in experiments for several graphs with up to 400 nodes that the orders of maximal c)iques found by NMCLIQ are almost more than 85% of the maximum orders.2. We have developed an 0(n^3)-time algorithm RACLIQUE for finding a near-maximum clique in a given graph of n nodes. While the algorithm is based upon the notion of Boltzmann machines, it employs no simulated annealing and hence is simple to control its execution. We have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that almost optimum solutions can be found very efficiently. In addition, further improvements and variations are considered and verified to be very useful.3. We have devised two non-searching algorithms for the n-queen problem which are based upon the former resuit for finding a near-maximum clique. We have confirmed in experiments for up to 50, 000 queens that they are extremly efficient

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

     View Summary

    班の研究会は,6月(西尾班と合同)と11月に開いた.各分担者による研究成果は,以下に示す通りであるが,本年度も当初の計画通りの成果が得られた.(1)概念形成と知識獲得の論理.有川は,概念形成と知識獲得を発展させて,機械発見の論理の基礎を構築し,仮説空間自体の論駁可能性が基本であることを明らかにした.小野は,知識獲得の論理を従来の様相論理に基づいた知識の論理の観点ではなくて,累積的推論の観点から整理して,新しい体系の構築に踏み出した.(2)推論による概念形成と知識獲得.石塚は,仮説推論の高速化の研究を発展させ,知識ベース・コンパイルや数理計画法準拠の手法等を用いて,高速化メカニズムを明らかにした.原口は,類推理論を発展させ,新しくアナロジーを構造写像として定義し,構造写像にガイドされる形式で推論する新しい類推方式をモデル推論の枠組を用いて与え,その極限同定性を証明した.佐藤は,帰納推論の方式の精緻な特徴付けに成功し,帰納推論可能性の新しい有用な必要十分条件を与え帰納推論の研究を飛躍的に発展させた.(3)概念形成と知識獲得における計算量.丸岡は,学習過程と情報圧縮過程との関係を,単調性や保存性の条件との関連のもとで研究し,新しい学習アルゴリズムを与えた.横森は,言語の帰納学習を扱い,ある種のオートマトンのクラスの多項式時間MAT学習可能性を明らかにした.富樫は,再帰的並行プロセスの学習理論を展開し,帰納推論による合成アルゴリズムを与え,理論の妥当性を実証した

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

     View Summary

    DNA,RNA,あるいは蛋白質の高次構造を予測するために重要なことは,それらの高次構造を表現するための形式モデルを提案することである.そのために,平成6年度の研究では,まず言語理論の枠組を援用しある種の木文法(tree grammar)に着目した.この木文法は元来自然言語処理の目的で提案されたものであるが,DNA配列などもある目的を持って生成された記号列であるという観点からすると,これらの形式文法を道具立てとしてDNA配列の性質をとらえられる可能性がある.実際,我々の研究から,特にRNAの二次構造に焦点をしぼったとき,この木文法をある方法で修正したモデルがRNA二次構造の表現文法として最適であることが判った.我々はこの文法をタグ付き木文法(TAG^2_<RNA>)と名付けたが,この文法によって非常に広範な種目に現れる既存のRNA二次構造が,無駄なくかつ無理書く表現できる.実際,生物データからの具体例を幾つか挙げると,HIV-2 gag-pol領域におけるRNA,グループIイントロンに見られるRNA,種々のtRN

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

     View Summary

    DNA,RNA,あるいは蛋白質の高次構造を予測するために重要なことは,それらの高次構造を表現するための形式モデルを提案することである.そのために,平成6年度の研究では,まず言語理論の枠組を援用しある種の木文法(tree grammar)に着目した.この木文法は元来自然言語処理の目的で提案されたものであるが,DNA配列などもある目的を持って生成された記号列であるという観点からすると,これらの形式文法を道具立てとしてDNA配列の性質をとらえられる可能性がある.実際,我々の研究から,特にRNAの二次構造に焦点をしぼったとき,この木文法をある方法で修正したモデルがRNA二次構造の表現文法として最適であることが判った.我々はこの文法をタグ付き木文法(TAG^2_<RNA>)と名付けたが,この文法によって非常に広範な種目に現れる既存のRNA二次構造が,無駄なくかつ無理書く表現できる.実際,生物データからの具体例を幾つか挙げると,HIV-2 gag-pol領域におけるRNA,グループIイントロンに見られるRNA,種々のtRNA,リボゾームRNAなどなどがある.現在,これらの研究知見をもとに,TAG^2_<RNA>による各種のRNA二次構造の同定(分類)システムを試作中であり,今後は,蛋白質の高次構造の予測問題などへの応用していく予定である.また,より進んだ研究として,DNA・RNA構造の予測問題をこの木文法に対する学習問題として定式化し,その数理的な解析,および学習アルゴリズムの開発を行なうことが考えられる.次年度では,本年度における理論的な知見・成果を基に同定・予測システムをより洗練されたものに改良すると同時に,試作された高次構造予測プロトタイプシステムの実験・評価結果をフィードバックすることにより徐々に改良を行ない,より完成度の高いシステムの構築を目指す.役割分担としては,本年度と同様,横森(研究代表者)が主に本研究の理論面の改良を担当し,小林(研究分担者)が高次構造予測システムの改良を担当する

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

     View Summary

    (1)DNA配列の組み替え現象をモデル化したスプライシング演算をさらに一般化することにより「環状スプライシングモデル」を提案し,この計算モデルの理論的能力を解析した.結果として,この計算モデルがTuring機械と等価な万能計算の能力を有することを示した.(2)本研究において,1994年のScience誌に掲載されたAdlemanのDNA計算の実験で用いられた"アニーリング","融解',"検知"という分子計算における3つの基本操作が,実は計算能力として(従来の計算機と同等な)Turing万能計算能力をもつことを示した.この計算モデルにおいては計算物質としてDNAが想定されていた.そこで,より抽象的な枠組みを設定して,各分子は符号化できかつ分子同士が自律的に会合する能力を有する計算モデルを研究した.その結果,『計算=自律的会合+形態変化』という新計算パラダイムが成り立つことが分かった.上記の考えを一般化し,自然界における様々な現象・原理を問題解決のための設計論という視点で見直すことにより"分子プログラミング"という概念を提唱した.そして,分子プログラミングのために必要な要素技術の検討と実現手法の開発の基礎的な研究を行なった

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

     View Summary

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

▼display all

Misc

▼display all

 

Overseas Activities

  • 帰納的学習の基礎理論とその生命情報学への応用

    2006.03
    -
    2007.03

    スペイン   セビリア大学

    フランス   サンテティエンネ大学

    カナダ   ブリティッシュコロンビア大学

Internal Special Research Projects

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

    2017  

     View Summary

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

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

    2016  

     View Summary

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

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

    2016  

     View Summary

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

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

    2015  

     View Summary

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

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

    2015  

     View Summary

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

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

    2013  

     View Summary

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

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

    2013   大久保文哉

     View Summary

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

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

    2012   大久保文哉

     View Summary

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

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

    2011   大久保文哉

     View Summary

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

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

    2002   上田和紀, 楠元範明

     View Summary

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

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

    1998  

     View Summary

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

▼display all