The Block Neighborhood
| Autor: | Arrighi, Pablo, Nesme, Vincent Fabrice |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: Journ\'ees Automates Cellulaires 2010, Turku : Finland (2010) |
| Databáze: | arXiv |
| Externí odkaz: |
|