General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Izv. RAN. Ser. Mat.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 18 scientific papers (total in 18 papers)

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.


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

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

Bibliographic databases:

MSC: 68R15
Received: 28.01.1999

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
\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
\jour Izv. Math.
\yr 2000
\vol 64
\issue 4
\pages 847--871

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. Karhumäki J., Shallit J., “Polynomial versus exponential growth in repetition-free binary words”, J. Combin. Theory Ser. A, 105:2 (2004), 335–347  crossref  mathscinet  zmath  isi  elib  scopus
    2. A. M. Shur, “Kombinatornaya slozhnost ratsionalnykh yazykov”, Diskretn. analiz i issled. oper., ser. 1, ser. 1, 12:2 (2005), 78–99  mathnet  mathscinet  zmath  elib
    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  mathscinet  zmath  isi
    4. Rampersad N., “Words avoiding $\frac 73$-powers and the thue-morse morphism”, Internat. J. Found. Comput. Sci., 16:4 (2005), 755–766  crossref  mathscinet  zmath  isi  elib  scopus
    5. Krieger D., Shallit J., “Every real number greater than 1 is a critical exponent”, Theoret. Comput. Sci., 381:1-3 (2007), 177–182  crossref  mathscinet  zmath  isi  scopus
    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.  mathscinet  zmath  isi
    7. Shur A.M., “Combinatorial complexity of regular languages”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, 2008, 289–301  crossref  mathscinet  zmath  isi  scopus
    8. Dubickas A., “Binary words with a given Diophantine exponent”, Theoret. Comput. Sci., 410:47-49 (2009), 5191–5195  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    11. Shur A.M., “Growth rates of complexity of power-free languages”, Theoretical Computer Science, 411:34–36 (2010), 3209–3223  crossref  mathscinet  zmath  isi  elib  scopus
    12. D. Jamet, G. Paquin, G. Richomme, L. Vuillon, “On the fixed points of the iterated pseudopalindromic closure operator”, Theoretical Computer Science, 2010  crossref  mathscinet  isi  scopus
    13. Shur A.M., “On the Existence of Minimal beta-Powers”, Developments in Language Theory, Lecture Notes in Computer Science, 6224, 2010, 411–422  crossref  mathscinet  zmath  isi  scopus
    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  crossref  zmath
    15. Shur A.M., “ON THE EXISTENCE OF MINIMAL beta-POWERS”, Internat J Found Comput Sci, 22:7 (2011), 1683–1696  crossref  mathscinet  zmath  isi  elib  scopus
    16. Shur A.M., “Deciding Context Equivalence of Binary Overlap-Free Words in Linear Time”, Semigr. Forum, 84:3 (2012), 447–471  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Number of views:
    This page:272
    Full text:121
    First page:1

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019