2-TESTABILITY AND RELABELINGS PRODUCE EVERYTHING

Authors
ILIE L SALOMAA A
Citation
L. Ilie et A. Salomaa, 2-TESTABILITY AND RELABELINGS PRODUCE EVERYTHING, Journal of computer and system sciences (Print), 56(3), 1998, pp. 253-262
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Hardware & Architecture","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences (Print) → ACNP
ISSN journal
00220000
Volume
56
Issue
3
Year of publication
1998
Pages
253 - 262
Database
ISI
SICI code
0022-0000(1998)56:3<253:2ARPE>2.0.ZU;2-C
Abstract
We show that grammar systems with communication by command and with ex tremely simple rewriting rules (in fact, only relabelings are needed) are able to generate all recursively enumerable languages. The result settles several open problems in the area of grammar systems. We also present the result in a general framework, without referring to gramma r systems, obtaining a characterization of recursively enumerable lang uages from a new point of view. (C) 1998 Academic Press.