Paper Info
Title
Computations on nondeterministic cellular automata
Abstract
This work concerns the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We assume that the space complexity is the diameter of area in space involved in computation. It is proved that (1) every nondeterministic cellular automata (NCA) A of dimension r , computing a predicate P with time complexity T ( n ) and space complexity S ( n ) can be simulated by r -dimensional NCA with time and space complexity O ( T 1/( r +1) S r /( r +1) ) and by r +1 dimensional NCA with time and space complexity O ( T 1/2 + S ), where T and S are functions constructible in time, (2) for any predicate P and integer r >1 if A is a fastest r -dimensional NCA computing P with time complexity T ( n ) and space complexity S ( n ), then T = O ( S ), and (3) if T r , P is the time complexity of a fastest r -dimensional NCA computing predicate P then T r +1, P = O (( T r , P ) 1− r /( r +1) 2 ), T r +1, P = O (( T r , P ) 1+2/ r ).Similar problems for deterministic cellular automata (CA) are discussed.
Year
DOI
Venue
1999
10.1006/inco.1998.2741
Inf. Comput.
Keywords
Field
DocType
nondeterministic cellular automaton,time complexity,cellular automata,space complexity
Discrete mathematics,Direct method,Cellular automaton,Combinatorics,Nondeterministic algorithm,Spacetime,Time complexity,Mathematics,One-dimensional space,Computation
Journal
Volume
Issue
ISSN
148
2
Information and Computation
Citations 
PageRank 
References 
6
0.43
3
Authors
1
Name
Order
Citations
PageRank
Yuri Ozhigov192.84