Reverse path forwarding accepts a source's multicast traffic only on the interface selected for the reverse route to that source. With consistent loop-free routing, those parent choices define a source-rooted tree. Membership pruning can then remove unneeded branches.

Liquor Morphiae Hydrochloratis is a solution of morphine hydrochloride. Its concentration and solvent are necessary to interpret the historical formulation.^[ref]

For a fixed word $w$, store the length of the longest suffix of the received stream that is also a prefix of $w$. On a new input symbol, append it to the represented prefix and select the longest resulting suffix that is a prefix of $w$. The complete-word state signals recognition. Its outgoing transitions retain proper suffix matches, allowing overlapping occurrences rather than automatically restarting from the empty prefix. This is the finite-state form of the prefix information used by the Knuth-Morris-Pratt algorithm.

For example, recognizing $1101$ needs suffix-prefix states of lengths zero through four. After a complete match followed by one, the last two symbols are $11$, so the next state retains length two. This permits the second match in $1101101$ without clearing the useful suffix.

Enter a distinguished Moore machine state whose output is active, and ensure that every outgoing transition leaves that state for an inactive-output state. The output then lasts one clock period. Its outgoing transitions may simultaneously recognize the start of the next event, avoiding an unnecessary idle cycle. The one-period statement refers to the synchronous logical model, with ordinary propagation delay after each clock edge.

A synchronous sequential circuit can use three states: armed, pulse, and waiting. Only the pulse state has output one. A reset input rearms the circuit, including when it arrives during the pulse cycle; this permits pulses on alternate clock cycles while each pulse still lasts exactly one cycle.

A wait returning without the application predicate necessarily becoming true. Rechecking that predicate in a loop also handles the separate possibility that another caller consumed the resource before the awakened caller could acquire the monitor.

If $U$ and $X$ are independent real random variables, then the moment-generating function of their product is $M_{UX}(t)={\mathbb{E}}_U[M_X(tU)]$ wherever the expression is finite. This follows by conditioning on $U$: the conditional law of $X$ is unchanged by independence, so $\mathbb{E}(e^{tUX}\mid U)=M_X(tU)$. For $U$ uniform on $(0,1)$, the formula becomes $M_{UX}(t)={\int }_0^1{M}_X(tu)du$. If $M_X$ is finite on a neighborhood of zero, this product also has a finite moment-generating function on a neighborhood of zero, because the bounded factor $U$ keeps $tu$ between zero and $t$.

For a module $M$ over an integral domain $R$ with field of fractions $K$, its rank is the dimension of $K{\otimes }_{R}M$. The tensor product of modules here extends scalars to a field, turning the question into a dimension calculation. For a free module $R^r$, the result is $r$.

For a finitely generated module over a principal ideal domain, the structure theorem for finitely generated modules over a principal ideal domain gives $M\cong R^r\oplus {⨁}_{i}R/(d_i)$, with $d_i$ nonzero nonunits. Each torsion element of a module vanishes after extension of scalars, because its annihilating nonzero scalar becomes invertible in $K$. Thus $K{\otimes }_{R}M\cong K^r$, proving that the rank is the number of free summands. The rank does not record the torsion submodule: for example, $R\oplus R/(d)$ and $R$ have the same rank.

A right module over a unital ring $R$ is an abelian group $M$ with an additive scalar action on the right satisfying $(mr)s=m(rs)$, $m(r+s)=mr+ms$ and $m1=m$. The order of multiplication matters for a noncommutative ring. Equivalently it is a left module over the opposite ring. Row vectors acted on by matrices on the right give a basic example.

A module over a complex associative algebra $A$ has central character $\theta$ if every element $z$ of the centre acts as the scalar $\theta (z)$, where $\theta$ is a unital algebra homomorphism. A Verma module has a central character: the centre preserves its one-dimensional highest-weight space, and centrality extends that scalar action from the cyclic generator to every vector. A nonzero homomorphism between two modules with scalar central actions forces their central characters to coincide. A generalized central character allows each $z-\theta (z)$ to act locally nilpotently instead of as zero.

Let $A=\{z:|z-i|<\sqrt{2},|z+i|<\sqrt{2}\}$. Writing $t=(1+z)/(1-z)=u+iv$, its inverse gives $1-|z{|}^2=4u/|t+1{|}^2$ and $\mathrm{Im}z=2v/|t+1{|}^2$. The lens condition is therefore exactly $u>|v|$. Multiplication by $1+i$ converts that to positive real and imaginary parts. Thus the displayed Möbius transformation maps the lens bijectively to the first quadrant. Its two boundary arcs meet at $-1,1$, which map to zero and infinity. The centre zero maps to $1+i$. The derivative never vanishes inside the lens.

A useful way to map a circular lens is to send its two corner points to zero and infinity with a Möbius transformation. The two bounding circles then become straight rays, and a suitable power opens their sector into a half-plane.

For the lens $|z+1|<\sqrt{2}$, $|z-1|<\sqrt{2}$, the corners are $\pm i$. Put $w=(z-i)/(z+i)$, with inverse $z=i(1+w)/(1-w)$. For $w=u+iv$, substitution givesThus the image is precisely $u<-|v|$, or $3\pi /4<\arg w<5\pi /4$. Rotation through $-3\pi /4$ followed by squaring gives the displayed conformal map onto the upper half-plane. The open sector contains no opposite pair, so squaring is injective; it has nonzero derivative away from its excluded vertex. These facts also prove bijectivity and conformality, rather than merely identifying boundary images.

