Affiliations: [a] Vladimir Andrunachievici Institute of Mathematics and Computer Science, Academiei 5, Chişinău, MD-2028, Moldova. [email protected] | [b] Faculty of Informatics, TU Wien, Favoritenstraße 9–11, 1040 Vienna, Austria. [email protected] | [c] IBISC, Université Évry, Université Paris-Saclay, 23 Boulevard de France, 91025, Évry, France. [email protected] | [d] Faculty of Informatics, TU Wien, Favoritenstraße 9–11, 1040 Vienna, Austria. [email protected]
Correspondence:
[†]
Address for correspondence: Faculty of Informatics, TU Wien, Favoritenstraße 9–11, 1040 Vienna, Austria.
Note: [*] This paper refines and extends the results presented at MCU 2018 in Fontainebleau, France, see [1] and [2].
Abstract: We extend and refine previous results within the general framework for regulated rewriting based on the applicability of rules in sequential grammars [3]. Besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules we also consider the new variant of activation and blocking of rules as investigated in [1, 2, 4]. Moreover, we exhibit special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups. Especially we prove that array grammars defined on Cayley grids of finitely presented groups using #-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, priority relations on rules, or activation and blocking of rules have the same computational power as such array grammars using arbitrary array productions.
Keywords: general framework, regulating rewriting, sequential grammars
