Skip to Main content Skip to Navigation
Conference papers

A General Framework for Sequential Grammars with Control Mechanisms

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:35:29 PM
Last modification on : Friday, November 29, 2019 - 5:01:54 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views