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 条

[1] On the number of components for some parallel communicating grammar systems
Dassow, Juergen
Truthe, Bianca
THEORETICAL COMPUTER SCIENCE, 2007, 387 (02) : 136 - 146
[2] The Conversion between Left-linear Grammar and Right-linear Grammar in Finite Automata
Wang, R. H.
PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND INFORMATION TECHNOLOGY (SEIT2015), 2016, : 293 - 296
[3] Confluence of shallow right-linear rewrite systems
Godoy, G
Tiwari, A
COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2005, 3634 : 541 - 556
[4] ON CENTRALIZED PARALLEL COMMUNICATING GRAMMAR SYSTEMS WITH CONTEXT-SENSITIVE COMPONENTS
Otto, Friedrich
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2013, 24 (04) : 453 - 471
[5] On metalinear parallel communicating grammar systems
Malcher, Andreas
Sunckel, Bettina
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2007, 18 (06) : 1313 - 1322
[6] ON THE SYNCHRONIZATION IN PARALLEL COMMUNICATING GRAMMAR SYSTEMS
PAUN, G
ACTA INFORMATICA, 1993, 30 (04) : 351 - 367
[7] Probabilistic parallel communicating grammar systems
Arthi, K
Krithivasan, K
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2002, 79 (01) : 1 - 26
[8] Variants of parallel communicating grammar systems
Mihalache, V
MATHEMATICAL AND COMPUTATIONAL ANALYSIS OF NATURAL LANGUAGE, 1998, 45 : 83 - 93
[9] Learning Subclasses of Parallel Communicating Grammar Systems
Kumaar, Sindhu J.
Abisha, P. J.
Thomas, D. G.
GRAMMATICAL INFERENCE: THEORETICAL RESULTS AND APPLICATIONS, ICGI 2010, 2010, 6339 : 301 - 304
[10] Parallel communicating grammar systems with separated alphabets
Mihalache, Valeria
Acta Cybernetica, 1996, 12 (04): : 397 - 409

← 1 2 3 4 5 →