The Generalized Smallest Grammar Problem
Table 2: Size of the final grammars obtained with the different algorithms. SGP algorithms (non-bold numbers) generate straight-line grammars, while NRGreedyfix and the +Post columns (bold numbers) infer non-recursive grammars. Green/Red down-/up-ward arrows show a reduction/increase in the grammar size with respect to the output of the reference algorithm in each section, and = shows no change. #Ctx is the number of branching rules detected by the post-processing algorithm. In the cases with -, either the final grammar or the output of ZZ algorithm was not available. The results for MMAS-GA are taken from Benz and Kötzing (2013).
['[BOLD] Data', 'Greedy', '[BOLD] Grammar Size NRGreedyfix', '[BOLD] Grammar Size  [BOLD] +Post', '[BOLD] Grammar Size # [ITALIC] Ctx', '[BOLD] Grammar Size  [BOLD] IRRMGP', '[BOLD] Grammar Size  [BOLD] +Post', '# [ITALIC] Ctx', '[BOLD] ZZ', '[BOLD] +Post', '# [ITALIC] Ctx', '[BOLD] MMAS-GA']
As pointed out before, we did not achieve to obtain smaller grammars by incorporating branching-rules inference during the main process (algorithm NRGreedyfix). The final grammars were consistently larger than the simplest baseline (Greedy), often considerably so (see for instance humhdab, alice29.txt). However, the same idea of inferring fixed-motifs proved to be successful when applied as a post-processing. Moreover, this strategy can be applied to any straight-line grammar and can therefore be used after any SGP algorithm. Under the column # Ctx, we give the number of branching rules that are inferred. The number of occurrences of these rules is of course much higher in general. The better the original algorithm, the smaller the gain. While this may point towards a convergence of the possible redundancy that can be extracted, it should be noted that our approach runs much faster than the more sophisticated algorithms (ZZ, MMAS-GA).