@inproceedings{5700596ff5b5443baea12f7654fabfbb,
title = "Ranking Binary Unlabelled Necklaces in Polynomial Time",
abstract = "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(n6log 2n), 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.",
author = "Duncan Adamson",
note = "Publisher Copyright: {\textcopyright} 2022, IFIP International Federation for Information Processing.; 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 ; Conference date: 29-08-2022 Through 31-08-2022",
year = "2022",
doi = "10.1007/978-3-031-13257-5_2",
language = "English",
isbn = "9783031132568",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media",
pages = "15--29",
editor = "Yo-Sub Han and Gy{\"o}rgy Vaszil",
booktitle = "Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings",
address = "United States",
}