TY - GEN
T1 - One guess one-way cellular arrays
A1 - Buchholz,Thomas
A1 - Klein,Andreas
A1 - Kutrib,Martin
Y1 - 1998/07/08
N2 - Oneway 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 speedup result that allows any lineartime computation to be spedup to realtime. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the realtime languages.
CY - Gießen
PB - Universitätsbibliothek
AD - Otto-Behaghel-Str. 8, 35394 Gießen
UR - http://geb.uni-giessen.de/geb/volltexte/1998/26
ER -