Automata and processes on multisets of communicating objects

作者：Yang Linmin^*; Wang Yong; Dang Zhe

来源：Natural Computing, 2010, 9(4): 865-887.

DOI：10.1007/s11047-010-9206-0

• P system
• Service automata
• Presburger reachability
• Network processes

Inspired by P systems initiated by Gheorghe Nun, we study a computation model over a multiset of communicating objects. The objects in our model are instances of finite automata. They interact with each other by firing external transitions between two objects. Our model, called a service automaton, is intended to specify, at a high level, a service provided on top of network devices abstracted as communicating objects. We formalize the concept of processes, running over a multiset of objects, of a service automaton and study the computing power of both single-process and multiprocess service automata. In particular, in the multiprocess case, regular maximal parallelism is defined for inter-process synchronization. It turns out that single-process service automata are equivalent to vector addition systems and hence can define nonregular processes. Among other results, we also show that Presburger reachability problem for single-process service automata is decidable, while it becomes undecidable in the multiprocess case. Hence, multiprocess service automata can not be effectively simulated by vector addition systems.

• 出版日期2010-12
• 单位Google Inc, Mountain View, CA