Parallel Communicating One-Way Reversible Finite Automata System

In this paper, we discuss the computational power of parallel communicating finite automata system with one-way reversible finite automaton as components. We show that unlike the multi-head one-way reversible finite automata model (where we are still not sure whether it accepts all the regular languages) parallel communicating one-way reversible finite automata systems can accept all the regular languages. Moreover, for every multi-head one-way reversible finite automaton, there exists a parallel communicating one-way reversible finite automata system which accepts the same language. We also make an interesting observation that although the components of the system are reversible the system as a whole is not reversible. On the basis of which we conjecture that parallel communicating one-way reversible finite automata systems may accept languages not accepted by multi-head one-way reversible finite automata.