Rewriting systems with limited distance forbidding context

Abstract

A random context production has a permitting and forbidding context. A symbol can be rewritten using such a production if all the permitting context symbols and no forbidding context symbol appear in the sentential string. In this paper we limit the effect of forbidding context symbols to be within a certain distance from the symbol to be rewritten. Outside this distance the forbidding context symbols do not influence the rewriting of a symbol. This restriction strictly increases the generating power of the rewriting system.

A further result of this paper is a “negative parallel” version of Penttonen's normal form.

Keywords:

• Parallel rewriting systems
• L-systems
• forbidding context

C.R.Categories:

• 5.23