TY - JOUR

T1 - Chemical Reaction Regular Grammars

AU - Okubo, Fumiya

AU - Fujioka, Kaoru

AU - Yokomori, Takashi

N1 - Funding Information:
The work of F. Okubo was in part supported by JSPS KAKENHI, Grants-in-Aid for Young Scientists (B) JP24700304. The work of T. Yokomori was in part supported by JSPS KAKENHI, Grant-in-Aid for Scientific Research (C) JP17K00021.
Publisher Copyright:
© 2022, Ohmsha, Ltd. and Springer Japan KK, part of Springer Nature.

PY - 2022

Y1 - 2022

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

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

UR - http://www.scopus.com/inward/record.url?scp=85126189071&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126189071&partnerID=8YFLogxK

U2 - 10.1007/s00354-022-00160-8

DO - 10.1007/s00354-022-00160-8

M3 - Article

AN - SCOPUS:85126189071

SN - 0288-3635

JO - New Generation Computing

JF - New Generation Computing

ER -