On regular characterizations of languages by grammar systems

We show that grammar systems with communication by command and with extremely simple rewriting rules are able to generate all recursively enumerable languages. The result settles several open problems in the area of grammar systems.

Elmentve itt :
Bibliográfiai részletek
Szerzők: Ilie Lucian
Salomaa Arto
Dokumentumtípus: Cikk
Megjelent: 1996
Sorozat:Acta cybernetica 12 No. 4
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12571
Leíró adatok
Tartalmi kivonat:We show that grammar systems with communication by command and with extremely simple rewriting rules are able to generate all recursively enumerable languages. The result settles several open problems in the area of grammar systems.
Terjedelem/Fizikai jellemzők:411-425
ISSN:0324-721X