Ranking Binary Unlabelled Necklaces in Polynomial Time

Duncan Adamson*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings
EditorsYo-Sub Han, György Vaszil
PublisherSpringer Science and Business Media
Pages15-29
Number of pages15
ISBN (Print)9783031132568
DOIs
Publication statusPublished - 2022
Event24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 - Debrecen, Hungary
Duration: 29 Aug 202231 Aug 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13439 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022
Country/TerritoryHungary
CityDebrecen
Period29/08/2231/08/22

Fingerprint

Dive into the research topics of 'Ranking Binary Unlabelled Necklaces in Polynomial Time'. Together they form a unique fingerprint.

Cite this