For ordered triples of distinct points of the Riemann sphere, a unique Möbius transformation sends the first triple to the second. Normalize each triple to $0,1,\infty$ using $T_z(z)=(z-z_1)(z_2-z_3)/((z-z_3)(z_2-z_1))$, with the usual limits at infinity, and compose $T_w^{-1}\circ T_z$. Any two choices differ by a Möbius transformation fixing those three standard points. Fixing infinity makes it affine; fixing zero and one then makes it the identity. Thus the Möbius group action is sharply three-transitive, a stronger property than mere transitivity on triples.

Root a finite tree, and let $D_0,D_1$ be the optimum vertex cover sizes of a descendant subtree conditional on excluding or including its root. Excluding a parent forces all children to be included; including it permits either child state. These facts prove the displayed recurrences by structural induction. Empty child sums give $D_0=0,D_1=1$ at a leaf of a rooted tree. Evaluating in postorder traversal and taking the smaller root state gives a linear-time dynamic programming algorithm.

For a permutation input, the first row of its RSK insertion tableau is the minimum-tail table for increasing subsequences: its $j$th entry is the least attainable final value of a strictly increasing subsequence of length $j$ in the processed prefix. Inserting $z$ replaces the first entry larger than $z$, or appends if none exists. In replacement position $r$, the previous entry in position $r-1$ supplies a subsequence that can be extended by $z$. Shorter minimum tails were already smaller, and a longer subsequence ending at $z$ would require an old tail in position at least $r$ smaller than $z$, contrary to the replacement rule. This proves the invariant inductively. Consequently the first-row length is the longest increasing subsequence length. The row entries need not be a subsequence together: input $2,4,3,1$ gives first row $1,3$, although one occurs after three. They are minima for different lengths, obtained from potentially different subsequences.

Sort the edge weights of a minimum spanning tree $T$ and of any spanning tree $S$ in nondecreasing order. Then $w_i(T)\le w_i(S)$ for every position. To prove it, fix a threshold $t$ and retain the graph's edges of weight at most $t$. If this graph has $c$ connected components, $T$ contains a spanning forest of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than $t$ on its tree path, decreasing total weight. Hence exactly $|V|-c$ edges of $T$ have weight at most $t$. No other spanning tree can have more, since its retained edges form a forest inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.

Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.

Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.

Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.^[ref]

Let an edge set $F$ be contained in some minimum spanning tree, and let a cut of a graph have no crossing edge in $F$. Any least-weight edge crossing that cut of a graph can be added to $F$ while preserving its containment in some minimum spanning tree. Insert the chosen edge into an optimum containing $F$, then remove another crossing edge from the resulting graph cycle; it is no lighter and cannot belong to $F$. Ties imply existence of an optimum containing the chosen edge, rather than membership in every optimum.

A minimizing sequence can converge uniformly while its derivatives keep oscillating between distinct energy wells. For the functional $I(u)={\int }_0^1[u^4+(u^{\prime 4}-16{)}^4]$, with zero endpoint values and Lipschitz admissible functions, the triangular waves displayed above have slopes $\pm 2$ almost everywhere and height $1/N$. Direct integration gives $I(u_N)=1/(5N^4)$. Nonnegativity therefore makes the infimum zero. Attainment would require both $u=0$ and $|u^{\prime }|=2$ almost everywhere, an impossibility. The uniform limit is zero but its energy is $16^4$; thus the energy fails to be lower semicontinuous for this convergence. The example explains why control of function values alone cannot replace suitable convexity in the derivative variable in the direct method in the calculus of variations.

Let $A$ be a companion matrix of a monic irreducible polynomial $f\in F[x]$ of degree $n$. Form the $N$-by-$N$ block matrix $B$ with $A$ on its diagonal, $I_n$ immediately above the diagonal, and zero elsewhere. If the field characteristic is $p>0$, write $f(x)=h(x^q)$ with $q=p^r$ maximal, so that $h^{\prime }\ne 0$; in characteristic zero take $q=1$ and $h=f$. ThenThus a separable polynomial gives $m_B=f^N$, but an irreducible polynomial with zero formal derivative can give a smaller exponent. For example, over the rational function field ${\mathbb{F}}_2(t)$, the irreducible polynomial $f(x)=x^2-t$ has $q=2$, so a two-block chain still has minimal polynomial $f$.

To prove the formula, write $B=D+K$, where $D$ has diagonal blocks $A$ and $K$ is the block shift. These are commuting operators, and $K^j$ vanishes exactly when $j\ge N$. The binomial theorem in positive field characteristic gives $B^q=D^q+K^q$. Expanding $h(D^q+K^q)$ gives $f(B)=K^{q}H$, with $H$ commuting with $K$. The diagonal blocks of $H$ are $h^{\prime }(A^q)$, which are invertible by Bézout's identity for polynomials, since $h$ is irreducible with nonzero formal derivative and $h(A^q)=0$. Therefore $f(B{)}^s=K^{qs}{H}^s$ vanishes exactly when $qs\ge N$. Finally, the block upper triangular matrix determinant gives the displayed characteristic polynomial, while the Cayley-Hamilton theorem and irreducibility force the minimal polynomial to be a power of $f$.