Two-way metalinear PC grammar systems and their descriptional complexity
Besides a derivation step and a communication step, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left-hand side. This paper proves that every non-unary recursively enumerable language is defined by a centralized...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
2004
|
| Series: | Acta cybernetica
16 No. 3 |
| Kulcsszavak: | Számítástechnika, Nyelvészet - számítógép alkalmazása |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12729 |
| Summary: | Besides a derivation step and a communication step, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left-hand side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, ┌, with two metalinear components in a very economical way. Indeed, ┌'s master has only three nonterminals and one communication production; furthermore, it produces all sentential forms with no more than two occurrences of nonterminals. In addition, during every computation, ┌ makes a single communication step. Some variants of two-way PC grammar systems are discussed in the conclusion of this paper. |
|---|---|
| Physical Description: | 385-397 |
| ISSN: | 0324-721X |