Compressing permutation groups into grammars and polytopes. A graph embedding approach

Abstract

In this work, we show that the minimum size of a context-free grammar generating a finite permutation group G can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree.

Keywords

• Permutation groups
• grammars
• polytopes