Token Deduplication for Hypergraphs

[maxitg]

The project goal

We do have some understanding of how token deduplication might work in systems where atoms have explicit names (i.e., multiset systems with no Module, Unique, or other randomly-generated symbols on right-hand sides of rules).

The case of hypergraphs, however, is considerably more complicated. In particular, it appears to not be possible to do token deduplication uniquely if one attempts to deduplicate states corresponding to isomorphic hypergraphs.

The goal of this project is to develop an approach for deduplication in this case.

• A research note describing the approach for token deduplication in hypergraph systems.
• If time permits, implementation of that approach for HypergraphSubstitutionSystem.

Motivations

Multihistories appear to have some resemblance to the path integral formalism of quantum mechanics. However, to complete the formalism, one needs to be able to merge paths (more precisely, subhistories), for which token deduplication is necessary. This project is a part of that effort. The other part (#645) is understanding how to define probabilities on multihistories.

External prerequisites

• Familiarity with path integrals.
• Proficiency in graph theory.
• Experience with C++ or Wolfram Language.

SetReplace prerequisites

• Understanding of token-event graphs.
• Understanding of HypergraphSubstitutionSystem.

Difficulty

I (@maxitg) am stuck on this problem myself at the moment, so it may well be rather difficult. Of course, I might also be missing something obvious.

Potential instructors

@maxitg

Existing work

• Research note describing local multiway systems and token-event graphs (called expression-event graphs in the note). There are some ideas on token deduplication in the end.
• Notebook describing a potential approach to deduplication. The probability theory will likely be based on graphs such as those generated by TimelessTEG from this notebook.

Required future SetReplace features

It would be useful to integrate TimelessTEG first, however, the algorithm for the HypergraphSubstitutionSystem might be completely different, so it's not strictly neccessary.