ω-P Automata with Communication Rules

摘要

We introduce ω-P automata based on the model of P systems with membrane channels (see [8]) using only communication rules. We show that ω-P automata with only two membranes can simulate the computational power of usual (non-deterministic) ω-Turing machines. A very restricted variant of ω-P automata allows for the simulation of ω-finite automata in only one membrane.