Iterated Context-Independent Rewriting -- From Grammars to Transformations and Their Fixed Points. An Introduction.

In this introductory survey we show that context-free grammars and similar context-independent rewriting systems can be viewed as a mapping that transforms a finite number of finite languages into a countable language. These transformations also allow (a finite number of) languages from a family $K$ rather than finite languages. Many well-known closure properties can be characterized in terms of fixed points of such transformations. Finally, attention is focussed on (i) the set of all these fixed points, and (ii) partially ordered monoids generated by a finite number of such transformations.