The subword complexity of a two-parameter family of sequences
type: Item
instance of: scholarly article
title: The subword complexity of a two-parameter family of sequences
zbMATH Open document ID: 0981.68125
author: Aviezri S. Fraenkel
author: Tamar Seeman
author: Jamie Simpson
published in: The Electronic Journal of Combinatorics
publication date: 2001-10-16T00:00:00Z
full work available at URL: https://eudml.org/doc/121682
full work available at URL: v8i2r10.html
review text: Summary: We determine the subword complexity of the characteristic functions of a two-parameter family \(\{A_n\}_{n=1}^\infty\) of infinite sequences \hfil\break which are associated with the winning strategies for a family of 2-player games. A special case of the family has the form \(A_n=\lfloor n\alpha\rfloor\) for all \(n\in {\mathbb{Z}}_{>0}\), where \(\alpha\) is a fixed positive irrational number. The characteristic functions of such sequences have been shown to have subword complexity \(n+1\). We show that every sequence in the extended family has subword complexity \(O(n)\).
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1638988
zbMATH Keywords: subword complexity
MaRDI profile type: MaRDI publication profile
Recommended article: Sequences with subword complexity \(2n\)
Recommended article: On the character of words of sublinear complexity
Recommended article: On the joint subword complexity of automatic sequences
Recommended article: Complexity functions for two-dimensional sequences
Recommended article: Complexity for finite factors of infinite sequences
description: scientific article; zbMATH DE number 1638988