Computations in coordinated pair systems. (English) Zbl 0642.68133

Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G.

Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 9, 455-480 (1986).

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.

MSC:

68Q45

Formal languages and automata

Keywords:

coordinated pair systems; Selective substitution grammars; formal language; coordinated table selective substitution systems; cts systems; push-down automata; cp systems; context-free languages

Citations:

Zbl 0381.68062; Zbl 0469.68079; Zbl 0601.68054