A simplified construction of nonlinear Davenport-Schinzel sequences

DOI10.1016/0097-3165(88)90055-6zbMath0673.05001OpenAlexW2070057062WikidataQ56545264 ScholiaQ56545264MaRDI QIDQ1120575

Péter Komjáth

Publication date: 1988

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(88)90055-6

zbMATH Keywords

length of words without repeated subwords

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items (6)

Generalized Davenport-Schinzel sequences ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ Enumerating Davenport-Schinzel sequences ⋮ Davenport-Schinzel theory of matrices ⋮ Generalized Davenport-Schinzel sequences with linear upper bound ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts

Cites Work

• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• On a problem of Davenport and Schinzel
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Combinatorial Problem Connected with Differential Equations
• A combinatorial problem connected with differential equations II
• Unnamed Item

This page was built for publication: A simplified construction of nonlinear Davenport-Schinzel sequences