About: Davenport-Schinzel sequence

Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Davenport-Schinzel sequence Sponge Permalink

An Entity of Type : owl:Thing, within Data Space : 134.155.108.49:8890 associated with source dataset(s)

Davenport-Schinzel sequences are sequences that give rise to a hierarchy of functions that grow extremely close to linearly. An \((n,s)\) Davenport-Schinzel sequence is a sequence \(a_1,a_2,\ldots,a_m\) where \(a_i\) are integers in \([1,n]\), such that: * \(a_i eq a_{i+1}\) * There is no sequence \(i_1 < i_2 < \cdots < i_{s + 2}\) such that \(a_{i_1} = a_{i_3} = a_{i_5} = \ldots eq a_{i_2} = a_{i_4} = a_{i_6} = \ldots\).

Attributes	Values
rdfs:label	Davenport-Schinzel sequence
rdfs:comment	Davenport-Schinzel sequences are sequences that give rise to a hierarchy of functions that grow extremely close to linearly. An \((n,s)\) Davenport-Schinzel sequence is a sequence \(a_1,a_2,\ldots,a_m\) where \(a_i\) are integers in \([1,n]\), such that: * \(a_i eq a_{i+1}\) * There is no sequence \(i_1 < i_2 < \cdots < i_{s + 2}\) such that \(a_{i_1} = a_{i_3} = a_{i_5} = \ldots eq a_{i_2} = a_{i_4} = a_{i_6} = \ldots\).
dcterms:subject	Functions Combinatorics
abstract	Davenport-Schinzel sequences are sequences that give rise to a hierarchy of functions that grow extremely close to linearly. An \((n,s)\) Davenport-Schinzel sequence is a sequence \(a_1,a_2,\ldots,a_m\) where \(a_i\) are integers in \([1,n]\), such that: * \(a_i eq a_{i+1}\) * There is no sequence \(i_1 < i_2 < \cdots < i_{s + 2}\) such that \(a_{i_1} = a_{i_3} = a_{i_5} = \ldots eq a_{i_2} = a_{i_4} = a_{i_6} = \ldots\). Define \(\lambda_s(n)\) as the length of the longest \((n,s)\) Davenport-Schinzel sequence. Then \(\lambda_1(n) = n\), \(\lambda_2(n) = 2n - 1\), \(\lambda_3(n) = \Theta(n\alpha(n))\) where \(\alpha\) is the inverse Ackermann function. A large number function can be extracted by defining \( ext{DS}_3(n) = \min\{m : \lambda_3(m) \geq mn\}\).

OpenLink Virtuoso version 07.20.3217, on Linux (x86_64-pc-linux-gnu), Standard Edition
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2012 OpenLink Software