论文标题
在多项式时间内排名二进制的未标记项链
Ranking Binary Unlabelled Necklaces in Polynomial Time
论文作者
论文摘要
未标记的项链是旋转（环状移动）和重新标记操作下的循环单词的等效类别。单词的重新布置是从字母到本身的射击映射。本文的主要结果是第一种用于对二进制字母的未标记项链进行排名的多项式算法。算法的时间复杂性为$ O（n^6 \ log^2 n）$，其中$ n $是所考虑的项链的长度。该算法的关键部分是通过找到其他三个排名来计算一组未标记项链的任何单词的等级：所有项链上的排名，对称对称的未标记项链的等级以及带有封闭标签的项链的等级。本文介绍了最后两个概念。
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.
