zbMATH — the first resource for mathematics

Basic ideas of selective substitution grammars. (English) Zbl 0637.68085
Trends, techniques, and problems in theoretical computer science, 4th Int. Meet. Young Comput. Sci., Smolenice/Czech. 1986, Lect. Notes Comput. Sci. 281, 75-95 (1987).
[For the entire collection see Zbl 0633.00024.]
In this paper a general framework for the study of rewriting systems is discussed.
After some preliminaries the concept of a selective substitution grammar is presented and motivated in Section 2. In Section 3 we introduce s- grammars as instances of selective substitution grammars. This gives rise to a simple framework still general enough to characterize in a uniform way different features of rewriting systems. In the remainder of the paper we review the lines of search pursued until now.

68Q45 Formal languages and automata