Relations between Control Mechanisms for Sequential Grammars
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
279 0
SM ISO690:2012
ALHAZOV, Artiom, FREUND, Rudolf, IVANOV, Sergiu, OSWALD, Marion. Relations between Control Mechanisms for Sequential Grammars. In: Fundamenta Informaticae, 2021, nr. 2-3(181), pp. 239-271. ISSN 0169-2968. DOI: https://doi.org/10.3233/FI-2021-2058
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Fundamenta Informaticae
Numărul 2-3(181) / 2021 / ISSN 0169-2968 /ISSNe 1875-8681

Relations between Control Mechanisms for Sequential Grammars

DOI:https://doi.org/10.3233/FI-2021-2058

Pag. 239-271

Alhazov Artiom1, Freund Rudolf2, Ivanov Sergiu34, Oswald Marion2
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 Faculty of Informatics, TU Wien,
3 Universitatea Paris-Saclay,
4 IBISC, Universite Evry
 
 
Disponibil în IBN: 25 august 2021


Rezumat

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. 

Cuvinte-cheie
general framework regulating rewriting sequential grammars