Space bounded probabilistic game automata

Results on the power of space-bounded probabilistic game automata are presented. Space-bounded analogs of Arthur-Merlin games and interactive proof systems are considered for bounded random game automata with complete and partial information. A consequence of the results is that any language recognizable in deterministic exponential time has an interactive proof that uses only logarithmic space. The power of games with simultaneous time and space bounds is also studied, and it is shown that any language in NTIME(t(n)) has an interactive proof that uses time polynomial in t(n) but space only logarithmic in t(n)