I'm trying to figure out this question:
Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice versa) that works in polynomial space.
Prove that we can simulate that machine by a deterministic machine also working in polynomial space.
Could some give me a hint how to approach this problem?
I was recently thinking about similar problem. After literature reserch I found out that
for every $S(n)\geq \log(n)$ hierarchy of $k-altBounded-ASpace((S(n)))$ colapses to $1-altBounded-ASpace((S(n)))=NSpace(S(n))$. I found it in article "Viliam Geffert A Hierarchy that does not collapse: alternations in low space". to convert to PSpace you can use Savitch's theorem.
But I can show you scatch of my simulation. (for simplicity let's assume that $S(n) \geq n$)
1) due to Immerman-Szelepczényi theorem: $USPACE(S(n))= NSPACE(S(n))$, where U-TM is using only universal branching.
2) let $L_{M,Q}=\{C| C$ is configuration M, subtree under configuration $C$ is accepting and consist only from $Q$-konfigurations}. Where $Q \in \{\forall,\exists\}$ Then $L_{M,Q} \in xSPACE(S(n))$, where $x \in\{N,U\}$ is coresponding to $Q$. We only need to simulate original ATM from $C$. So also $L_{M,Q} \in \overline{x}SPACE(S(n))$ where $\overline{x}$ is oposite to $x$.(due to first statment)
3) We will simulate S(n) space bounded ATM $M$ by onother ATM $N$ using k-1 alternations. During first k-1 alternations $N$ is simulationg $M$. Then in configucation $C$, which $C$ reqires k-th alternation we will stop simulation and write $C$ on working tape. Then we will run machine $X$ for $L_{M,Q}$ on $C$. This machine $X$ has same type as our current alternation, so we don't have to make k-th alternation. $X$ is working in $S(n)$ space.
So we saved one alternation. Ssing this simulation k-times we will get NTM. On NTM we will use Savitch's theorem. so
$k-altBounded-ASpace((S(n))) = 1-altBounded-ASpace((S(n))) = NSPACE(S(n)) = DSPACE(S(n)^2)$
I hope that hepls:) And sorry for my english.