A Note on Pushdown Automata Systems

DOI10.1007/978-3-319-09704-6_30zbMATH Open1417.68089arXiv1310.0504OpenAlexW3105006843MaRDI QIDQ5496201FDOQ5496201

Authors: Holger Petersen 

Publication date: 7 August 2014

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Abstract: 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).

Full work available at URL: https://arxiv.org/abs/1310.0504

Recommendations

• scientific article; zbMATH DE number 2150277
• Notes on looping deterministic two-way pushdown automata
• A note on limited pushdown alphabets in stateless deterministic pushdown automata
• Algebraic systems and pushdown automata
• Algebraic systems and pushdown automata
• Equivalence of deterministic pushdown automata revisited
• Pushdown automata, multiset automata, and Petri nets
• scientific article; zbMATH DE number 3883637
• scientific article; zbMATH DE number 4047168
• Pushdown automata with bounded nondeterminism and bounded ambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (10)

• Serializing the parallelism in parallel communicating pushdown automata systems
• Title not available (Why is that?)
• Asynchronous PC systems of pushdown automata
• Asynchronous parallel communicating systems of pushdown automata
• Uniform distributed pushdown automata systems
• Centralized PC systems of pushdown automata versus multi-head pushdown automata
• Variations on pushdown machines (Detailed Abstract)
• The power of centralized PC systems of pushdown automata
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: A Note on Pushdown Automata Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496201)