We consider parallel communicating pushdown automata systems (PCPA)
and define a property called known communication for it. We use
this property to prove that the power of a variant of PCPA, called
returning centralized parallel communicating pushdown automata
(RCPCPA), is equivalent to that of multi-head pushdown automata. The
above result presents a new sub-class of returning parallel
communicating pushdown automata systems (RPCPA) called
simple-RPCPA and we show that it can be written as a finite
intersection of multi-head pushdown automata systems. |