Constructible functions in cellular automata and their applications to hierarchy results |
| |
Authors: | Chuzo Iwamoto Tomonobu Hatsuyama Kenichi Morita Katsunobu Imai |
| |
Affiliation: | Department of Industrial & Systems Engineering, Faculty of Engineering, Hiroshima University, 4-1 Kagami-Yama 1 chome, Higashi-Hiroshima, 739-8527 Japan |
| |
Abstract: | We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)?n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t1(n) and t2(n) are time constructible functions such that limn→∞ t1(n)/t2(n) = 0 and t1(n)n, then there is a language which can be recognized by a CA in t2(n) time but not by any CA in t1(n) time. |
| |
Keywords: | Cellular automata Time constructibility Complexity hierarchy |
本文献已被 ScienceDirect 等数据库收录! |
|