Chapter 30
Decoration: One Map, Many Semirings
An earlier presentation of this material carried two separate pieces of data — a weight map valued in \(\CC\) and a cost map valued in an ordered monoid — and called the first a Lagrangian and the second a Hamiltonian. That presentation was doing more work than it needed to and claiming more than it had earned. The two maps have the same domain, the same indexing, and the same shape; they differ only in where they take their values. This chapter replaces them with a single construction, parametric in a semiring, and is careful about which classical structures the construction actually delivers.
The construction itself was built in Part Part I: a decoration is the weight map of Definition 13.4, its domain is the admissible key set of Definition 13.3, and equipping a theory with one is the endofunctor \(\Wgt_{\Semi}\) of Construction 13.1. What is new here is the parameter. Chapter 13 developed two instances because those are the two an implementation runs; the question this chapter asks is what the other choices of semiring deliver, and the answer is that a surprising amount of the classical vocabulary of dynamics is a choice of \(\oplus\) and \(\otimes\).
30.1 Decorations
A semiring \(\Semi = (R, \oplus, \otimes, 0_R, 1_R)\) is a set with two monoid structures, \(\otimes\) distributing over a commutative \(\oplus\), with \(0_R\) absorbing for \(\otimes\). We do not require additive inverses; that omission is the point of the generality.
A decoration of a GSLT \(\GSLT\) in a semiring \(\Semi\) is a family \[\dec_r : \HML(\ctx) \rightharpoonup R, \qquad r \in \rules,\] whose domain consists of formulae that refine the left-hand side of \(r\): formulae \(\phi\) such that \(u \sat \phi\) implies \(u\) matches the pattern \(l_r\). A decorated GSLT is a pair \((\GSLT, \dec)\).
The refinement relation orders the domain of \(\dec_r\): write \(\phi \leq \psi\) when \(\psi\) entails \(\phi\). To evaluate a decoration at a step one must select a formula, and the selection has to be well defined. The condition under which it is, is the partition discipline of Definition 13.2: the keys of a rule are pairwise exclusive and jointly exhaustive over the rule’s left-hand side, so that by Proposition 13.1 each redex is classified by exactly one of them. We write \(\phi_r(u)\) for that unique witness and \(\dec_r(u)\) for \(\dec_r(\phi_r(u))\), and everything below assumes it.
An earlier presentation of this chapter imposed a different and weaker condition, which is worth naming because it is the obvious one and because it will occur independently to any reader who tries to build the construction. Call a decoration refinement-complete when, for every rule \(r\) and every term \(u\) matching \(l_r\), the set of satisfied formulae in \(\mathrm{dom}(\dec_r)\) has a greatest element — a most refined witness — and evaluate the decoration there. This also makes the selection single-valued, and it is strictly weaker: a partition is refinement-complete, since the unique satisfied key is trivially the greatest, and the converse fails.
The reason to prefer the partition is not that most-specific-match is ill-defined but that it is differently defined, and that three things downstream need the disjointness rather than the selection. The locality of reclassification which licenses an incremental simulator needs it; the propensity of a class being summable over its redexes needs it; and in the complex instance the classes being orthogonal projectors needs it. Refinement-completeness delivers a well-defined rate and none of the three. Where a modeller genuinely wants overlapping keys with a most-specific rule — and it is a natural thing to want — what is being specified is a different semantics, and it should be said which.
Let \(\gamma = r_1 \cdot r_2 \cdots r_n\) be a rewrite path from \(P\) to \(Q\), with \(u_i\) the redex at step \(i\). The path weight is the ordered product \[W(\gamma) \;=\; \dec_{r_1}(u_1) \otimes \cdots \otimes \dec_{r_n}(u_n) \;\in\; R,\] and the transition weight from \(P\) to \(Q\) is the sum over paths \[\langle Q \mid P \rangle \;=\; \bigoplus_{\gamma : P \to Q} W(\gamma),\] whenever that sum exists.
The product is ordered because \(\otimes\) need not be commutative, and is not in the cases of interest: the order of the factors is the order of the steps. This is the temporal monoid of [62, \S4] reappearing inside the decoration — reduction is sequential even when interaction is parallel.
30.2 Four instances
The content of the parametrisation is that familiar dynamical structures are recovered by a choice of semiring. What follows is the reading of [62, \S13], transposed to the present setting.
{1.35}
| Semiring \(\Semi\) | What \((\GSLT,\dec)\) becomes |
|---|---|
| Boolean \((\{0,1\},\vee,\wedge)\) | the bare nondeterministic transition system; \(\langle Q\mid P\rangle\) is reachability |
| Tropical \((\Real\cup\{\infty\},\min,+)\) | cost; \(W(\gamma)\) is the total charge of a path and \(\langle Q\mid P\rangle\) is the cheapest way to get there |
| Non-negative reals \((\Real_{\geq 0},+,\times)\) | stochastic dynamics; \(W\) is a path weight, and the Gillespie algorithm samples it — which by Theorem 13.3 is a theorem about degeneration and not an analogy |
| Complex numbers \((\CC,+,\times)\) | amplitudes, and with them interference — see Chapter 33, and the obstruction recorded there |
The weight map was the complex instance; the cost map was the tropical instance. They were never two kinds of structure. Nothing is lost by the merge, and something is gained: the Boolean and stochastic instances, for which the two-map presentation had no room, are now the same construction specialised twice more.
30.3 Where the Lagrangian actually is
The earlier text set \(S[\gamma] = \sum_i \log \dec_{r_i}(u_i)\), observed that \(W(\gamma) = e^{S[\gamma]}\), and called \(S\) an action. That is a change of variable, not a variational principle: it converts a product into a sum and asserts nothing further. A Lagrangian earns its name by making the realised trajectory the stationary point of an action over a space of competing trajectories, and no such principle was stated, let alone proved.
There is nevertheless a genuine least-action statement available, and it is the tropical instance.
In the tropical semiring, Definition 30.3 reads \[W(\gamma) = \sum_{i=1}^{n} \dec_{r_i}(u_i), \qquad \langle Q \mid P \rangle = \min_{\gamma : P \to Q} W(\gamma).\] The path weight is an additive action functional, and the transition weight is its minimisation over all paths. The principle of least action is therefore not an approximation to the sum over paths in this setting; it is the sum over paths, computed in the semiring whose addition is \(\min\).
Immediate from \(\oplus = \min\) and \(\otimes = +\).
The relation between Proposition 30.1 and the complex instance is the relation between tropicalisation and the \(\hbar \to 0\) limit: the saddle-point approximation of a complex sum over paths is a tropical minimisation, which is why the classical limit of a path integral is a least-action principle. Here the two are not limits of each other but instances of one construction at different semirings, so the passage between them is a question about semiring homomorphisms rather than about asymptotics. We do not claim to have answered it. We claim only that this is where the question lives.
The honest summary is this. The decoration supplies a charge per step. The tropical instance supplies a least-action principle. The word “Lagrangian” is warranted for the tropical case and premature for the others.
30.4 Decorations move
A decoration as defined above is static: \(\dec_r\) is fixed once and for all. That is too weak for what the later parts of this book require, where the rate at which a rule fires depends on what has already happened.
A dynamic decoration equips each state with a table \(T : \mathrm{dom}(\dec) \to R\) keyed by the formulae refining the left-hand sides of the rules, and equips each rewrite with an update \(T \mapsto T'\) on the table carried by its successor. A static decoration is the special case in which every update is the identity.
Because the successor state carries a table of the same kind, the updates compose, and the weights are genuinely dynamical rather than parameters.
It is worth being explicit about what that costs and what it buys, since the chapter as previously written recorded the construction and not its consequence. A table travelling with the state means the state is not the term. The object being decorated is the configuration \((P, T)\) of Definition 13.5, and the process is Markov on configurations and in general not on terms — two runs can reach the same term carrying different tables, and then no rate function of the term alone reproduces both (Theorem 13.1, Example 13.1). This is the price of dynamism and it is paid in the size of the state space. It is also, read the other way, the reason a physics whose constants respond to what has happened is still a physics: one has not left the Markovian world, one has moved up a level inside it.
One further consequence is worth recording early: the adequacy of a logic generated over such a structure is a function of the rewrites. Interleaving rewrites yield a logic that sees only interleaving; true-concurrency rewrites yield a logic that sees true concurrency. The decoration does not fix this; the rewrites do.
The propensity of Definition 13.7 carries a second factor this chapter has so far ignored: the geometric factor \(\gfac(k)\) accumulated along the context rules addressing a redex. It is worth naming here because the split it induces is a physical one and the book has no other statement of it. \(\dec_r(u)\) prices a step by what is transferred; \(\gfac(k)\) prices it by where in the term the interaction surfaces are. The first depends on the matter of the interaction and the second on nothing but its position. A weighting of the reduction graph therefore splits, canonically, into a geometric part and a matter part.
We take the default \(\gfac \equiv 1\) throughout — addressing is free — and record the split as an opportunity rather than a result. What would make it more than a suggestive coincidence is an action forcing the two parts to agree, in the way that a field equation forces geometry and matter to determine one another. Chapter 36 lists this among the things not attempted.
30.5 The cost instance, and affordability
The tropical instance deserves separate treatment, because it alone supports a notion of sufficiency: a step can fail for want of funds, which is not something a probability or an amplitude can do.
A resource algebra is a commutative ordered monoid \((A, +, \mathbf{0}, \leq)\). A vectorial account over resource types \(\mathbf{I} = \{1,\ldots,k\}\) is an element \(\vect{A} = (A_1,\ldots,A_k)\) of \(A^k\), each \(A_i\) tracking the available amount of one type.
For the rho calculus the natural types include a budget for fresh names (the \(@\) constructor), a budget for synchronisations, and a budget for persistent-receive firings. Heterogeneous resources are tracked separately because they are not interconvertible for free; what it costs to convert one into another is the subject of the next chapter.
A step is affordable if the account covers the charge: \(\langle P, \vect{A}\rangle \rewrite_r \langle P', \vect{A}'\rangle\) provided that \(P \rewrite_r P'\) via \(r\) with witness \(\phi_r(u)\), that \(\dec_r(u) \leq \vect{A}\) componentwise, and that \(\vect{A}' = \vect{A} - \dec_r(u)\).
Definition 30.6 is stated here in the form the earlier presentation used, and in that form it harbours a defect: it says nothing about who may draw on \(\vect{A}\). A single account adjacent to an associative–commutative soup of processes is adjacent to every process in it, and adjacency taken as the right to spend is ambient authority [64]. The next chapter states the defect precisely and repairs it, and the repair turns out to carry the most interesting physics in this part of the book.