A simplified construction of nonlinear Davenport-Schinzel sequences
type: Item
instance of: scholarly article
title: A simplified construction of nonlinear Davenport-Schinzel sequences
zbMATH Open document ID: 0673.05001
DOI: 10.1016/0097-3165(88)90055-6
author: Péter Komjáth
published in: Journal of Combinatorial Theory. Series A
publication date: 1988-01-01T00:00:00Z
review text: \textit{H. Davenport} and \textit{A. Schinzel} [Am. J. Math. 57, 684-694 (1965; Zbl 0132.006); Acta Arith. 17, 363-372 (1971; Zbl 0216.302)] haben ein Problem aufgestellt zur Beurteilung der Länge von aus n Buchstaben zusammengesetzten Wörtern mit nicht unmittelbaren Wiederholungen derselben Buchstaben oder Unterwörtern vom Typ abab... der Länge \(s+2\). Die maximale Länge soll mit \(\lambda_ s(n)\) bezeichnet werden. Ein langdauerndes Problem war zu bestimmen, ob \(\lambda_ 3(n)\) linear ist. \textit{S. Hart} und \textit{M. Sharir} [Combinatorica 6, 151-177 (1986; Zbl 0636.05003)] haben das Problem gelöst. Der Zweck dieses Artikels ist, eine direkte Konstruktion für die untere Grenze auszuarbeiten. Es werden zunächst die Begriffe der regulären und singulären Blöcke erörtert, die in den Wörtern vorkommen. Es folgt eine Aussage S(k,m) über eine Zahl \(F_ k(m)\), welche in 7 Punkten die Eigenschaften eines in reguläre und singuläre Blöcke zerlegten Wortes zusammenfaßt. Im Schlußteil des Artikels wird das Problem der unteren Grenzen mittels der Funktionalinverse \(\alpha (n)=\min \{k:\quad n\leq A_ k(k)\}\) der Ackermann-Funktion \(A_ k(m)\) mit den Beziehungen \(A_ 1(m)=2^{m+1},\) \(A_{k+1}(1)=A_ k(2),\) \(A_{k+1}(m+1)=A_ k(A_{k+1}(m)),\) behandelt.
reviewed by: A.Huťa jun
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4101186
zbMATH Keywords: length of words without repeated subwords
Wikidata QID: Q56545264
MaRDI profile type: Publication
full work available at URL: 0097-3165(88)90055-6
OpenAlex ID: W2070057062
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
description: scientific article; zbMATH DE number 4101186