CONTEXTUAL GRAMMARS: PARALLELISM AND BLOCKING OF DERIVATION

Article type: Research Article

Authors: P$\check{A}$un, Gheorghe | Rozenberg, Grzegorz | Salomaa, Arto

Affiliations: Institute of Mathematics of the Romanian Academy of Sciences, P.O. Box 1-764, 70700 Bucureşti, Romania | University of Leiden, Department of Computer Science, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands | Academy of Finland and University of Turku, Department of Mathematics, 20500 Turku, Finland

Abstract: Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking languages). Some open problems are also formulated.

DOI: 10.3233/FI-1996-253410

Journal: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 381-397, 1996