# An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation

Take $$s = a^{10}$$ for our example string. Compute the set of all potential grammar reducing variable-rules:

$$A \to aa \\ B \to aaa \\ C \to aaaa \\ D \to aaaaa$$

There is always exactly $$\left\lfloor \dfrac{|s|}{2}\right\rfloor - 1$$ of these over a singleton alphabet, or in other words $$O(|s|)$$.

Now enumerate all possible start reduced rules up to commutation of the variables. Everything commutes over a singleton alphabet! Note that because these rules are reduced, we will not see $$AABB \simeq ABAB$$ because clearly you can reduce that, where $$\simeq$$ is equivalence by commuting symbols (they expand to the same string i.e.). Note that to compute just one smallest grammar, it is sufficient to only search for reduced smallest grammars.

$$S \to ABCa \\ S \to AAAC \\ \vdots$$

So the rule here is you can have $$1$$ to $$3$$ copies of one variable and single copies of the other variables, and everything must expand to $$S \to s = a^{10}$$. I can see and easily enough prove this.

So all of these look like (dropping the "$$S \to$$" notationally):

$$ABCa \\ ABD \\ AADa \\ AAAC \\ BBC \\ BBBa \\ ACC \\ CDa \\ DD$$

Those are all that I could figure out off the top of my head, but of course an algorithm for enumerating them is not the critical part of this discussion. Those are all possible RHS's $$\gamma$$ of start rules $$S \to \gamma$$ in any reduced grammar for $$s$$, up to commutation of the symbols (i.e. the total number of possibilities is too much to count, but we can do it up to commutation). Remember, the reduced smallest grammars are a non-empty subset of the reduced grammars. So the reduced grammars can make up our sufficient search space.

I have two questions:

1. What is the approximate order or Big-O notation for the number of possible irreducible start rules in the $$|\Sigma|$$ symbols where in the example $$\Sigma = \{A, B, C, D, a\}$$, i.e. the size of the above enumeration?

2. How should the algorithm then recurse? It's as if you need to form all $$k$$-tuples of strings:

$$(ABCa, aa, Aa, AA) \\ (ABCa, aa, Aa, C)\\ \vdots$$

for where $$k$$ depends on each case's number of involved variables, so it's like doing the first enumeration but $$(k-1)$$-fold simultaneously, minding the already set start rule RHS.

A last question:

Does this algorithm have a polynomial-time feeling about it?

The initial list of possibly needed-to-be-considered start rules can actually be shortened to:

$$BBC, DD, ACC, BBBa$$

If we apply the fact that for example $$B = Aa, C = Ba = AA, D = AB$$, etc. Because if you look at $$ABCa \simeq AaBC$$; this can clearly be reduced by the presence of $$B$$ in the grammar to: $$BBC$$, and similarly for the other above-listed start rule possibilities.

• @D.W. This algorithm will compute an optimal smallest grammar for $s = a^n$ I think in polynomial time in $n$. So if you apply it to exponention / addition chains, you'll get the most optimal way to exponentiate. But a better application for it is theoretical. I.e. perhaps we can generalize it to handle a binary alphabet $\Sigma = \{a, b\}$. Nov 11, 2022 at 20:55