  In (Csuhaj-Varju et. al. 2000) Parallel Communicating Systems of Pushdown
Automata (PCPA) were introduced and shown to be able to simulate
nondeterministic one-way multi-head pushdown automata in returning mode, even
if communication is restricted to be one-way having a single target component.
A simulation of such centralized PCPA by one-way multi-head pushdown automata
(Balan 2009) turned out to be incomplete (Otto 2012). Subsequently it was shown
that centralized returning PCPA are universal even if the number of components
is two (Petersen 2013) and thus are separated from one-way multi-head pushdown
automata. Another line of research modified the definition of PCPA such that
communication is asynchronous (Otto 2013). While the simulation of one-way
multi-head pushdown automata is still possible, now a converse construction
shows this model in returning mode to be equivalent to the one-way multi-head
pushdown automaton in a very precise sense. It was left open, whether
non-centralized returning PCPA of degree two are universal. In the first part
of the paper we show this to be the case. Then we turn our attention to Uniform
Distributed Pushdown Automata Systems (UDPAS). These systems of automata work
in turn on a single tape. We show that UPDAS accepting with empty stack do not
form a hierarchy depending on the number of components and that the membership
problem is complete in NP, answering two open problems from (Arroyo et. al.
2012).
