On subword complexity functions
type: Item
instance of: scholarly article
title: On subword complexity functions
zbMATH Open document ID: 0562.68060
DOI: 10.1016/0166-218X(84)90102-1
author: Anni Sajo
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: The author finds a polynomial formula for the subword complexity function of a cyclic language. A characterization of context-free languages with exponential subword complexity is derived by appropriately using the pumping lemma.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3896327
zbMATH Keywords: subword complexity
zbMATH Keywords: cyclic language
zbMATH Keywords: context-free languages
reviewed by: H. Luchian
MaRDI profile type: Publication
cites work: Subword complexities of various classes of deterministic developmental languages without interactions
cites work: Q4140407
cites work: Q5678435
description: scientific article; zbMATH DE number 3896327