Computations in Coordinated Pair Systems

Article type: Research Article

Authors: Ehrenfeucht, A.^a | Hoogeboom, H.J.^b | Rozenberg, G.^b

Affiliations: [a] University of Colorado, Department of Computer Science, Boulder, Colorado 80309, U.S.A. | [b] University of Leiden, Institute of Applied Mathematics and Computer Science, P.O. Box 9512, 2300 RA Leiden, The Netherlands

Abstract: Selective substitution grammars provide a rather general framework for the grammatically oriented formal language theory (see, e.g., [R1], [K], and [KR]). They were generalized in [R2] to coordinated table selective substitution systems (ds 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.

DOI: 10.3233/FI-1986-9405

Journal: Fundamenta Informaticae, vol. 9, no. 4, pp. 455-480, 1986