Unlabelled Necklaces are an equivalence class of cyclic words under both the rotation (cyclic shift) and the relabelling operations. The relabelling of a word is a bijective mapping from the alphabet to itself. The main result of the paper is the first polynomial-time algorithm for ranking unlabelled necklaces of a binary alphabet. The time-complexity of the algorithm is $O(n^6 \log^2 n)$, where $n$ is the length of the considered necklaces. The key part of the algorithm is to compute the rank of any word with respect to the set of unlabelled necklaces by finding three other ranks: the rank over all necklaces, the rank over symmetric unlabelled necklaces, and the rank over necklaces with an enclosing labelling. The last two concepts are introduced in this paper.
翻译:未贴标签的颈带是旋转(循环转移)和重新标签操作下的循环单词的等值类。 一个单词的重新标签是从字母到本身的双向映射。 论文的主要结果为二字母中排序未贴标签项链的第一个多元时间算法。 算法的时间复杂性为$O( n)6\log ⁇ 2 n), 其中一美元是所考虑项链的长度。 算法的关键部分是通过找到另外三个等级来计算未贴标签项链集中任何单词的等级: 所有项链的等级、 未贴标签项链的等级高于对称的等级以及带有标签的项链的等级。 本文介绍了最后两个概念 。