×

Active symbols in grammars with valuations. (English) Zbl 1371.68134

Summary: 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.

MSC:

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI

References:

[1] Bordihn, H., On deterministic grammars with valuations, Wiss. Z. Univ. Otto-von Gruericke Magdeburg, 31, 1-3 (1987) · Zbl 0639.68070
[2] Bordihn, H.; Holzer, M., On the number of active symbols in L and CD grammar systems, J. Autom. Lang. Comb., 6, 4, 411-426 (2001) · Zbl 0997.68066
[3] Dassow, J., Grammars with valuations - a discrete model for self-organization of biopolymers, Discrete Appl. Math., 4, 161-174 (1982) · Zbl 0485.68062
[4] Dassow, J.; Vaszil, G., On the number of active symbols in Lindenmayer systems, Internat. J. Found. Comput. Sci., 22, 1, 223-235 (2011) · Zbl 1213.68345
[5] Klejn, H.; Rozenberg, G., A study in parallel rewriting systems, Inf. Control, 44, 134-163 (1980) · Zbl 0436.68051
[6] Păun, G.; Dassow, J., \(L(E T 0 L_{[5]}) = L(E T 0 L)\), Elektronische Informationsverarbeitung und Kybernetik, J. Inf. Process. Cybern. EIK, 18, 6, 345-348 (1982) · Zbl 0538.68059
[7] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[8] Wood, D., Theory of Computation (1987), John Wiley & Sons: John Wiley & Sons New York · Zbl 0734.68001
[9] Yokomori, T.; Wood, D.; Lange, K.-J., A three-restricted normal form for ET0L languages, Inform. Process. Lett., 14, 3, 97-100 (1982) · Zbl 0483.68068
[10] Yokomori, T.; Wood, D.; Lange, K.-J., Erratum at a three-restricted normal form for ET0L languages, Inform. Process. Lett., 21, 53 (1985) · Zbl 0571.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.