Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102933
Название: Branching densities of cube-free and square-free words
Авторы: Petrova, E. A.
Shur, A. M.
Дата публикации: 2021
Издатель: MDPI AG
Библиографическое описание: Petrova E. A. Branching densities of cube-free and square-free words / E. A. Petrova, A. M. Shur. — DOI 10.3390/a14040126 // Algorithms. — 2021. — Vol. 14. — Iss. 4. — 126.
Аннотация: Binary cube-free language and ternary square-free language are two “canonical” represen-tatives of a wide class of languages defined by avoidance properties. Each of these two languages can be viewed as an infinite binary tree reflecting the prefix order of its elements. We study how “homogenious” these trees are, analysing the following parameter: the density of branching nodes along infinite paths. We present combinatorial results and an efficient search algorithm, which together allowed us to get the following numerical results for the cube-free language: the minimal density of branching points is between 3509/9120 ≈ 0.38476 and 13/29 ≈ 0.44828, and the maximal density is between 0.72 and 67/93 ≈ 0.72043. We also prove the lower bound 223/868 ≈ 0.25691 on the density of branching points in the tree of the ternary square-free language. © 2021 by the authors. Licensee MDPI, Basel, Switzerland.
Ключевые слова: CUBE-FREE WORD
POWER-FREE WORD
PREFIX TREE
GEOMETRY
BRANCHING DENSITY
BRANCHING POINTS
FREE LANGUAGES
INFINITE PATH
LOWER BOUNDS
NUMERICAL RESULTS
SEARCH ALGORITHMS
SQUARE-FREE WORDS
BINARY TREES
URI: http://elar.urfu.ru/handle/10995/102933
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор РИНЦ: 46036362
Идентификатор SCOPUS: 85105119295
Идентификатор WOS: 000642702000001
Идентификатор PURE: 21871426
87174162-f3a5-4f49-b011-64291c216add
ISSN: 19994893
DOI: 10.3390/a14040126
Сведения о поддержке: This research was funded by Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2020-1537/1).
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-85105119295.pdf550,1 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.