中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

Synchronization and Synchronizability of Multitape Automata

:::

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.