Bijective cellular systems

Introduction

"Bijective cellular systems" is an umbrella term, intended to describe reversible cellular systems where global reversibility is attained by repeated use of a small, finite bijections which are applied locally.

Previously I identified that partitioning was a subset of a larger number of techniques for devloping reversible systems. I described a larger set that included partitioning that I called isometric.

Now it appears that isometric cellular systems are themselves a subset of a larger set - the set of bijective cellular systems. Isometric systems are not the only way to manufacture reversible cellular systems using small bijective maps.

The rest of this page is devoted to another method of producing reversible cellular systems using bijections - one which appears not to have been previously described or clearly identified. I call this technique "fencing".

It will be considered initially as an extension of partitioning. However it applies to all isometric systems.

It appears that two of the restrictions employed during partitioning can usefully be relaxed under certain conditions.

These restrictions are:

  • That the domain and co-domain are of the same size.

  • That partitions form disjoint sets.

The idea is a somewhat complex and difficult to explain - I'll do the best I can.

I assume knowledge of partitioning - if you are in need of such knowledge, I recommend you start here.

Diagrams

In the following diagrams, colours have the following significance:

These diagrams roughly outline the system I was thinking of when I came up with the idea.

Here is a (somewhat abstract) diagram of a conventional partitioning scheme:

I'll assume for the moment that regions not within the co-domains of partitions are preserved unchanged from generation to generation during evolution of the system.

First note that, the co-domain can be contracted - so that it forms a subset of the domain. One can imagine elements in the domain in the region covered by the co-domain to form a bijection with the latter - while elements outside the co-domain always remain unchanged. This can be done without any significant change to the reversibility of the resulting system.

Then note that it is no longer necessary for the domains to be disjoint - since they are effectively fixed - and consequently they may be allowed to overlap in the region that is effectively fixed:

Precise formulation

The idea can be more precisely formulated in such a way that it applies to all isometric schemes - not just as an extension of partitioning. Also the requitement that certain regions remain unchanged is not necessary - and can be eliminated.

The following critera are presented in the form of a recipe:

  1. A co-domain may lie within a region that is shared between two other domains iff its domain lies entirely within that region;
  2. Some specified subset of the domain always forms a bijection with the co-domain;
  3. Any two subsets of the type formed in 2) are disjoint and may not overlap;
  4. Any two co-domains are disjoint and may not overlap;
Discussion of these criteria follows.

Discussion

Criteria 1 contains the conditions under which co-domains may overlap intersections of other domains. It should be thought of applying to all regions that are shared between domains - even if they are shared between more domains than two.

Criteria 2 is an enlarged version of a similar rule for isometric schemes. It is primarily intended to ensure reversibility. The "specified subset" consists of some specified group of cells in the domain. They need to form a bijection with the co-domain regardless of what the rest of the domain consists of.

Criteria 3 supplements 2 - and is again intended to ensure reversibility by ensuring that no information can be lost.

Criteria 4 is common sense.

Notes

It appears to be a theorem that any systems created using this technique will be equivalent to some isometric system using finer granulations of time - i.e. a sysyem with N times as many time steps producing the same temporal evolution.

Seen in this light the technique appears to be a speed-up - a way of evaluating several iterations of an isomentric system concurrently under some circumstances.

Examples

As a simple example, one implication is that - in a partitioning cellular system - the domain of the partition transition function may be expanded to include whole entire neighbouring partitions (provided that there remains a bijection between the original domain and co-domain) while maintaining reversibility.

I imagine it will find application when people want to share information near the edges of partitions by making the partitions slightly overlap.

As a concrete example, the technique arose from the desire to create a reversible cellular system which seemed to demand its usage. You can see that system in action here - and it comes with diagrams of the neighbourhood it uses.

Summary

I have presented a new technique for creating reversible cellular systems. It was inspired by the existing techniques for making isometric cellular systems.

I hope others will find the technique useful.

Tim Tyler | tim@tt1.org | http://cell-auto.com/