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ő: | Meduna Alexander |
---|---|
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 |
Hasonló tételek
-
Descriptional complexity of multi-continuous grammars
Szerző: Meduna Alexander
Megjelent: (1998) -
Various communications in PC grammar systems
Szerző: Vaszil György
Megjelent: (1997) -
Economical transformations of phrase-structure grammars to scattered context grammars
Szerző: Meduna Alexander
Megjelent: (1998) -
Two transformations on attribute grammars improving the complexity of their evaluation
Szerző: Gombás Éva, et al.
Megjelent: (1989) -
Two power-decreasing derivation restrictions in generalized scattered context grammars
Szerző: Masopust Tomáš, et al.
Megjelent: (2008)