×

Communication P systems with channel states working in flat maximally parallel manner. (English) Zbl 1423.68171

Summary: Communication P systems with channel states (CC P systems, for short) are a class of distributed parallel computing models, where communication (symport/antiport) rules associated with channel states are executed in a sequential manner on membrane channels. In this work, communication P systems with channel states working in flat maximally parallel manner are considered and the computational power is investigated. Specifically, it is proved that communication P systems with channel states using symport rules of length two are Turing universal when having one membrane and any number of channel states, or two membranes and three channel states. Furthermore, membrane division isintroduced into communication P systems with channel states, communication P systems with channel states and membrane division (CCD P systems, for short) are proposed. We provide a uniform solution to the Hamiltonian path problem (HPP) by CCD P systems working in a flat maximally parallel manner.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI