zbMATH — the first resource for mathematics

Computations in coordinated pair systems. (English) Zbl 0642.68133
Summary: Selective substitution grammars provide a rather general framework for the grammatically oriented formal language theory [see, e.g., the third author, Elektron. Informationsverarbeitung Kybernetik 13, 455-463 (1977; Zbl 0381.68062), the third author and H. C. M. Kleijn, Theor. Comput. Sci. 16, 237-269 (1981; Zbl 0469.68079)]. They were generalized by the third author [ibid. 37, 31-50 (1985; Zbl 0601.68054)] to coordinated table selective substitution systems (cts systems) which provide a convenient unifying framework for both grammars and machines (automata).
The present paper investigates coordinated pair (cp) systems which form a subclass of cts systems corresponding in a very natural way to push-down automata: thus cp systems generate context-free languages (all and only). This paper investigates the structure of computations in cp systems.

68Q45 Formal languages and automata