Computational power of two stacks with restricted communication

DOI10.1016/j.ic.2009.07.001zbMath1209.68288OpenAlexW1993721751MaRDI QIDQ1959441

Alexander Okhotin, Michal Kunc, Juhani Karhumäki

Publication date: 7 October 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.07.001

zbMATH Keywords

communicationuniversalitystring rewritingmulti-pushdown machinespost systemsword rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Circular Post Machines and P Systems with Exo-insertion and Deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deleting string rewriting systems preserve regularity
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-bounded multipushdown machines
• The power of commuting with finite sets of words
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Regular canonical systems
• Counter machines and counter languages
• Formal Reductions of the General Combinatorial Decision Problem