Chemical Reaction Regular Grammars

Fumiya Okubo, Kaoru Fujioka, Takashi Yokomori

Research output: Contribution to journalArticlepeer-review


We propose a new type of computing devices based on grammatical formulation augmented by multiset storages, called chemical reaction regular grammars (CRRGs), and investigate some formal language theoretic characterizations of CRRGs including their generative capabilities. Shortly, a CRRG is a regular grammar with multisets, while its computational capability exhibits very intriguing aspects depending on the manners of rule applications. Firstly, we show that the class of languages (denoted by CRRLλ) generated by CRRGs coincides with the class of languages accepted by chemical reaction automata (Okubo and Yokomori in Nat Comput 15(2): 215–224, 2016), whose implication is that the computing power of CRRGs is also equivalent to that of several known devices introduced from different motivations such as Petri nets (Peterson in ACM Comput Surv 9(3):223–252, 1977) and partially blind 1-way multicounter machines (Greibach in Theor Comput Sci 7:311–324, 1979). Second, a new manner of rewriting strategy is integrated into CRRGs and we show that CRRGs working in maximal-sequential manner can generate any recursively enumerable language, which is an unexpected result with a surprise. In contrast, it is also shown that regulated controls due to regular sets and matrix constraints do not enhance the computing power of CRRGs. Third, for each k≥ 1 a subclass of languages k-CRRLλ is considered, where k is the number of different symbols for multisets of CRRGs. We show that the class of languages is a full principal semi-AFL, which is obtained from a characterization result that L is in k-CRRLλ iff L= h(g- 1(Bk) ∩ R) for some homomorphisms g, h, a regular set R, where Bk is a paritally balanced language over k-symbol alphabet.

Original languageEnglish
JournalNew Generation Computing
Publication statusAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Chemical Reaction Regular Grammars'. Together they form a unique fingerprint.

Cite this