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.

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.