Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101532
Title: Transition Property for Cube-Free Words
Authors: Petrova, E. A.
Shur, A. M.
Issue Date: 2021
Publisher: Springer
Citation: Petrova E. A. Transition Property for Cube-Free Words / E. A. Petrova, A. M. Shur. — DOI 10.1007/s00224-020-09979-4 // Theory of Computing Systems. — 2021. — Vol. 65. — Iss. 3. — P. 479-496.
Abstract: We study cube-free words over arbitrary non-unary finite alphabets and prove the following structural property: for every pair (u, v) of d-ary cube-free words, if u can be infinitely extended to the right and v can be infinitely extended to the left respecting the cube-freeness property, then there exists a “transition” word w over the same alphabet such that uwv is cube free. The crucial case is the case of the binary alphabet, analyzed in the central part of the paper. The obtained “transition property”, together with the developed technique, allowed us to solve cube-free versions of three old open problems by Restivo and Salemi. Besides, it has some further implications for combinatorics on words; e.g., it implies the existence of infinite cube-free words of very big subword (factor) complexity. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Keywords: CUBE-FREE WORD
EXTENDABLE WORD
POWER-FREE WORD
TRANSITION PROPERTY
COMPUTER SCIENCE
MATHEMATICAL TECHNIQUES
BINARY ALPHABETS
COMBINATORICS ON WORDS
FINITE ALPHABET
SUB WORDS
TRANSITION PROPERTIES
GEOMETRY
URI: http://hdl.handle.net/10995/101532
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85084089411
PURE ID: 21881783
ISSN: 14324350
DOI: 10.1007/s00224-020-09979-4
metadata.dc.description.sponsorship: E.A. Petrova — Supported by the Russian Science Foundation, grant 18-71-00043.
RSCF project card: 18-71-00043
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85084089411.pdf666,48 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.