A symmetric set without identity $S$ is a set with a bijective function $inv : S \rightarrow S$ with no fixed points such that $inv(inv(x)) = x$ for any $x \in S$.
We say that two disjoint pairs $\{i,j\}$ and $\{k,m\}$ where $i<j$ and $k<m$, are linked if either $i<k<j<m$ or $k<i<m<j$.
A folding of a word $w = l_1 \cdots l_n$ over a symmetric set without identity is a collection of disjoint pairs $F \subset \{\{i,j\} | 1 \leq i <j \leq n\}$ such that for $\{i,j\} \in F$ we have $l_i = inv(l_j)$ and that any two pairs $\{i_1,j_1\} \in F$ and $\{i_2,j_2\} \in F$ are not linked.
We say a position $ i (i \leq i \leq n)$ is unpaired in a folding $F$ of a word w = $l_1 \cdots l_n$ over a symmetric set without identity, if $\{i,j\} \notin F$ for any $ i \leq j \leq n$.
A weight function on a symmetric set without identity S is a function $wt : S \rightarrow \mathbb{R}^+ \cup {0}$ such that $wt(inv(x)) = wt(x)$ for any $x \in S$.
The weighted cancellation norm of a word $w = l_1 \cdots l_n$ over a symmetric set without identity $S$ with a weight function $wt$ is defined as $$ \| w\|: = \min_F \sum_i wt(l_i)$$ where $F$ ranges over all foldings of $w$ and $i$ ranges over all umpaired positions in $F$
How can the weighted cancellation norm of a word $w = l_1 \cdots l_n$ be computed within time $\mathcal{O}(n^3)$ and space $\mathcal{O}(n^2)$
This is all there in https://arxiv.org/abs/1412.0101
I don't understand how the author does it. So he considers whether $l_n$ is in folding $F$ or not. I don't understand how that reduces the no of steps? Like for example $n=3$ then we need three comparisons in the worst case $\{3,2\} , \{3,1\} \text{and} \{1,2\}$
Any intuition or explanation on how to compute the weighted cancellation norm would be extremely helpful.
