TWO-DIMENSIONAL LANGUAGES AND CELLULAR AUTOMATA

被引：0
|
作者：
Dolzhenko, Egor [1 ]
Jonoska, Natasa [1 ]
机构：
[1] Univ S Florida, Dept Math & Stat, Tampa, FL 33620 USA
来源：
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2012年 / 23卷 / 01期
基金：
美国国家科学基金会;
关键词：
Cellular automata; two-dimensional languages; picture languages; factorial-local languages; traces; shadowing property; SFT traces;
D O I：
10.1142/S0129054112500037
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Space-time diagrams of a one-dimensional cellular automaton can be visualized as half-plane arrays of symbols. The set of rectangular blocks extracted from such arrays forms a two-dimensional (picture) language. We initiate a study of cellular automata through the associated two dimensional languages by investigating cellular automata whose two-dimensional languages are factorial-local. We show that these cellular automata have the same characterization as one-sided cellular automata with SFT traces.
引用
收藏
页码：185 / 206
页数：22
相关论文
共 50 条
  • [1] Entropy of two-dimensional permutative cellular automata
    Namiki, Takao
    2013 FIRST INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2013, : 510 - 514
  • [2] From One-dimensional to Two-dimensional Cellular Automata
    Dennunzio, Alberto
    FUNDAMENTA INFORMATICAE, 2012, 115 (01) : 87 - 105
  • [3] Two-dimensional cellular automata and deterministic on-line tessalation automata
    Terrier, V
    THEORETICAL COMPUTER SCIENCE, 2003, 301 (1-3) : 167 - 186
  • [4] Triangular Automata: The 256 Elementary Cellular Automata of the Two-Dimensional Plane
    Cousin, Paul
    COMPLEX SYSTEMS, 2024, 33 (03): : 253 - 275
  • [5] Encryption using two-dimensional cellular automata with applications
    Srebrny, M
    Such, P
    ARTIFICIAL INTELLIGENCE AND SECURITY IN COMPUTING SYSTEMS, 2003, 752 : 203 - 215
  • [6] The reversibility problem for a family of two-dimensional cellular automata
    Koroglu, Mehmet Emin
    Siap, Irfan
    Akin, Hasan
    TURKISH JOURNAL OF MATHEMATICS, 2016, 40 (03) : 665 - 678
  • [7] Text compression using two-dimensional cellular automata
    Khan, AR
    Choudhury, PP
    Dihidar, K
    Verma, R
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1999, 37 (06) : 115 - 127
  • [8] Leader election on two-dimensional periodic cellular automata
    Bacquey, Nicolas
    THEORETICAL COMPUTER SCIENCE, 2017, 659 : 36 - 52
  • [9] Construction of μ-Limit Sets of Two-dimensional Cellular Automata
    Delacourt, Martin
    de Menibus, Benjamin Hellouin
    32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015), 2015, 30 : 262 - 274
  • [10] On behavior of two-dimensional cellular automata with an exceptional rule
    Zhai, Ying
    Yi, Zhong
    Deng, Pei-min
    INFORMATION SCIENCES, 2009, 179 (05) : 613 - 622
12345