The Block Neighborhood

Details The Block Neighborhood The Block Neighborhood

2010-12-03

arxiv.org/abs/1012.1334v1

Computer Science

Discrete Mathematics

Journ\'ees Automates Cellulaires 2010, Turku : Finland (2010)

Scientific paper

We define the block neighborhood of a reversible CA, which is related both to its decomposition into a product of block permutations and to quantum computing. We give a purely combinatorial characterization of the block neighborhood, which helps in two ways. First, it makes the computation of the block neighborhood of a given CA relatively easy. Second, it allows us to derive upper bounds on the block neighborhood: for a single CA as function of the classical and inverse neighborhoods, and for the composition of several CAs. One consequence of that is a characterization of a class of "elementary" CAs that cannot be written as the composition of two simpler parts whose neighborhoods and inverse neighborhoods would be reduced by one half.

Affiliated with

Also associated with

No associations

Rating

The Block Neighborhood does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Block Neighborhood, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Block Neighborhood will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515749