Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/101737
Title: | Transition property for cube-free words |
Authors: | Petrova, E. A. Shur, A. M. |
Issue Date: | 2019 |
Publisher: | Springer Verlag |
Citation: | Petrova E. A. Transition property for cube-free words / E. A. Petrova, A. M. Shur. — DOI 10.1007/978-3-030-19955-5_27 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2019. — Vol. 11532 LNCS. — P. 311-324. |
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. © Springer Nature Switzerland AG 2019. |
Keywords: | ARTIFICIAL INTELLIGENCE COMPUTER SCIENCE COMPUTERS BINARY ALPHABETS COMBINATORICS ON WORDS FINITE ALPHABET SUB WORDS TRANSITION PROPERTIES GEOMETRY |
URI: | http://elar.urfu.ru/handle/10995/101737 |
Access: | info:eu-repo/semantics/openAccess |
SCOPUS ID: | 85068604352 |
PURE ID: | 10263206 c2359594-49cf-4df0-95be-471c8f5a20b9 |
ISSN: | 3029743 |
ISBN: | 9783030199548 |
DOI: | 10.1007/978-3-030-19955-5_27 |
Appears in Collections: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2-s2.0-85068604352.pdf | 666,48 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.