JUCS - Journal of Universal Computer Science 6(12): 1165-1184, doi: 10.3217/jucs-006-12-1165
Grammar Systems with Negated Conditions in their Cooperation Protocols
expand article infoHenning Bordihn‡, Markus Holzer§
‡ Fakultät für Informatik, Otto-von-Guericke-University, Magdeburg, Germany§ Departement d'I.R.O., Université de Montreal, Montreal, Canada

Corresponding author: Henning Bordihn ( bordihn@iws.cs.uni-magdeburg.de )

© Henning Bordihn, Markus Holzer.
This article is freely available under the J.UCS Open Content License.
Citation: Bordihn H, Holzer M (2000) Grammar Systems with Negated Conditions in their Cooperation Protocols. JUCS - Journal of Universal Computer Science 6(12): 1165-1184. https://doi.org/10.3217/jucs-006-12-1165
Open Access
Abstract
The investigation on Boolean operations on the stop conditions of derivation modes for cooperating distributed grammar systems is continued by considering the logical negation of such conditions. The focus is on the negation of the t-mode of derivation, where such non-t-components may stop rewriting only if they still have a production applicable to the current sentential form. In many cases, hybrid cooperating distributed grammar systems with non-t-components turn out to give new characterizations of the class of programmed context-free languages or recurrent programmed context-free languages, where the latter class coincides with the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.
Keywords
formal languages, grammar systems, programmed grammars, regulated rewriting