 All-subsequence embedding kernel

Here ${\varphi }_u(x)$ counts increasing position embeddings of the word $u$ as a subsequence of $x$. Counting embeddings retains repeated-letter multiplicities. The empty word has one embedding in every string. Prefix dynamic programming computes this positive-semidefinite kernel by $F(i,j)=F(i-1,j)+F(i,j-1)-F(i-1,j-1)+1_{\{x_i=y_j\}}F(i-1,j-1)$ with boundary values one. The time complexity is $O(|x||y|)$ arithmetic operations, and rolling rows require $O(\min (|x|,|y|))$ integer cells. Counting pairs of position subsets bounds output bit length by $O(|x|+|y|)$.