Buchholz, ThomasThomasBuchholzKlein, AndreasAndreasKleinKutrib, MartinMartinKutrib2022-09-121999-08-182022-09-121998http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-1438https://jlupub.ub.uni-giessen.de/handle/jlupub/7559http://dx.doi.org/10.22029/jlupub-6993Oneway and twoway cellular language acceptors with restricted non determinism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to realtime, lineartime and unrestrictedtime computations. A speedup result that allows any lineartime computation to be spedup to realtime is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and [Epsilon]free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.enIn Copyrightddc:004On interacting automata with limited nondeterminism