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 条

[21] Limitations of Coverability Trees for Context-Free Parallel Communicating Grammar Systems and Why these Grammar Systems are not Linear Space
Bruda, Stefan D.
Wilkin, Mary Sarah Ruth
PARALLEL PROCESSING LETTERS, 2016, 26 (03)
[22] Right-linear half-monadic term rewrite systems
Vágvölgyi, S
THEORETICAL COMPUTER SCIENCE, 2003, 309 (1-3) : 195 - 211
[23] Persistence of Termination for Right-Linear Overlay Term Rewriting Systems
Iwami, Munehiro
PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, VOL 3, 2005, 3 : 94 - 97
[24] Parallel communicating grammar systems with incomplete information communication
Csuhaj-Varjú, E
Vaszil, G
DEVELOPMENTS IN LANGUAGE THEORY, 2002, 2295 : 359 - 368
[25] Parallel communicating grammar systems with incomplete information communication
Csuhaj-Varjú, Erzsébet
Vaszil, György
Grammars, 2002, 5 (03): : 153 - 176
[26] Properties of fuzzy right-linear languages
Su, Lan
Dianzi Keji Daxue Xuebao/Journal of University of Electronic Science and Technology of China, 1994, 23 (01):
[27] Termination of rewrite systems with shallow right-linear, collapsing, and right-ground rules
Godoy, G
Tiwari, A
AUTOMATED DEDUCTION - CADE-20, PROCEEDINGS, 2005, 3632 : 164 - 176
[28] Parallel communicating grammar systems with context-free components are Turing complete for any communication model
Wilkin, Mary Sarah Ruth
Bruda, Stefan D.
ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA, 2016, 8 (02) : 113 - 170
[29] SOME DECISION-PROBLEMS FOR PARALLEL COMMUNICATING GRAMMAR SYSTEMS
TIPLEA, FL
ENE, C
IONESCU, CM
PROCOPIUC, O
THEORETICAL COMPUTER SCIENCE, 1994, 134 (02) : 365 - 385
[30] On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata
Pardubska, Dana
Platek, Martin
Otto, Friedrich
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, 2009, 5457 : 660 - +

← 1 2 3 4 5 →