Abstract
A weak square in a binary word is a pair of adjacent nonempty blocks of the same length, having the same number of 1s. A weak circular square is a weak square which is possibly wrapped around the word: the tail protruding from the right end of the word reappears at the left end. Two weak circular squares are equivalent if they have the same length and contain the same number of ones. We prove that the longest word with only k inequivalent weak circular squares contains 4k+2 bits and has the form (01)2k+1 or its complement. Possible connections to tandem repeats in the human genome are pointed out.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Berstel [1992], Axel Thue's work on repetitions in words, in: Séries Formelles et Combinatoire Algébrique (P. Leroux and C. Reutenauer, eds.), Publ. du LaCIM, Vol. 11, Université de Québec à Montréal, Canada, pp. 65–80.
J. Berstel [1995], Axel Thue's papers on repetition in words: an English translation, Publ. du LACIM, Vol. 20, Université de Québec à Montréal, Canada.
S. Burris and E. Nelson [1971/72], Embedding the dual of π∞ in the lattice of equational classes of semigroups, Algebra Universalis 1, 248–153.
J.D. Currie [1993], Open problems in pattern avoidance, Amer. Math. Monthly 100, 790–793.
A. del Junco [1977], A transformation with simple spectrum which is not rank one, Canad. J. Math. 29, 655–663.
A. Ehrenfeucht and G. Rozenberg [1983], On the separating power of EOL systems, RAIRO Inform. Théor. 17, 13–22.
R. Entringer, D. Jackson and J. Schatz [1974], On nonrepetitive sequences, J. Combin. Theory (Ser. A) 16, 159–164.
P. Erdös [1961], Some unsolved problems, Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 6, 221–254.
A.S. Fraenkel and R.J. Simpson [1995], How many squares must a binary sequence contain? Electronic J. Combinatorics 2 (1995) R2, 9pp. http://ejc.math.gatech.edu:8080/Journal/journalhome.html
D. Hawkins and W.E. Mientka [1956], On sequences which contain no repetitions, Math. Student 24, 185–187.
A.J. Jeffreys, M. Turner and P. Debenham [1991], The efficiency of multilocus DNA fingerprint probes for individualization and establishment of family relationships, determined from extensive casework, Am. J. Hum. Genet. 48, 824–840.
A.J. Jeffreys, V. Wilson and S.L. Thein [1985], Hypervariable ‘minisatellite’ regions in human DNA, Nature 314, 67–73.
A.J. Jeffreys, V. Wilson and S.L. Thein [1985], Individual-specific ‘fingerprints’ of human DNA, Nature 316, 76–79.
V. Keränen [1992], Abelian squares are avoidable on 4 letters, Automata, Languages and Programming: Lecture Notes in Computer Science 623, 41–52, Springer Verlag.
J.A. Leech [1957], A problem on strings of beads, Math. Gaz. 41, 277–278.
A. Milosavljević [≥1997], Repeat Analysis, Ch. 13, Sect. 4, Imperial Cancer Research Fund Handbook of Genome Analysis, Blackwell Scientific Publications, in press.
M. Morse and G.A. Hedlund [1944], Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J. 11, 1–7.
P.S. Novikov and S.I. Adjan [1968], Infinite periodic groups I, II, III, Izv. Akad. Nauk. SSSR Ser. Mat. 32, 212–244; 251–524; 709–731.
P.A.B. Pleasants [1970], Non-repetitive sequences, Proc. Cambridge Phil. Soc. 68, 267–274.
I. Raskó and C.S. Downes [1995], Genes in Medicine: Molecular Biology and Human Genetic Disorders, Chapman & Hall, London.
A. Thue [1912], Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr., I. Mat. Nat. Kl. Christiania I, 1–67.
E.N. Trifonov [1989], The multiple codes of nucleotide sequences, Bull. Math. Biology 51, 417–432.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fraenkel, A.S., Simpson, J., Paterson, M. (1997). On weak circular squares in binary words. In: Apostolico, A., Hein, J. (eds) Combinatorial Pattern Matching. CPM 1997. Lecture Notes in Computer Science, vol 1264. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63220-4_51
Download citation
DOI: https://doi.org/10.1007/3-540-63220-4_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63220-7
Online ISBN: 978-3-540-69214-0
eBook Packages: Springer Book Archive