We propose a computational framework in which networks connecting nodes called ports are formed with fibers elongated by the extension and branching of their growing points, and various computations in networks (such as path formation, circuit generation, matching, etc.) are realized by propagation of states along fibers. Fibers and ports have states that are changed depending on the states of the neighboring fibers and ports. Since the framework features growing points that are elongated according to states of fibers, models in the framework are named growing point automata (GPA) after the Growing Point Language (GPL) proposed in the study of amorphous computing. In this chapter, we first give the simple version of growing point automata with an example of path formation between ports. We then refine this simple version by taking transmission of signals along fibers into account. Refined models are called signal-passing models. We show that there exists a weak bisimulation between the simple and signal-passing models of path formation.

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

Growing Point Automata

  • Masami Hagiya

摘要

We propose a computational framework in which networks connecting nodes called ports are formed with fibers elongated by the extension and branching of their growing points, and various computations in networks (such as path formation, circuit generation, matching, etc.) are realized by propagation of states along fibers. Fibers and ports have states that are changed depending on the states of the neighboring fibers and ports. Since the framework features growing points that are elongated according to states of fibers, models in the framework are named growing point automata (GPA) after the Growing Point Language (GPL) proposed in the study of amorphous computing. In this chapter, we first give the simple version of growing point automata with an example of path formation between ports. We then refine this simple version by taking transmission of signals along fibers into account. Refined models are called signal-passing models. We show that there exists a weak bisimulation between the simple and signal-passing models of path formation.