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

DOI10.1016/0304-3975(92)90346-HMaRDI QIDQ1184994zbMATH OpenFDO

Authors Anna Slobodová

Publication date 28 June 1992

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90346-H

zbMATH Keywords

alternating Turing machinessynchronization

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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.

Recommendations

• On space-bounded synchronized alternating Turing machines
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
• On communication-bounded synchronized alternating finite automata
• On the power of synchronization in parallel computations

Cites work

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
• Alternating on-line Turing machines with only universal states and small space bounds
• Alternation
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On the power of synchronization in parallel computations
• Tradeoffs for language recognition on alternating machines
• Two-dimensional alternating turing machines with only universal states

Cited in

(8)

• A communication hierarchy of parallel computations
• On space-bounded synchronized alternating Turing machines
• Communication for alternating machines
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• Four-dimensional synchronized alternating Turing machines
• ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
• The Communication Hierarchy of Time and Space Bounded Parallel Machines
• On the power of synchronization in parallel computations

This page was built for publication: Some properties of space-bounded synchronized alternating Turing machines with universal states only

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1184994)