✦ LIBER ✦

On words containing all short subwords

✍ Scribed by Ioan Tomescu

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 317 KB
Volume: 197
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00231-4

No coin nor oath required. For personal study only.

✦ Synopsis

Lutz Priese raised the following conjecture: Almost all words of length n over a finite alphabet A with m letters contain as subwords all words of length [log log n] over A as n -+ co. In this note we prove that this property holds for subwords of length k(n) over A provided lim,, m k(n)/logn = 0.

📜 SIMILAR VOLUMES

On subwords of infinite words

✍ Lucian Ilie 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 175 KB

On the number of occurrences of all shor

On the number of occurrences of all short factors in almost all words

✍ Ioan Tomescu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 93 KB

Short strings containing all k-element p

Short strings containing all k-element permutations

✍ Carla Savage 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Given n and k, we consider the problem of conslructing a shortest string over the, set ~. ={1,2 ..... n} which contains every permulation of each k-element subset of ~, as a scbsequence. Let g(n, k) denote the length of a shorte,;t such string. We show by construction tic, a: g(n, k) <~ k(n -2) + 4

On strings containing all subsets as sub

On strings containing all subsets as substrings

✍ Witold Lipski Jr. 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 998 KB

Let s,, be the length of a shortest sequence cf positive integers which contains every Yc(l,..., d}-as a subsequence of IY 1 consecutive terms. We give the following asymptotic estimation\* (2/7rnY22" d S . n Q (2/7r)2". TIC. upper bound is derived constructively.

Almost all one-rule thue systems have de

Almost all one-rule thue systems have decidable word problems

✍ Ronald V Book; Craig C Squier 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 167 KB

The decidability of the word problem for one-rule Thue systems is an open cluestion. In the case of one-rule special Thue systems, i.e., those of the form {(w, 1)} where 1 is the identity, it is known [1] that the word problem is decidable. Here we show that 'almost all' one-rule Thue systems have

On a subgroup contained in some words wi

On a subgroup contained in some words with a bounded length

✍ Yahya Ould Hamidoune 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 315 KB

Hamidoune, Y.O., On a subgroup contained in some words with a bounded length, Discrete Mathematics 103 (1992) 171-176. Let G be a group and let A and B be two finite nonvoid subsets of G such that 1$ B. Using results of Kemperman, we show that either IA U B U ABl b IAl + IBI or there exists a nonnul