On the number of nodes in universal networks of evolutionary processors

被引：0
|
作者：
Artiom Alhazov
Carlos Martín-Vide
Yurii Rogozhin
机构：
[1] Academy of Sciences of Moldova,Institute of Mathematics and Computer Science
[2] Rovira i Virgili University,Research Group on Mathematical Linguistics
来源：
Acta Informatica | 2006年 / 43卷
关键词：
Regular Language; Mathematical Linguistics; Hybrid Network; Grammar System; Connection Machine;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.
引用
收藏
页码：331 / 339
页数：8
相关论文
共 50 条
  • [41] Accepting Networks of Evolutionary Processors with Subregular Filters
    Florin Manea
    Bianca Truthe
    Theory of Computing Systems, 2014, 55 : 84 - 109
  • [42] Networks of evolutionary processors: wheel graph simulation
    José Ángel Sánchez Martín
    Victor Mitrana
    Mihaela Păun
    Journal of Membrane Computing, 2023, 5 : 221 - 237
  • [43] NETWORKS OF EVOLUTIONARY PROCESSORS AS NATURAL LANGUAGE PARSERS
    Bel-Enguix, Gemma
    Dolores Jimenez-Lopez, M.
    Merca, Robert
    Perekrestenko, Alexander
    ICAART 2009: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, 2009, : 619 - +
  • [44] Target Based Accepting Networks of Evolutionary Processors
    Truthe, Bianca
    FUNDAMENTA INFORMATICAE, 2010, 104 (1-2) : 161 - 183
  • [45] Networks of Polarized Evolutionary Processors as Problem Solvers
    Pablo Alarcon, Pedro
    Arroyo, Fernando
    Mitrana, Victor
    ADVANCES IN KNOWLEDGE-BASED AND INTELLIGENT INFORMATION AND ENGINEERING SYSTEMS, 2012, 243 : 807 - 815
  • [46] Towards Probabilistic Networks of Polarized Evolutionary Processors
    Arroyo, Fernando
    Gomez-Canaval, Sandra
    Mitrana, Victor
    Paun, Mihaela
    Ramon Sanchez-Couso, Jose
    PROCEEDINGS 2018 INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING & SIMULATION (HPCS), 2018, : 764 - 771
  • [47] Accepting networks of evolutionary processors with filtered connections
    Dragoi, Cezara
    Manea, Florin
    Mitrana, Victor
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2007, 13 (11) : 1598 - 1614
  • [48] Networks of Evolutionary Picture Processors with Filtered Connections
    Bottoni, Paolo
    Labella, Anna
    Manea, Florin
    Mitrana, Victor
    Sempere, Jose L.
    UNCONVENTIONAL COMPUTATION, PROCEEDINGS, 2009, 5715 : 70 - +
  • [49] On the computational power of networks of polarized evolutionary processors
    Arroyo, Fernando
    Canaval, Sandra Gomez
    Mitrana, Victor
    Popescu, Stefan
    INFORMATION AND COMPUTATION, 2017, 253 : 371 - 380
  • [50] Complete Obligatory Hybrid Networks of Evolutionary Processors
    Alhazov, Artiom
    Bel-Enguix, Gemma
    Krassovitskiy, Alexander
    Rogozhin, Yurii
    HIGHLIGHTS IN PRACTICAL APPLICATIONS OF AGENTS AND MULTIAGENT SYSTEMS, 2011, 89 : 275 - 282
12345