What is the proper name for this "tersest path" problem in Infinite Craft?

Question

The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another way to describe this structure is as a directed hypergraph on $V$ where every edge is of the form $(\{v_a,v_b\}, \{v_c\})$.

I'm looking for information on how to find "tersest routes" in this structure. However, our definition of "route" is different from the usual mathematical definition of a "path" in a hypergraph. Let a "route" in Infinite Craft be a sequence $v_{1..n}$ such that for each $i$, either $v_i\in V_0$ or else $v_i = E(v_g, v_h)$ for some $g,h < i$.

For example, one route from $V_0= \{\text{Earth},\text{Wind},\text{Fire},\text{Water}\}$ to $\text{Sandwich}$ is six steps:

Wave = Water + Wind
Steam = Fire + Water
Plant = Earth + Water
Sand = Earth + Wave
Tea = Plant + Steam
Sandwich = Sand + Tea

But the tersest route from $V_0= \{\text{Earth},\text{Wind},\text{Fire},\text{Water}\}$ to $\text{Sandwich}$ is only five steps:

Wave = Water + Wind
Sand = Earth + Wave
Glass = Fire + Sand
Wine = Glass + Water
Sandwich = Sand + Wine

That route involves $\text{Wine}$, and gets to $\text{Wine}$ in the fourth step. But the tersest route from $V_0= \{\text{Earth},\text{Wind},\text{Fire},\text{Water}\}$ to $\text{Wine}$ is only three steps:

Plant = Earth + Water
Dandelion = Plant + Wind
Wine = Dandelion + Water

which isn't a subset of the tersest route to $\text{Sandwich}$!

This seems to make it really computationally expensive to compute tersest routes from $V_0$ to $v_\text{target}$. I'm looking for resources on this structure — what is it called (besides being a very specific shape of "hypergraph")? Has it been studied before? What is the proper name for this sort of "route" (or perhaps "support"), which is different from an ordinary linear "path"? Surely something like this must have been studied before (perhaps in the context of job-scheduling theory)? Are there any route-finding algorithms analogous to Dijkstra's algorithm or A* on this kind of structure?

Answer 1

The kind of hypergraphs you describe are a special case of hypergraphs where edges are ordered lists of nodes, e.g.

$e = ([ v_a, v_b ], [v_c])$

"Routes" in this kind of hypergraph correspond to morphisms of symmetric monoidal categories - here is a paper which describes this correspondence.

More precisely, what you have is essentially a presentation of a symmetric monoidal category:

• Some generating objects $\Sigma_0 = \{ \mathsf{Earth}, \mathsf{Wind}, ... \}$
• For each production rule like Wave = Water + Wind, a generating operation $f : Water \otimes Wind → Wave$

Your category then has objects $\Sigma_0$ plus their tensor products (e.g., $\mathsf{Earth} \otimes \mathsf{Wind} \otimes \ldots$). Morphisms in this category correspond to your "routes"; routes go between a starting list of "resources" to a resulting list of resources.

There is one piece missing; we require each $f : A \otimes B \to C$ to be commutative, so we actually have a symmetric monoidal theory with an equation $\sigma ; f = f$ for each operation $f$.

There is some work on studying "route-finding" algorithms in this context, but I'm not intimately familiar with it. Here are some pointers:

• A Categorical Representation Language and Computational System for Knowledge-Based Planning
• Open Algebraic Path problem
• Structured Decompositions: Structural and Algorithmic Compositionality
• Monoidal Width
• String Diagrams for Assembly Planning

Answer 2

I am embarrassed not to have recognized this sooner, but a 'canonical' structure that models Infinite Craft is the Commutative Magma — definitionally, a set $S$ with a binary operation $\oplus$ that is closed ($s\oplus t$ is defined and is $\in S$ for all $s,t\in S$) and commutative. Unfortunately, the level of generality at play here means that this is not necessarily helpful for practical considerations, but those are the magic words I'd start with to try and find more information if it's out there.

Note that breadth-first search provides an algorithm polynomial time in the size $\sigma=|S|$ of the magma: let $S_0$ be your chosen generating set and $S_{n+1}=S_n\cup(S_n\oplus S_n)$. Then if $S_{n+1}=S_n$ then clearly $S_m=S_n$ for all $m\geq n$; otherwise, at least one element must be added at every stage, so after at most $\sigma$ stages we must either get $S$ or hit a fixed-point. Either way, $S_\mu=S_\sigma$ for all $\mu\geq\sigma$. This gives an $O(\sigma^3)$ algorithm, since computing each stage $S_{n+1}$ takes $O(|S_n|^2)\subseteq O(\sigma^2)$ time.