Generalized Davenport-Schinzel sequences with linear upper bound
type: Item
instance of: scholarly article
title: Generalized Davenport-Schinzel sequences with linear upper bound
zbMATH Open document ID: 0768.05007
DOI: 10.1016/0012-365X(92)90677-8
author: Radek Adamec
author: Martin Klazar
author: Pavel Valtr
published in: Discrete Mathematics
publication date: 1993-01-17T00:00:00Z
review text: If a sequence of symbols from an \(n\)-letter alphabet has no immediate repetition of the same letter and does not contain a subsequence of the form \(ababa\) then it is a Davenport-Schinzel sequence. The authors generalize this notion in two aspects: 1) No immediate repetition is replaced by \(k\)-regularity (i.e. the number of different symbols among \(k\) consecutive symbols from the sequence is \(k\)). 2) The forbidden pattern \(ababa\) is replaced by an arbitrary pattern. The key problem is to determine the maximum length of such sequences with respect to the size of the alphabet \(n\) and the forbidden pattern \(f\). The main result is that the maximum length is of order \(n\) if and only if the forbidden pattern \(f\) has no subsequence of the form \(ababa\).
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 97504
zbMATH Keywords: Davenport-Schinzel sequence
zbMATH Keywords: maximum length
zbMATH Keywords: forbidden pattern
reviewed by: Herman J. Tiersma
MaRDI profile type: Publication
cites work: A Combinatorial Problem Connected with Differential Equations
cites work: A combinatorial problem connected with differential equations II
cites work: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
cites work: Almost linear upper bounds on the length of general Davenport-Schinzel sequences
cites work: Planar realizations of nonlinear Davenport-Schinzel sequences by segments
cites work: On a problem of Davenport and Schinzel
cites work: Efficiency of a Good But Not Linear Set Union Algorithm
cites work: Q4010349
cites work: A simplified construction of nonlinear Davenport-Schinzel sequences
Wikidata QID: Q126529479
description: scientific article; zbMATH DE number 97504