Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions

被引：1

作者：

Ma, Junchi ^{[1
]}

Wang, Chen ^{[1
]}

Chen, Weilin ^{[1
]}

Lin, Defu ^{[1
]}

Wang, Chao ^{[1
]}

机构：

[1] Nankai Univ, Coll Software, Tianjin 300350, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2024年 / 1012卷

关键词：

Cellular automata; Non-linear rules; Reversibility; Reflective boundary conditions; One-dimensional; PERIODIC BOUNDARY; MODELS;

D O I：

10.1016/j.tcs.2024.114732

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Reversibility is one of the most significant properties of cellular automata (CA). In this paper, we focus on the reversibility of one-dimensional finite CA under reflective boundary conditions (RBC). We present two algorithms for deciding the reversibility of one-dimensional CA under RBC. Both algorithms work for not only linear rules but also non-linear rules. The first algorithm is to determine what we call the "strict reversibility" of CA. The second algorithm is to compute what we call the "reversibility function" of CA. Reversibility functions are proved to be periodic. Based on the algorithms, we list some experiment results of one-dimensional CA under RBC and analyse some features of this family of CA.

引用

页数：11

共 31 条

[1] A cryptosystem based on elementary cellular automata [J].

Abdo, A. A. ;

Lian, Shiguo ;

Ismail, I. A. ;

Amin, M. ;

Diab, H. .

COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION, 2013, 18 (01) :136-147

[2] ON 1D REVERSIBLE CELLULAR AUTOMATA WITH REFLECTIVE BOUNDARY OVER THE PRIME FIELD OF ORDER p [J].

Akin, Hasan ;

Sah, Ferhat ;

Siap, Irfan .

INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 2012, 23 (01)

[3]

Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8

[4]

[Anonymous], 1963, Proc. Sympos. Appl. Math, DOI DOI 10.1090/PSAPM/014/9961

[5]

Bruckner L.K., 1979, Acta Cybern., V4, P259

[6] Resolution Scalable Image Coding With Reversible Cellular Automata [J].

Cappellari, Lorenzo ;

Milani, Simone ;

Cruz-Reyes, Carlos ;

Calvagno, Giancarlo .

IEEE TRANSACTIONS ON IMAGE PROCESSING, 2011, 20 (05) :1461-1468

[7]

Chaudhuri P.P., 1997, Additive Cellular Automata: Theory and Applications, V43

[8]

Cinkir Z, 2011, J STAT PHYS, V143, P807, DOI 10.1007/s10955-011-0202-2

[9] On the reversibility of 150 Wolfram cellular automata [J].

Del Rey, A. Martin ;

Rodriguez Sanchez, G. .

INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 2006, 17 (07) :975-983

[10] Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over Zp [J].

Du, Xinyu ;

Wang, Chao ;

Wang, Tianze ;

Gao, Zeyu .

INFORMATION SCIENCES, 2022, 594 :163-176

← 1 2 3 4 →