Multitape NFA: weak synchronization of the input heads

Given an n -tape nondeterministic finite automaton (NFA) M with a one-way read-only head per tape and a right end marker $ on each tape, and a nonnegative integer k , we say that M is weakly k -synchronized if for every n -tuple x =( x 1 , …, x n ) that is accepted, there is a computation on x such that at any time during the computation, no pair of input heads, neither of which is on $, are more than k cells apart. As usual, an n -tuple x =( x 1 , …, x n ) is accepted if M eventually reaches the configuration where all n heads are on $ in an accepting state. We show decidable and undecidable results concerning questions such as: (1) Given M , is it weakly k -synchronized for some k (resp., for a specified k ) and (2) Given M , is there a weakly k -synchronized M ′ for some k (resp., for a specified k ) such that L ( M ′)= L ( M )? Most of our results are the strongest possible in the sense that slight restrictions on the models make the undecidable problems decidable. A few questions remain open.