On the power of parallel communicating grammar systems with right-linear components

被引：4

作者：

Dumitrescu, S ^{[1
]}

Paun, G ^{[1
]}

机构：

[1] Romanian Acad, Inst Math, Bucharest 70700, Romania

来源：

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 1997年 / 31卷 / 04期

关键词：

D O I：

10.1051/ita/1997310403311

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We settle here two problems concerning the generative power of parallel communicating grammar systems with right-linear components: (1) each linear language can be generated by a non-centralized returning system, (2) the family of languages generated by centralized returning systems is incomparable with the family of languages generated by non-returning centralized systems. It is also proved that centralized returning systems with right-linear components are strictly more powerful than systems with regular rules in the restricted sense.

引用

页码：331 / 354

页数：24

共 50 条

[31] PARALLEL COMMUNICATING GRAMMAR SYSTEMS - THE CONTEXT-SENSITIVE CASE
PROCOPIUC, O
IONESCU, CM
TIPLEA, FL
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1993, 49 (3-4) : 145 - 156
[32] On the computational complexity of context-free parallel communicating grammar systems
Bruda, S
NEW TRENDS IN FORMAL LANGUAGES, 1997, 1218 : 256 - 266
[33] On the computational completeness of context-free parallel communicating grammar systems
Csuhaj-Varjú, E
Vaszil, G
THEORETICAL COMPUTER SCIENCE, 1999, 215 (1-2) : 349 - 358
[34] Right-linear finite path overlapping term rewriting systems effectively preserve recognizability
Takai, T
Kaji, Y
Seki, H
REWRITING TECHNIQUES AND APPLICATIONS, PROCEEDINGS, 2000, 1833 : 246 - 260
[35] GENERATION OF RIGHT-LINEAR GRAMMARS FROM REGULAR EXPRESSIONS
PATEL, AR
IEEE TRANSACTIONS ON COMPUTERS, 1971, C 20 (04) : 472 - &
[36] EFFICIENT EVALUATION OF RIGHT-LINEAR, LEFT-LINEAR, AND MULTILINEAR RULES
NAUGHTON, JF
RAMAKRISHNAN, R
SAGIV, Y
ULLMAN, JD
PROCEEDINGS OF THE 1989 ACM SIGMOD INTERNATIONAL CONFERENCE ON THE MANAGEMENT OF DATA, 1989, 18 : 235 - 242
[37] A proof theory of right-linear (ω-)grammars via cyclic proofs
Das, Anupam
De, Abhishek
PROCEEDINGS OF THE 39TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS 2024, 2024,
[38] Parallel communicating grammar systems with regular control and skeleton preserving FRR automata
Pardubska, Dana
Platek, Martin
Otto, Friedrich
THEORETICAL COMPUTER SCIENCE, 2011, 412 (4-5) : 458 - 477
[39] On context-free parallel communicating grammar systems:: synchronization, communication, and normal forms
Csuhaj-Varjú, E
Vaszil, G
THEORETICAL COMPUTER SCIENCE, 2001, 255 (1-2) : 511 - 538
[40] Remarks on context-free parallel communicating grammar systems generating crossed agreements
Truthe, Bianca
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2008, 19 (04) : 873 - 886

← 1 2 3 4 5 →