Centralized PC Systems of Pushdown Automata versus Multi-head Pushdown Automata

摘要

In returning mode centralized PCI systems of pushdown automata of degree n can simulate n-head pushdown automata (Csuhaj-Varju et. al. 2000). At DCFS 2009, Balan claimed that also the converse holds. Here we show that Balan's proof of this claim is not correct. Accordingly it is still open whether n-head pushdown automata and centralized PC systems of pushdown automata of degree n working in returning mode accept the same class of languages.