• 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. In: Proceedings of DMCS´04, TUCS General Publication, 27-39, 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. We also make some connections with finite automata.

BibTeX entry:

@INPROCEEDINGS{inpCzeizler04a,
  title = {On The Size of the Inverse Neighborhoods for One-Dimensional Reversible Cellular Automata},
  booktitle = {Proceedings of DMCS´04},
  author = {Czeizler, Eugen},
  number = {32},
  series = {TUCS General Publication},
  pages = {27-39},
  year = {2004},
}

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

Edit publication