Davenport-Schinzel sekvenser är sekvenser som inte innehåller förbjudna undersekvenser av alternerande symboler. De uppstår i beräkningen av kuvertet av en uppsättning funktioner. Vi visar att den maximala längden av en Davenport-Schinzel sekvens som består av n symboler är 6(noc(n»), där t1.(n)är den funktionella inversen av Ackermanns funktion, och ökar därför mycket långsamt till oändligheten. Detta uppnås genom att etablera en likvärdighet mellan sådana sekvenser och generaliserade vägkompressionssystem på rotade träd, och sedan genom att analysera dessa system.
I synnerhet är det övre (lägre) kuvertet för en uppsättning n-linjesegment en bitvis linjär funktion som i värsta fall består av linjära (nα(n)-segment Ref.
Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
{'venue': 'Combinatorica', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}