Repetition-free words. (English) Zbl 0596.20058

Kobayashi, Yuji

Theor. Comput. Sci. 44, 175-197 (1986).

The author derives general properties of the language of all words in an alphabet not satisfying a property P inherited by subwords. These include results on density and ”growing homomorphisms” by which such words can be constructed. He derives as applications new proofs of results of the growth of squarefree words and new results on power 7/4 free words.

Reviewer: K.H.Kim

MSC:

20M35	Semigroups in automata theory, linguistics, etc.
20M05	Free semigroups, generators and relations, word problems
68Q45	Formal languages and automata

Keywords:

growing homomorphisms; language; words; density; growth of squarefree words

References:

[1]	Adian, S.I., The Burnside problem and identities in groups, (1979), Springer Berlin/Heidelberg/New York · Zbl 1343.20040
[2]	Arson, S., Proof of the existence of asymmetric infinite sequences, Math. semesterber., 4, 769-777, (1937)
[3]	Bean, D.R.; Ehrenfeucht, A.; McNulty, G.F., Avoidable patterns in strings of symbols, Pacific J. math., 85, 261-294, (1979) · Zbl 0428.05001
[4]	Berstel, J., Sur LES mots sans carré définis par un morphisme, (), 16-25 · Zbl 0425.20046
[5]	Berstel, J.; Reutenauer, C., Square-free words and idempotent semigroups, (), Chapter 2
[6]	Boasson, L.; Nivat, M., Adherences of languages, J. comput. system sci., 20, 285-309, (1980) · Zbl 0471.68052
[7]	Brandenburg, F.-J., Uniformly growing kth power-free homomorphisms, Theoret. comput. sci., 23, 69-82, (1983) · Zbl 0508.68051
[8]	Brinkhuis, J., Non-repetitive sequences on three symbols, Quart. J. math. Oxford, 34, 145-149, (1983) · Zbl 0528.05004
[9]	Burris, S.; Nelson, E., Embedding the dual of π_{∞} in the lattice of equation class of semigroups, Algebra universalis, 1, 248-253, (1971) · Zbl 0227.08006
[10]	Crochemore, M., Sharp characterizations of squarefree morphisms, Theoret. comput. sci., 18, 221-226, (1982) · Zbl 0482.68085
[11]	Déjean, F., Sur un théorème de thue, J. combin. theory ser. A, 13, 90-99, (1972) · Zbl 0245.20052
[12]	Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of square-free D0L languages, Theoret. comput. sci., 16, 25-32, (1981) · Zbl 0481.68073
[13]	Ehrenfeucht, A.; Rozenberg, G., Repetition of subwords in D0L languages, Inform. and control, 59, 13-35, (1983) · Zbl 0549.68076
[14]	Eilenberg, S., ()
[15]	Fife, E.D., Binary sequences which contain no bbb, Trans. amer. math. soc., 261, 115-136, (1980) · Zbl 0464.05018
[16]	Fife, E.D., Irreducible binary sequences, (), 91-99
[17]	Gantmacher, F.R., Application of the theory of matrices, (1959), Interscience New York · Zbl 0085.01001
[18]	Gottschalk, W.H.; Hedlund, G.A., A characterization of the Morse minimal set, (), 70-74 · Zbl 0134.42203
[19]	Govorov, V.E., Graded algebras, Mat. zametki, 12, 197-204, (1972)
[20]	Head, T., The adherences of languages as topological spaces, (), 147-163
[21]	Hedlund, G.A., Remarks on the work of axel thue on sequences, Nordisk mat. tidskr., 16, 148-150, (1967) · Zbl 0153.33101
[22]	Karhumäki, J., On cube-free ω-words generated by binary morphisms, Discrete appl. math., 5, 279-297, (1983) · Zbl 0505.03022
[23]	Kim, K.H.; Putcha, M.S.; Roush, F.W., Some combinatorial properties of free semigroups, J. London math. soc., 16, 397-402, (1977) · Zbl 0368.20036
[24]	Kobayashi, Y., Filtered monoids, graded monoids and the Hilbert series, (), 13-19
[25]	Kuich, W., On the entropy of context-free languages, Inform. and control, 16, 173-200, (1970) · Zbl 0193.32603
[26]	Leech, J., A problem on strings of beads, Math. gaz., 41, 277-278, (1957) · Zbl 0079.01101
[27]	Morse, M., Recurrent geodesics on a surface of negative curvature, Trans. amer. math. soc., 22, 84-100, (1921) · JFM 48.0786.06
[28]	Morse, M.; Hedlund, G.A.; Morse, M.; Hedlund, G.A., Symbolic dynamics II, Amer. J. math., Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[29]	Novikov, P.S., On periodic groups, Dokl. akad. nauk SSSR, 127, 749-752, (1959) · Zbl 0119.02202
[30]	Pansiot, J.-J., A propos d’une conjecture de F. Déjean sur LES répétitions dans LES mots, Discrete appl. math., 7, 297-311, (1984) · Zbl 0536.68072
[31]	Pleasants, P.A.B., Nonrepetitive sequences, (), 267-274 · Zbl 0237.05010
[32]	Prodinger, H.; Urbanek, F.J., Infinite 0-1-sequences without long adjacent identical blocks, Discrete math., 28, 277-289, (1979) · Zbl 0421.05007
[33]	Restivo, A.; Salemi, S., Overlap free words on two symbols, (), 198-206
[34]	Restivo, A.; Salemi, S., Some decision results on nonrepetitive words, (), 289-295
[35]	Salomaa, A., Morphisms on free monoids and language theory, (), 141-166
[36]	Salomaa, A., Jewels of formal language theory, (1981), Computer Science Press Rockville, MD · Zbl 0487.68063
[37]	Séébold, P., Overlap-free sequences, (), 207-215
[38]	Shelton, R.O.; Soni, R.P.; Shelton, R.O.; Soni, R.P.; Shelton, R.O.; Soni, R.P., Aperiodic words on three symbols, III, J. reine angew. math., J. reine angew. math., J. reine angew. math., 330, 44-52, (1982) · Zbl 0467.05010
[39]	Shelton, R.O., On the structure and extendibility of square-free words, (), 101-118 · Zbl 0561.68054
[40]	Thue, A., Über unendliche zeichenreihe, Norske vid. selsk. skr. I, math. nat. kl. christiana, VII, 1-22, (1906)
[41]	Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichrenreihen, Norske vid. selsk. skr. I, math. nat. kl. christiana, I, 1-67, (1912) · JFM 44.0462.01
[42]	Willard, S., General topology, (1970), Addison-Wesley Reading, MA · Zbl 0205.26601