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...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2004
|
| Sorozat: | Acta cybernetica
16 No. 3 |
| Kulcsszavak: | Számítástechnika, Nyelvészet - számítógép alkalmazása |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12729 |
| Tartalmi kivonat: | 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. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 385-397 |
| ISSN: | 0324-721X |