Grammar Systems with Negated Conditions in their Cooperation Protocols

Henning Bordihn (Fakultät für Informatik, Otto-von-Guericke-University, Germany)

Markus Holzer (Departement d'I.R.O., Université de Montreal, Canada)

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

Categories: F.4.2, F.4.3