Weak Synchronization and Synchronizability of Multi-Tape Pushdown Automata and Turing Machines
Óscar H. Ibarra, Nicholas Trân · Universitätsbibliothek Gießen · 2014
Given an $n$-tape automaton $M$ with a one-way read-only head per tape which is delimited by an end marker $\$$ and a nonnegative integer $k$, we say that $M$ is weakly $k$-synchronized if for every $n$-tuple $x = (x_1, \dots, x_n)$ that is accepted, there is an accepting computation on $x$ such that no pair of input heads, neither of which is on $\$$, are more than $k$ tape cells apart at any time during the computation. When a head reaches the marker, it can no longer move. As usual, an $n$-tuple $x = (x_1, \ldots, x_n)$ is accepted if $M$ eventually reaches the configuration where all $n$ heads are on $\$$ in an accepting state. We look at the following problems: (1) Given an $n$-tape automaton $M$, is it weakly $k$-synchronized for a given $k$ (for some $k$)? and (2) Given an $n$-tape automaton $M$ and $k$ (for some $k$), does there exist a weakly $k$-synchronized automaton $M'$ such that $L(M') = L(M)$? In earlier papers, we studied the case of multi-tape finite automata (these automata accept rational relations). Here, we investigate the case of multi-tape pushdown automata (NPDAs), multi-tape Turing machines, and other multi-tape models. The results that we obtain contrast those of the earlier results and involve some rather intricate constructions.