Weakly self-avoiding words and a construction of Friedman
type: Item
instance of: scholarly article
title: Weakly self-avoiding words and a construction of Friedman
zbMATH Open document ID: 0966.68164
author: Jeffrey Shallit
author: Ming-wei Wang
published in: The Electronic Journal of Combinatorics
publication date: 2001-02-19T00:00:00Z
full work available at URL: https://eudml.org/doc/121156
full work available at URL: v8i1n2.html
review text: Summary: H. Friedman obtained remarkable results about the longest finite sequence \(x\) over a finite alphabet such that for all \(i \not= j\) the word \(x[i..2i]\) is not a subsequence of \(x[j..2j]\). In this note we consider what happens when ``subsequence'' is replaced by ``subword''; we call such a sequence a ``weakly self-avoiding word''. We prove that over an alphabet of size \(1\) or \(2\), there is an upper bound on the length of weakly self-avoiding words, while if the alphabet is of size \(3\) or more, there exists an infinite weakly self-avoiding word.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1566551
zbMATH Keywords: weakly self-avoiding word
MaRDI profile type: MaRDI publication profile
Recommended article: On weakly self-avoiding words
Recommended article: Growth problems for avoidable words
Recommended article: Long finite sequences
Recommended article: The length of short words in unavoidable sets
Recommended article: Sequence avoiding any complete word
description: scientific article; zbMATH DE number 1566551