In this paper, we investigate how to initialise cellular automata implemented in the hyperbolic plane. We generalise a technique which was indicated in to the case of any rectangular regular grid of the hyperbolic plane. This allows us to construct the initial configuration of any cellular automaton belonging to a rather large class of problems.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.