Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-27T10:56:00.188Z Has data issue: false hasContentIssue false
  • English
  • Français

Unavoidable regularities and factor permutations of words

Published online by Cambridge University Press:  14 November 2011

W. L. Fouché
W. L. Fouché
Affiliation:
Department of Mathematics and Applied Mathematics, University of Pretoria, 0002 Pretoria, South Africa
Get access Rights & Permissions [Opens in a new window]

Extract

We show that for every finite set A and for every natural number n, there exists a natural number N such that every word of length N over the alphabet A has, for every permutation π of the numbers 1,…,n, a representation of the form Xw1 … wnzwπ(1) … wπ(n) Y, where X, Y are words and w1,…,wn, z are nonempty words over A.

Type
Research Article
Information
Proceedings of the Royal Society of Edinburgh Section A: Mathematics , Volume 125 , Issue 3 , 1995 , pp. 519 - 524
Copyright
Copyright © Royal Society of Edinburgh 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Bean, D. R., Ehrenfeucht, A. and McNulty, G. F.. Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979), 261–94.CrossRefGoogle Scholar
2Lothaire, M.. Combinatorics on Words (Reading, Mass.: Addison-Wesley, 1983).Google Scholar
3Rose, H. E.. Subrecursion: Functions and Hierarchies (Oxford: Clarendon Press, 1984).Google Scholar
4Shirshov, A. I.. On certain non associative nil rings and algebraic algebras. Mat. Sb. 41 (1957), 381–94.Google Scholar