Institute of Information Science, Academia Sinica

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 k-synchronized if for every n-tuple x = (x1, . . . , xn) 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 = (x1, . . . , xn) 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 k-synchronized for a given k (for some k)? and (2) Given an n-tape automaton M, does there exist a k-synchronized automaton for a given k (for some k) M′ such that L(M′) = L(M)? We consider various classes of multitape automata. Our work is motivated by applications to reachability analyses and verification problems in string manipulating programs.