Token Deduplication

[maxitg]

The problem

One difference between multihistories as implemented in SetReplace and the MultiwaySystem is that MultiwaySystem identifies isomorphic states and merges them into one in properties such as "StatesList". We need to be able to do that here as well.

Discussion

A naive approach would be to perform isomorphism tests on entire states, however, that is not practical for even moderately large states. The better solution may be to perform an isomorphism locally.

As an example, consider a set of expressions that is matched to two different events thus producing two local branches. We can evolve these branches for some time, and then notice that the states (set of edges) they generated after some number of steps are identical up to the renaming of new atoms created during that evolution. In this case, we can identify expressions that appear in these states. This would be similar to what the MultiwaySystem does with identifying complete states, but for sub-evolution instead of entire evolutions.

It is also interesting to think about how it relates to caching parts of evolution, and what happens if isomorphic sets of expressions appear in different parts of the evolution.

Goals

At the very least, we should be able to reproduce the "StatesList" of the MultiwaySystem with identified isomorphic states. We should also have an option to specify the max number of steps to which such identification should be attempted.

[maxitg]

The situation is, in fact, weirder than I originally thought. In particular, if one demands that the deduplication both allows one to reconstruct the duplicated token-event graph and is unique, then it necessarily introduces cycles in the TEG. Even weirder is that uniqueness requires the deduplication of even spacelike expressions.

Here are some notes on the deduplication in the case where all atoms are explicitly named (e.g., there is no Module on the right-hand side of the rules):

TokenDeduplication.nb.zip