This is a short review of the following paper: http://www.javakade.nl/research/pdf/tragr-termgraph-2022-long-revised.pdf

The Trace Graph (tragr)

Tragrs (pronounced as trackers) are similar to token event graphs and single-way causal graphs with causal edges for a single path of the underlying multiway string rewriting system. But they have some additional details:
◼
  • only tokens (characters) of the initial and final strings are shown
    • ◼
  • there are additional juxtaposition edges between tokens making up an initial and final string
    • ◼
  • there are two explicit empty string tokens
    • ◼
  • events are colored and labeled by the string rewriting rule
    • ◼
  • causal edges are transitively reduced based on what token is involved
    • ◼
  • graph planarity (seems like it always holds, which is not immediately obvious, but the paper requires it to be the case by definition)
    • There is a notion of a Multistep, a generalisation of everything from a single updating event to a generational event, a parallel composition of space-like separated events.
    There is a bijection between these tragrs and greedy multistep reductions on string rewriting paths (proof terms), which says that one can go from a reduced string proof to tragr and back uniquely. Topological Multi-sorting is a name the paper dubs a way to read back a proof term from a tragr.
    Evolution graph of a multiway system have annotated evolution edges, from which all necessary information can be extracted to construct a Trace Graph for a given path:
    In[]:=
    PacletInstall["https://wolfr.am/Multicomputation.paclet",ForceVersionInstall->True]​​<<Wolfram`Multicomputation`
    Out[]=
    PacletObject
    Name: Wolfram/Multicomputation
    Version: 0.1.4
    
    In[]:=
    eg=MultiwaySystem[{"BB"->"A","AAB"->"BAAB"},"ABAAB"]["EvolutionGraph",7,AspectRatio->1/3]
    Out[]=
    In[]:=
    EdgeTags[eg][[;;3]]
    Out[]=
    Input{3,4,5},Output3,4,5,c.$151240,Rule2,Position{{3},{4},{5}},MatchPositions{{1}},MatchTypeRule,Step1,Input{2,3},Output{2},Rule1,Position{{2},{3}},MatchPositions{{1}},MatchTypeRule,Step2,Input4,5,c.$151240,Output4,5,c.$151240,c.$151871,Rule2,Position{{4},{5},{6}},MatchPositions{{1}},MatchTypeRule,Step2
    Example path from the paper:
    In[]:=
    source=ToLinkedHypergraph["ABAAB"];​​targets=Select[VertexList[eg],FromLinkedHypergraph[#,"String"]=="ABAABAAB"&];
    There are 24 paths in total, the 1st one (accidentally) corresponds to the example:
    In[]:=
    paths=Catenate@Map[EdgeList[Subgraph[eg,#]]&/@FindPath[eg,source,#,All,All]&,targets];
    In[]:=
    Length[paths]
    Out[]=
    24
    In[]:=
    Subgraph[eg,FindPath[eg,source,targets[[1]]]]
    Out[]=
    In[]:=
    HighlightGraph[Graph[eg,VertexSize->Medium,AspectRatio->1/3],Subgraph[eg,FindPath[eg,source,#]]&/@targets]
    Out[]=
    In[]:=
    Graph[%,GraphLayout->"SpringEmbedding",EdgeStyle->Arrowheads[Small],VertexShapeFunction->{Except[source|Alternatives@@targets]->Automatic},AspectRatio->1]
    Out[]=
    The function that constructs the tragr from the path:
    Compare its output to the one from the paper:
    All 24 Trace Graphs:
    All Trace Graphs are planar:
    Up-to permutation equivalence, which can be determined by comparing Trace Graphs, there are only 3 distinct paths:

    CITE THIS NOTEBOOK

    String rewriting trace graphs​
    by Nikolay Murzin​
    Wolfram Community, STAFF PICKS, May 8, 2024
    ​https://community.wolfram.com/groups/-/m/t/3172220