Ranking binary unlabelled necklaces in polynomial time

Duncan Adamson

doi:10.1007/978-3-031-13257-5_2

Ranking binary unlabelled necklaces in polynomial time

Duncan Adamson^*

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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(n⁶log ²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.

Original language	English
Title of host publication	Descriptional complexity of formal systems
Subtitle of host publication	24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, proceedings
Editors	Yo-Sub Han, György Vaszil
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	15-29
Number of pages	15
ISBN (Electronic)	9783031132575
ISBN (Print)	9783031132568
DOIs	https://doi.org/10.1007/978-3-031-13257-5_2
Publication status	Published - 2022
Event	24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 - Debrecen, Hungary Duration: 29 Aug 2022 → 31 Aug 2022 Conference number: 24 https://konferencia.unideb.hu/en/dcfs-2022

Publication series

Name	Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)
Publisher	Springer Nature
Volume	13439 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022
Abbreviated title	DCFS 2022
Country/Territory	Hungary
City	Debrecen
Period	29/08/22 → 31/08/22
Internet address	https://konferencia.unideb.hu/en/dcfs-2022

Access to Document

10.1007/978-3-031-13257-5_2

https://arxiv.org/abs/2205.13916Licence: Other

Cite this

Adamson, D. (2022). Ranking binary unlabelled necklaces in polynomial time. In Y.-S. Han, & G. Vaszil (Eds.), Descriptional complexity of formal systems: 24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, proceedings (pp. 15-29). (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13439 LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-13257-5_2

Adamson, Duncan. / Ranking binary unlabelled necklaces in polynomial time. Descriptional complexity of formal systems: 24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, proceedings. editor / Yo-Sub Han ; György Vaszil. Cham : Springer Nature Switzerland AG, 2022. pp. 15-29 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)).

@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",

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 Nature Switzerland AG",

pages = "15--29",

editor = "Yo-Sub Han and Gy{\"o}rgy Vaszil",

booktitle = "Descriptional complexity of formal systems",

address = "Switzerland",

note = "24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022, DCFS 2022 ; Conference date: 29-08-2022 Through 31-08-2022",

url = "https://konferencia.unideb.hu/en/dcfs-2022",

}

Adamson, D 2022, Ranking binary unlabelled necklaces in polynomial time. in Y-S Han & G Vaszil (eds), Descriptional complexity of formal systems: 24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, proceedings. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics), vol. 13439 LNCS, Springer Nature Switzerland AG, Cham, pp. 15-29, 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022, Debrecen, Hungary, 29/08/22. https://doi.org/10.1007/978-3-031-13257-5_2

Ranking binary unlabelled necklaces in polynomial time. / Adamson, Duncan.
Descriptional complexity of formal systems: 24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, proceedings. ed. / Yo-Sub Han; György Vaszil. Cham: Springer Nature Switzerland AG, 2022. p. 15-29 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13439 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Ranking binary unlabelled necklaces in polynomial time

AU - Adamson, Duncan

N1 - Conference code: 24

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-13257-5_2

DO - 10.1007/978-3-031-13257-5_2

M3 - Conference contribution

AN - SCOPUS:85137067107

SN - 9783031132568

T3 - Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)

SP - 15

EP - 29

BT - Descriptional complexity of formal systems

A2 - Han, Yo-Sub

A2 - Vaszil, György

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022

Y2 - 29 August 2022 through 31 August 2022

ER -