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 :
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 |
Hasonló tételek
-
On monotone languages and their characterization by regular expressions
Szerző: Gyurica György
Megjelent: (2007) -
On nilpotent languages and their characterization by regular expressions
Szerző: Gyurica György
Megjelent: (2009) -
Regular grammar model for protocol testing [abstract] /
Szerző: Rotter Csaba V.
Megjelent: (1998) -
Linear regular languages part I. /
Szerző: Herman Gábor T.
Megjelent: (1969) -
Regularizing context-free languages by AFL operations concatenation and Kleene closure /
Szerző: Dassow Jürgen, et al.
Megjelent: (1992)