Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952034 | Theoretical Computer Science | 2017 | 7 Pages |
Abstract
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 Jürgen 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Henning Bordihn,