TY  - JOUR
A1  - Bordihn, Henning
T1  - Active symbols in grammars with valuations
JF  - Theoretical computer science
N2  - Grammars with valuations are context-free rewriting mechanisms where the derivation process is controlled by a recursive function that evaluates strings. They have been introduced by Jurgen Dassow as models for the molecular replication process taking into account its selective character. A symbol is active in a grammar with valuation if it can be rewritten non-identically. This paper studies the effect of restricting the number of active symbols in grammars with valuations and several variants thereof to their generative power. It is investigated in which cases the number of active symbols induces infinite strict hierarchies and when the hierarchies collapse. The induced language families are compared among one another. (C) 2016 Elsevier B.V. All rights reserved.
KW  - Formal languages
KW  - Biologically inspired formal systems
KW  - Descriptional complexity
Y1  - 2017
U6  - https://doi.org/10.1016/j.tcs.2016.11.008
SN  - 0304-3975
SN  - 1879-2294
VL  - 682
SP  - 42
EP  - 48
PB  - Elsevier
CY  - Amsterdam
ER  -