• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Size of the Inverse Neighborhoods for One-Dimensional Reversible Cellular Automata

Eugen Czeizler, On the Size of the Inverse Neighborhoods for One-Dimensional Reversible Cellular Automata. Theoretical Computer Science 325(2), 273–284, 2004.

Abstract:

In this paper we investigate the possible neighborhood size of the inverse automaton of some types of one-dimensional reversible cellular automata. Considering only the case when the local function is a size two map, we give a quadratic upper bound for the neighborhood size of the inverse automaton. We show that this bound can be lowered in some particular cases, and give an algorithm for computing these better bounds.

BibTeX entry:

@ARTICLE{jCzeizler04a,
  title = {On the Size of the Inverse Neighborhoods for One-Dimensional Reversible Cellular Automata},
  author = {Czeizler, Eugen},
  journal = {Theoretical Computer Science},
  volume = {325},
  number = {2},
  pages = {273–284},
  year = {2004},
  keywords = {Cellular automata; Reversability; Neighborhood; Welch index },
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication