Buchholz, ThomasThomasBuchholzKlein, AndreasAndreasKleinKutrib, MartinMartinKutrib2022-09-121998-07-082022-09-121998http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-269https://jlupub.ub.uni-giessen.de/handle/jlupub/7564http://dx.doi.org/10.22029/jlupub-6998One­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.enIn Copyrightddc:004