zbMATH — the first resource for mathematics

Adding global forbidding context to context-free grammars. (English) Zbl 0603.68078
A 1S grammar generalizes a context-free grammar in the following way: a production \(A\to \alpha\) can be applied to a string uAv (to rewrite the designated occurrence of A) provided that all letters from u belong to a fixed alphabet X and all letters from v belong to a fixed alphabet Z (the alphabets X and Z are independent of the production). It is proved that a language is generated by a 1S grammar if and only if it is context-free: this solves an open problem from the theory of selective substitution grammars [H. C. M. Kleijn and G. Rozenberg, Inf. Control 48, 221-260 (1981; Zbl 0469.68080); corrigendum ibid. 52, 364 (1982; Zbl 0506.68064)].

68Q45 Formal languages and automata
Full Text: DOI
[1] Chottin, L., Langage algébriques et système de réécriture rationnels, RAIRO inform. théor., 16, 93-112, (1982) · Zbl 0498.68048
[2] Ehrenfeucht, A.; Maurer, H.A.; Rozenberg, G., Continuous grammars, Inform. and control., 46, 71-91, (1980) · Zbl 0471.68050
[3] Gonczarowski, J.; Kleijn, H.C.M.; Rozenberg, G., Closure properties of selective substitution grammars, part 1, Internat. J. comput. math., 14, 19-42, (1983) · Zbl 0514.68071
[4] Gonczarowski, J.; Kleijn, H.C.M.; Rozenberg, G., Closure properties of selective substitution grammars, part 2, Internat. J. comput. math., 14, 109-135, (1983) · Zbl 0521.68086
[5] Kleijn, H.C.M., Selective substitution grammars based on context-free productions, () · Zbl 0637.68085
[6] Kleijn, H.C.M.; Rozenberg, G., Context-free like restriction on selective rewriting, Theoret. comput. sci., 16, 237-269, (1981) · Zbl 0469.68079
[7] Kleijn, H.C.M.; Rozenberg, G.; Kleijn, H.C.M.; Rozenberg, G., Sequential, continuous and parallel grammars, Inform. and control, Inform. and control, 52, 364-260, (1982), Corrigendum · Zbl 0506.68064
[8] Lomkovskaja, M.V., O nekotoryh svjostvah k-uslovnyh grammatik, Nauchn-tekhn. informatsiya ser., 2, 1, 16-21, (1972)
[9] Mayer, O., Some restrictive devices for context-free grammars, Inform. and control., 20, 69-92, (1972) · Zbl 0248.68035
[10] Penttonen, M., ET0L grammars and N grammars, Inform. process. lett., 4, 11-13, (1975) · Zbl 0312.68045
[11] Rozenberg, G., Selective substitution grammars (towards a framework for rewriting systems), part I: definitions and examples, Elektron. informationsverarb. kybernet., 13, 455-463, (1977) · Zbl 0381.68062
[12] Rozenberg, G.; von Solms, S.H., Priorities on context conditions in rewriting systems, Inform. sci., 14, 15-51, (1978) · Zbl 0416.68066
[13] Rozenberg, G.; Wood, D., Context-free grammars with selective rewriting, Acta inform., 13, 257-268, (1980) · Zbl 0445.68058
[14] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[15] van der Walt, A.P.J., Random context languages, (), 66-68 · Zbl 0221.68047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.