Journal article

Publication year: 2008

Pages: 10-14

Journal: Information Processing Letters

Volume number: 108

Issue number: 1

ISSN: 0020-0190

eISSN: 1872-6119

DOI Link: https://doi.org/10.1016/j.ipl.2008.03.023

Publisher: Elsevier

Abstract: 
We investigate the generative power of cooperating distributed grammar systems with context-free rules working in the full-competence mode in combination with another derivation mode, combined sf-mode, for short. A combined sf-mode as, for example, (sf Lambda <= k) restricts the valid derivations such that both properties have to be satisfied. If erasing rules are allowed, then except for the (sf Lambda <= 1)-, (sf Lambda = 1)-, and (sf Lambda t)-modes, it is shown that the family of recursively enumerable languages is characterized. The former two exceptions characterize the family of linear context-free languages, while the latter mode describes the family of context-free languages. (c) 2008 Elsevier B.V. All rights reserved.

Harvard Citation style: Bordihn, H. and Holzer, M. (2008) A note on cooperating distributed grammar systems working in combined modes, Information Processing Letters, 108(1), pp. 10-14. https://doi.org/10.1016/j.ipl.2008.03.023

APA Citation style: Bordihn, H., & Holzer, M. (2008). A note on cooperating distributed grammar systems working in combined modes. Information Processing Letters. 108(1), 10-14. https://doi.org/10.1016/j.ipl.2008.03.023