Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems

M. Sakthi Balan
(Infosys)

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.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 59–68.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.5 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org