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.

  • 1
    $\begingroup$ Possibly related: en.wikipedia.org/wiki/Addition_chain $\endgroup$
    – D.W.
    Nov 11, 2022 at 19:49
  • $\begingroup$ @D.W. that is related, but also my approach is something new. $\endgroup$ Nov 11, 2022 at 20:41
  • $\begingroup$ @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\}$. $\endgroup$ Nov 11, 2022 at 20:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.