RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. RAN. Ser. Mat., 2000, Volume 64, Issue 4, Pages 201–224 (Mi izv301)

The structure of the set of cube-free $Z$-words in a two-letter alphabet

A. M. Shur

Abstract: The object of our study is the set of $Z$-words, that is, (bi)infinite sequences of alphabetic symbols indexed by integers. We consider an ordered family of subsets of the set of all the cube-free $Z$-words in a two-letter alphabet. The construction of this family is based on the notion of the local exponent of a $Z$-word. The problem of existence of cube-free $Z$-words which are $Z$-words of local exponent 2 (the minimum possible) is described. An important distinction is drawn between strongly cube-free $Z$-words and $Z$-words of greater local exponent.

DOI: https://doi.org/10.4213/im301

Full text: PDF file (2358 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2000, 64:4, 847–871

Bibliographic databases:

MSC: 68R15

Citation: A. M. Shur, “The structure of the set of cube-free $Z$-words in a two-letter alphabet”, Izv. RAN. Ser. Mat., 64:4 (2000), 201–224; Izv. Math., 64:4 (2000), 847–871

Citation in format AMSBIB
\Bibitem{Shu00} \by A.~M.~Shur \paper The structure of the set of cube-free $Z$-words in a~two-letter alphabet \jour Izv. RAN. Ser. Mat. \yr 2000 \vol 64 \issue 4 \pages 201--224 \mathnet{http://mi.mathnet.ru/izv301} \crossref{https://doi.org/10.4213/im301} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1794601} \zmath{https://zbmath.org/?q=an:0972.68131} \transl \jour Izv. Math. \yr 2000 \vol 64 \issue 4 \pages 847--871 \crossref{https://doi.org/10.1070/im2000v064n04ABEH000301} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000165984800008} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33745002826} 

• http://mi.mathnet.ru/eng/izv301
• https://doi.org/10.4213/im301
• http://mi.mathnet.ru/eng/izv/v64/i4/p201

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Karhumäki J., Shallit J., “Polynomial versus exponential growth in repetition-free binary words”, J. Combin. Theory Ser. A, 105:2 (2004), 335–347
2. A. M. Shur, “Kombinatornaya slozhnost ratsionalnykh yazykov”, Diskretn. analiz i issled. oper., ser. 1, ser. 1, 12:2 (2005), 78–99
3. Aberkane A., Currie J.D., “Attainable lengths for circular binary words avoiding $k$ powers”, Bull. Belg. Math. Soc. Simon Stevin, 12:4 (2005), 525–534
4. Rampersad N., “Words avoiding $\frac 73$-powers and the thue-morse morphism”, Internat. J. Found. Comput. Sci., 16:4 (2005), 755–766
5. Krieger D., Shallit J., “Every real number greater than 1 is a critical exponent”, Theoret. Comput. Sci., 381:1-3 (2007), 177–182
6. Currie J.D., Rampersad N., “For each $\alpha>2$ there is an infinite binary word with critical exponent $\alpha$”, Electron. J. Combin., 15:1 (2008), Note 34, 5 pp.
7. Shur A.M., “Combinatorial complexity of regular languages”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, 2008, 289–301
8. Dubickas A., “Binary words with a given Diophantine exponent”, Theoret. Comput. Sci., 410:47-49 (2009), 5191–5195
9. Blondel V.D., Cassaigne J., Jungers R.M., “On the number of $\alpha$-power-free binary words for $2<\alpha\le 7/3$”, Theoret. Comput. Sci., 410:30-32 (2009), 2823–2833
10. Currie J., Rampersad N., “There are $k$-uniform cubefree binary morphisms for all $k\ge 0$”, Discrete Appl. Math., 157:11 (2009), 2548–2551
11. Shur A.M., “Growth rates of complexity of power-free languages”, Theoretical Computer Science, 411:34–36 (2010), 3209–3223
12. D. Jamet, G. Paquin, G. Richomme, L. Vuillon, “On the fixed points of the iterated pseudopalindromic closure operator”, Theoretical Computer Science, 2010
13. Shur A.M., “On the Existence of Minimal beta-Powers”, Developments in Language Theory, Lecture Notes in Computer Science, 6224, 2010, 411–422
14. Elena A. Petrova, Arseny M. Shur, “Constructing Premaximal Binary Cube-free Words of Any Level”, Electron. Proc. Theor. Comput. Sci, 63 (2011), 168–178
15. Shur A.M., “ON THE EXISTENCE OF MINIMAL beta-POWERS”, Internat J Found Comput Sci, 22:7 (2011), 1683–1696
16. Shur A.M., “Deciding Context Equivalence of Binary Overlap-Free Words in Linear Time”, Semigr. Forum, 84:3 (2012), 447–471
17. Petrova E.A., Shur A.M., “Constructing Premaximal Binary Cube-Free Words of Any Level”, Int. J. Found. Comput. Sci., 23:8, SI (2012), 1595–1609
18. Du Ch.F., Shallit J., Shur A.M., “Optimal Bounds For the Similarity Density of the Thue-Morse Word With Overlap-Free and 7/3-Power-Free Infinite Binary Words”, Int. J. Found. Comput. Sci., 26:8 (2015), 1147–1165
•  Number of views: This page: 272 Full text: 121 References: 42 First page: 1