Towards Settling the Complexity of the Lettericity Problem

Mario Grobler, Nils Morawietz, Silas Cato Sacher

The lettericity of a graph $G=(V,E)$ is defined as the smallest size of an alphabet $\Sigma$ such that there is a word $w_1\dots w_{|V|}\in {\Sigma }^{\ast }$ and a decoder $\mathcal{D} \subseteq Σ…