When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring.
Take the string $s = a^6$. Then its compressible substrings are $aa, aaa$. Now assign positioned variables $A_i \to aa$, $B_j \to aaa$, for $i = 1...5, j = 1...4$ like this:
A1 A3
___ ___ ...
a a a a a a
___ ...
A2
B1 B4
_____ _____
a a a a a a
_____
B2 ...
Place each positioned variable in a graph vertex, and connect two vertices whenever one variable cuts another variable, i.e. $A_1 \leqslant B_1$ has a proper substring relationship, so there's no cut there, however, $A_1$ and $B_2$ cut each other, because they overlap in this way:
$$ \exists v \leqslant s : \\ A_1 u = v = u'' B_1; \\ |u|, |u''| \gt 0 $$
/``````\
/```/```\ \
B1---B2---B3----B4
| __/ \ _/\__ |
|/ /\____ \_/_
/\____/__ __\_/ \
/ / \/ \ \
A1----A2---A3---A4---A5
An undirected edge between two nodes means their respective variables cut one another (the positioned strings they expand to within $s$)
Now, you start by picking any vertex of least degree - i.e. the least number of cuttings of other variables. Here, the choices are one of: $B_1, B_4, A_1, A_5$. However, $A_1 \leqslant B_1$ so choosing $A_1$ before $B_1$ is preferable, because, if you do this, then you can still choose $B_1$ later and have $A_1$ sit inside of the rule $B_1 \to A_1 a$ like so. So the first choices are merely $A_1, A_5$.
So you loop over the first choices, say we chose $A_1$. This gives:
$$g :\\ S \to Aa^4 \\ A \to aa $$
And the conflict graph then becomes:
B1--------B3----B4
\ | __/
\ \/______
\ / \
`--A3---A4---A5
You then have choices: $B1, B_4, A_4, A_5$ since choosing $A_1$ the first iteration, cancelled the nodes $A_2, B_2$ (and their edges).
Now loop over the possible choices, and so on...
Question. Does this always lead to all possible smallest grammars for $s$?
