On the length of word chains
type: Item
instance of: scholarly article
title: On the length of word chains
zbMATH Open document ID: 0654.68096
DOI: 10.1016/0020-0190(87)90031-7
author: Jean Berstel
author: Srečko Brlek
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: Word chains are an extension of addition chains to words. We show that over a q-letter alphabet, any long enough word admits a word chain of length at most \((1+\epsilon)n/\log_ q n\), for a fixed arbitrary \(\epsilon >0\); there exist words with no chain shorter than \(n/\log_{q- 1} n\). Several examples are given. Finally, we show that words with few factors have short chains.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 4068326
zbMATH Keywords: D0L-systems
zbMATH Keywords: addition chains
zbMATH Keywords: word chain
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90031-7
OpenAlex ID: W2028460486
cites work: Q5585020
cites work: Q3659988
cites work: Q3689370
cites work: Q4140407
description: scientific article; zbMATH DE number 4068326