On time computability of functions in one-way cellular automata

被引:34
作者
Buchholz, T [1 ]
Kutrib, M [1 ]
机构
[1] Univ Giessen, Inst Informat, D-35392 Giessen, Germany
关键词
D O I
10.1007/s002360050123
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The capability of one-way (space-bounded) cellular automata (OCA) to time-compute functions is investigated. That means given a constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C(OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time-computable and properties of C(OCA) are given. The time-computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.
引用
收藏
页码:329 / 352
页数:24
相关论文
共 16 条
[1]   AN 8-STATE MINIMAL TIME SOLUTION TO FIRING SQUAD SYNCHRONIZATION PROBLEM [J].
BALZER, R .
INFORMATION AND CONTROL, 1967, 10 (01) :22-&
[2]   Some relations between massively parallel arrays [J].
Buchholz, T ;
Kutrib, M .
PARALLEL COMPUTING, 1997, 23 (11) :1643-1662
[3]  
CHOFFRUT C, 1984, ACTA INFORM, V21, P393, DOI 10.1007/BF00264617
[4]   SYSTOLIC TRELLIS AUTOMATA - STABILITY, DECIDABILITY AND COMPLEXITY [J].
CULIK, K ;
GRUSKA, J ;
SALOMAA, A .
INFORMATION AND CONTROL, 1986, 71 (03) :218-230
[5]   ONE-WAY BOUNDED CELLULAR AUTOMATA [J].
DYER, CR .
INFORMATION AND CONTROL, 1980, 44 (03) :261-281
[6]   GENERATION OF PRIMES BY A 1-DIMENSIONAL REAL-TIME ITERATIVE ARRAY [J].
FISCHER, PC .
JOURNAL OF THE ACM, 1965, 12 (03) :388-&
[7]   SOME RESULTS CONCERNING LINEAR ITERATIVE (SYSTOLIC) ARRAYS [J].
IBARRA, OH ;
PALIS, MA ;
KIM, SM .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1985, 2 (02) :182-218
[8]   ON ONE-WAY CELLULAR ARRAYS [J].
IBARRA, OH ;
JIANG, T .
SIAM JOURNAL ON COMPUTING, 1987, 16 (06) :1135-1154
[9]  
KUTRIB M, 1996, DEV LANGUAGE THEORY, V2, P420
[10]  
KUTRIB M, 1998, IN PRESS THEORET COM