Synchronization and Synchronizability of Multitape Automata
- 講者Oscar H. Ibarra 教授 (Department of Computer Science, UCSB)
邀請人:陳郁方 - 時間2012-08-10 (Fri.) 10:30 ~ 12:00
- 地點本所新館一樓101演講廳
摘要
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.