A recursive padding technique on nondeterministic cellular automata

被引：0
|
作者：
Iwamoto, Chuzo [1 ]
Yoneda, Harumasa [1 ]
Morita, Kenichi [1 ]
Imai, Katsunobu [1 ]
机构：
[1] Hiroshima Univ, Grad Sch Engn, Higashihiroshima 7398527, Japan
来源：
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2008年 / E91A卷 / 09期
关键词：
cellular automata; computational complexity; hierarchy theorem;
D O I：
10.1093/ietfec/e91-a.9.2335
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t(2)(n) is a time-constructible function and t2(n) grows faster than t(1)(n + 1), then there exists a language which can be accepted by a t(2)(n)-time nondeterministic cellular automaton but not by any t(1)(n)-time nondeterministic cellular automaton.
引用
收藏
页码：2335 / 2340
页数：6
相关论文
共 50 条
  • [1] Nondeterministic Cellular Automata
    Di Lena, Pietro
    Margara, Luciano
    INFORMATION SCIENCES, 2014, 287 : 13 - 25
  • [2] Topological dynamics of Nondeterministic Cellular Automata
    Di Lena, Pietro
    Information and Computation, 2020, 274
  • [3] Nondeterministic and Stochastic Cellular Automata and Virus Dynamics
    Burkhead, E. G.
    Hawkins, J. M.
    JOURNAL OF CELLULAR AUTOMATA, 2018, 13 (1-2) : 103 - 119
  • [4] Image security system using recursive cellular automata substitution
    Chen, Rong-Jian
    Lai, Jui-Lin
    PATTERN RECOGNITION, 2007, 40 (05) : 1621 - 1631
  • [5] Extension of cellular automata via the introduction of an algorithm for the recursive estimation of neighbors
    Kayama, Yoshihiko
    ARTIFICIAL LIFE AND ROBOTICS, 2016, 21 (03) : 338 - 344
  • [6] Encryption Technique with Programmable Cellular Automata (ETPCA)
    Anghelescu, Petre
    Ionita, Silviu
    Sofron, Emil
    JOURNAL OF CELLULAR AUTOMATA, 2010, 5 (1-2) : 79 - 105
  • [7] Audio scrambling technique based on cellular automata
    Madain, Alia
    Abu Dalhoum, Abdel Latif
    Hiary, Hazem
    Ortega, Alfonso
    Alfonseca, Manuel
    MULTIMEDIA TOOLS AND APPLICATIONS, 2014, 71 (03) : 1803 - 1822
  • [8] On path equivalence of nondeterministic finite automata
    Tzeng, WG
    INFORMATION PROCESSING LETTERS, 1996, 58 (01) : 43 - 46
  • [9] Audio scrambling technique based on cellular automata
    Alia Madain
    Abdel Latif Abu Dalhoum
    Hazem Hiary
    Alfonso Ortega
    Manuel Alfonseca
    Multimedia Tools and Applications, 2014, 71 : 1803 - 1822
  • [10] Cellular automata-based recursive pseudoexhaustive test pattern generator
    Dasgupta, P
    Chattopadhyay, S
    Chaudhuri, PP
    Sengupta, I
    IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (02) : 177 - 185
12345