Publication details
Simple restriction in context-free rewriting
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Computer and System Sciences |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.jcss.2010.04.001 |
| Field | Informatics |
| Keywords | Formal languages; Context-free grammar; Rewriting system; Derivation restriction; Generative power |
| Description | Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with erasing productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or - to each nonterminal. A production is applicable if it is applicable as a context-free production and if the symbol assigned to the left-hand side of the production is coupled with +, then this symbol has to appear in the sentential form, while if coupled with -, it must not appear in the sentential form. This restriction is simpler than most of the other restrictions, since the context conditions are assigned to nonterminals, not to productions, and their type is the simplest possible -- a nonterminal. |