One guess one-way cellular arrays

One-way cellular automata with restricted nondeterminism are investigated. The number of allowed nondeterministic state transitions is limited to a constant. It is shown that a limit to exactly one step does not decrease the language accepting capabilities. We prove a speed-up result that allows any linear-time computation to be sped-up to real-time. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the real-time languages. (orig.)SIGLEAvailable from TIB Hannover: RO 9119(9801) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman