Skip to Main content Skip to Navigation
Journal articles

Relations between Control Mechanisms for Sequential Grammars1

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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03324134
Contributor : Frédéric Davesne <>
Submitted on : Monday, August 23, 2021 - 12:13:32 PM
Last modification on : Wednesday, August 25, 2021 - 3:27:23 AM

Identifiers

Citation

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, Marion Oswald. Relations between Control Mechanisms for Sequential Grammars1. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2021, 181 (2-3), pp.239--271. ⟨10.3233/FI-2021-2058⟩. ⟨hal-03324134⟩

Share

Metrics

Record views

14