Alternation with restrictions on looping

DOI10.1016/S0019-9958(85)80023-1zbMATH Open0611.68020MaRDI QIDQ3751006FDOQ3751006

John Michael Robson

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

Recommendations

• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• Alternating space is closed under complement and other simulations for sublogarithmic space
• scientific article; zbMATH DE number 3868618
• Some observations concerning alternating Turing machines using small space
• On reversal bounded alternating Turing machines

zbMATH Keywords

time complexitycomplexity of gamesAlternating Turing machines with restrictionsChinese version of Go

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Cited In (3)

• More on looping vs. repeating in dynamic logic
• Complexity of path-forming games
• Turing machines with access to history

This page was built for publication: Alternation with restrictions on looping

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