Question for #math and #ComputerScience folks: What search terms should I use to find papers related to transitioning graphs to other graphs. Kinda like graph cellular automata but more the basic operations. I want to think about code AST transforms but would like to learn about general purpose graph transforms first. Boosts appreciated.
@pbloem TY, the elementary graph edit operators described in that article are a great starting point for what I want to do. I could probably build up higher order operations on top of them. 🙇
@mauve Hmm, https://en.wikipedia.org/wiki/Graph_reduction_machine (which mentions the SKIM); also https://en.wikipedia.org/wiki/SKI_combinator_calculus
I don't know if there are examples of graph reduction that are _not_ generally associated with some sort of computational system.
Worth looking at some data-structures too. For example Splay Trees https://en.wikipedia.org/wiki/Splay_tree emply a zig and zag graph operator, which could clearly be expressed in some sort of more general graph reduction language (but isn't).
@drj These are excellent, ty. I think I should dig more into the sorts of ways folks work with combinatory logic, too.
@mauve There's a graph edit distance. That implicitly computes a transform between two graphs.
https://en.wikipedia.org/wiki/Graph_edit_distance
Might be a good starting point.