Some properties of space-bounded synchronized alternating Turing machines with universal states only (Q1184994)

Synchronized alternating Turing machines (SA) allow communication among the parallel processes during the computation. When some branch of a computation enters a synchronizing state with a synchronizing symbol, it stops and waits for the other branches to reach a synchronizing state with the same synchronizing symbol or stop. The paper investigates synchronized alternating Turing machines having only universal states (SU). It is shown that such machines can be simulated by universal alternating TMs, the price for synchronization is paid by an increase of the space complexity. If \(S(n)\) is a space-constructible function such that \(S(n)\geq\log n\), then \(SU-SPACE(S(n))=N-Space(S(n))\). It is also shown that if \(\lim S(n)/n=0\), then 1-way \(SA\)-machines with space bounded by \(S(n)\) are strictly more powerful then 1-way SU-machines working in the same space.