This paper aims to provide a systematic and coherent overview of advances in computational modeling within the framework of grammar systems theory. In grammar systems theory, grammars can be interpreted as agents, while the generated language describes the behavior of the system. The agents collectively shape the complexity and emergent properties of the system, which go beyond the scope of individual dynamics. Such emergent phenomena, considered as computational results, require an understanding of the limitations of these computations. We consider Internet crawlers searching for novel information on the World Wide Web, network clustering, peer-to-peer networks, and string assembly in distributed environments. First, we review the results concerning the computational capabilities of the devised constructs, which can be viewed as language-generating devices. Special emphasis is placed on certain variants, namely eco-grammar systems and networks of language processors, including networks of evolutionary processors. In addition, this paper shows how the NP-complete Hamiltonian Path Problem can be solved efficiently in linear time using networks of evolutionary processors. Finally, prospective avenues for future research are proposed to inspire further exploration in this area.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Unconventional Computational Models for Distributed Networks: Results and Perspectives

  • Katalin Anna Lazár

摘要

This paper aims to provide a systematic and coherent overview of advances in computational modeling within the framework of grammar systems theory. In grammar systems theory, grammars can be interpreted as agents, while the generated language describes the behavior of the system. The agents collectively shape the complexity and emergent properties of the system, which go beyond the scope of individual dynamics. Such emergent phenomena, considered as computational results, require an understanding of the limitations of these computations. We consider Internet crawlers searching for novel information on the World Wide Web, network clustering, peer-to-peer networks, and string assembly in distributed environments. First, we review the results concerning the computational capabilities of the devised constructs, which can be viewed as language-generating devices. Special emphasis is placed on certain variants, namely eco-grammar systems and networks of language processors, including networks of evolutionary processors. In addition, this paper shows how the NP-complete Hamiltonian Path Problem can be solved efficiently in linear time using networks of evolutionary processors. Finally, prospective avenues for future research are proposed to inspire further exploration in this area.