Modified complexity and *-Sturmian word
type: Item
instance of: scholarly article
title: Modified complexity and *-Sturmian word
zbMATH Open document ID: 0928.11012
author: Izumi Nakashima
author: Jun-ichi Tamura
author: Shin-ichi Yasutomi
published in: Proceedings of the Japan Academy. Series A
publication date: 2000-01-17T00:00:00Z
review text: The authors introduce a new notion of complexity \(p^*\) for an infinite sequence over a finite alphabet. Instead of counting all the factors (blocks) of given length occurring in the sequence, they count all the blocks of given length that occur infinitely often in the sequence. Accordingly they define *-Sturmian words. For a sequence indexed by \(\mathbb{N}\) these are exactly the sequences for which \(p^*(n)\leq n+1\) \(\forall n\geq 1\). The paper announces many interesting results.
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1335028
zbMATH Keywords: block-complexity
zbMATH Keywords: Sturmian sequences
zbMATH Keywords: infinite sequence
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
full work available at URL: pjaa.75.26
OpenAlex ID: W2002327233
cites work: Sequences with minimal block growth
cites work: Symbolic Dynamics II. Sturmian Trajectories
cites work: The continued fraction expansion of α with μ(α) = 3
DOI: 10.3792/PJAA.75.26
description: scientific article; zbMATH DE number 1335028