A General Framework for Sequential Grammars with Control Mechanisms - Descriptional Complexity of Formal Systems
Conference Papers Year : 2019

A General Framework for Sequential Grammars with Control Mechanisms

Rudolf Freund
  • Function : Author
  • PersonId : 1022707

Abstract

Since more than five decades, many control mechanisms have been introduced for sequential string grammars, including control graphs, matrices, permitting and forbidden contexts, and order relations. These control mechanisms then have been extended to sequential grammars working on objects different from strings, for example, to array, graph, and multiset grammars. Many relations between the languages generated by sequential grammars working on these objects with different control mechanisms were shown to be similar to the relations already proved for the string case. Within a general framework for regulated rewriting based on the applicability of rules in sequential grammars, many relations between various control mechanisms can be established in a very general setting without any reference to the underlying objects the rules are working on. Besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules, the new variants of activation of rules as well as activation and blocking of rules are considered. Special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups are exhibited based on the general results. Finally, some general results for cooperating distributed grammar systems are established.
Fichier principal
Vignette du fichier
480958_1_En_1_Chapter.pdf (430.21 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02387286 , version 1 (29-11-2019)

Licence

Identifiers

Cite

Rudolf Freund. A General Framework for Sequential Grammars with Control Mechanisms. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.1-34, ⟨10.1007/978-3-030-23247-4_1⟩. ⟨hal-02387286⟩
48 View
66 Download

Altmetric

Share

More