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 |
| LEADER | 01527nab a2200217 i 4500 | ||
|---|---|---|---|
| 001 | acta12729 | ||
| 005 | 20220615102025.0 | ||
| 008 | 161015s2004 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Meduna Alexander | |
| 245 | 1 | 0 | |a Two-way metalinear PC grammar systems and their descriptional complexity |h [elektronikus dokumentum] / |c Meduna Alexander |
| 260 | |c 2004 | ||
| 300 | |a 385-397 | ||
| 490 | 0 | |a Acta cybernetica |v 16 No. 3 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Nyelvészet - számítógép alkalmazása | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12729/1/Meduna_2004_ActaCybernetica.pdf |z Dokumentum-elérés |