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] Parallel recognition of rational languages on two-dimensional cellular automata
    Delorme, M
    Mazoyer, J
    THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) : 251 - 289
  • [2] TWO-DIMENSIONAL CELLULAR AUTOMATA
    PACKARD, NH
    WOLFRAM, S
    JOURNAL OF STATISTICAL PHYSICS, 1985, 38 (5-6) : 901 - 946
  • [3] Two-dimensional cellular automata and their neighborhoods
    Terrier, V
    THEORETICAL COMPUTER SCIENCE, 2004, 312 (2-3) : 203 - 222
  • [4] Two-dimensional cellular automata recognizer
    Terrier, V
    THEORETICAL COMPUTER SCIENCE, 1999, 218 (02) : 325 - 346
  • [5] Universality for two-dimensional critical cellular automata
    Bollobas, Bela
    Duminil-Copin, Hugo
    Morris, Robert
    Smith, Paul
    PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2023, 126 (02) : 620 - 703
  • [6] A Synchronization Problem in Two-Dimensional Cellular Automata
    Umeo, Hiroshi
    NATURAL COMPUTING, PROCEEDINGS, 2009, 1 : 222 - 237
  • [7] Hardware version for two-dimensional cellular automata
    Dascalu, M
    Franti, E
    Hascsi, Z
    CAS '97 PROCEEDINGS - 1997 INTERNATIONAL SEMICONDUCTOR CONFERENCE, 20TH EDITION, VOLS 1 AND 2, 1997, : 597 - 600
  • [8] Entropy of two-dimensional permutative cellular automata
    Namiki, Takao
    2013 FIRST INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2013, : 510 - 514
  • [9] Coexistence of Dynamics for Two-Dimensional Cellular Automata
    Severino, Ricardo
    Soares, Maria Joana
    Athayde, Maria Emilia
    COMPLEX SYSTEMS, 2016, 25 (01): : 1 - 21
  • [10] From One-dimensional to Two-dimensional Cellular Automata
    Dennunzio, Alberto
    FUNDAMENTA INFORMATICAE, 2012, 115 (01) : 87 - 105
12345