One guess one-way cellular arrays

Files in this item
Date
1998Author
Buchholz, Thomas
Klein, Andreas
Kutrib, Martin
Quotable link
http://dx.doi.org/10.22029/jlupub-6998Abstract
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.