• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Computational Power of Two Stacks with Restricted Communication

Juhani Karhumäki, Michal Kunc, Alexander Okhotin, Computational Power of Two Stacks with Restricted Communication. TUCS Technical Reports 744, Turku Centre for Computer Science, 2008.

Abstract:

Rewriting systems working on words with a center marker are considered.
The derivation is done by erasing a prefix or a suffix and
then adding a prefix or a suffix.
This models a communication of two stacks
according to a fixed protocol
defined by the choice of rewriting rules.
The paper systematically considers different cases of these systems
and determines their expressive power.
Several cases are identified where very restricted communication
surprisingly yields computational universality.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tKaKuOk06a,
  title = {Computational Power of Two Stacks with Restricted Communication},
  author = {Karhumäki, Juhani and Kunc, Michal and Okhotin, Alexander},
  number = {744},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {Word rewriting, string rewriting, Post systems, multi-pushdown machines, communication, universality},
  ISBN = {952-12-1687-5},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication