Journal article
Automata and processes on multisets of communicating objects
Natural computing, Vol.9(4), pp.865-887
12/2010
Handle:
https://hdl.handle.net/2376/117128
Abstract
Inspired by P systems initiated by Gheorghe Pãun, 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.
Metrics
14 Record Views
Details
- Title
- Automata and processes on multisets of communicating objects
- Creators
- Linmin Yang - School of Electrical Engineering and Computer Science Washington State University Pullman WA 99164 USAYong Wang - Google Inc. Mountain View CA 94043 USAZhe Dang - School of Electrical Engineering and Computer Science Washington State University Pullman WA 99164 USA
- Publication Details
- Natural computing, Vol.9(4), pp.865-887
- Academic Unit
- Chemical Engineering and Bioengineering, School of; Electrical Engineering and Computer Science, School of
- Publisher
- Springer Netherlands; Dordrecht
- Identifiers
- 99900548075801842
- Language
- English
- Resource Type
- Journal article