A General Framework for Sequential Grammars with Control Mechanisms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

A General Framework for Sequential Grammars with Control Mechanisms

Rudolf Freund
  • Fonction : Auteur
  • PersonId : 1022707

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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⟩
26 Consultations
43 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More