Basic ideas of selective substitution grammars. (English) Zbl 0637.68085

Kleijn, H. C. M.

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.

MSC:

68Q45

Formal languages and automata

Keywords:

rewriting systems; selective substitution grammar