Counting Ternary Square-Free Words Quickly › SPbU Researchers Portal

DOI

https://doi.org/10.1007/978-3-030-85088-3_12
Final published version

Vladislav Makarov

An efficient, when compared to exhaustive enumeration, algorithm for computing the number of square-free words of length n over the alphabet { a, b, c} is presented.

Original language	English
Title of host publication	Combinatorics on Words - 13th International Conference, WORDS 2021, Proceedings
Editors	Thierry Lecroq, Svetlana Puzynina
Publisher	Springer Nature
Pages	142-152
Number of pages	11
ISBN (Electronic)	978-3-030-85088-3
ISBN (Print)	9783030850876
DOIs	https://doi.org/10.1007/978-3-030-85088-3_12
State	Published - 2021
Event	13th International Conference on Combinatorics on Words, WORDS 2021 - Virtual, Online Duration: 13 Sep 2021 → 17 Sep 2021

Publication series

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

Conference

Conference	13th International Conference on Combinatorics on Words, WORDS 2021
City	Virtual, Online
Period	13/09/21 → 17/09/21

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Research areas

Aho-Corasick automaton, Dynamic programming, Inclusion-exclusion, Square-free words

ID: 93920109