Nondecreasing subsequences of t-sequences

DOI10.1016/0012-365X(90)90036-HMaRDI QIDQ908917zbMATH OpenFDO

Authors Tat-Hung Chan

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(90)90036-H

zbMATH Keywords

1-VASSsalgorithmic complexity

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Sequences and sets (11B99)

Review text

A sequence of nonnegative integers is called a t-sequence if consecutive elements differ by no more than 1. The integer g(m,n) is the smallest k such that every t-sequence of length k starting with m contains a nondecreasing subsequence of length n. The author demonstrates, with elementary arguments, that \(g(m,n)=n(n-1)/2+m(n-1)+1.\) This function is related to the longest path in a tree construction algorithm used to solve the boundedness problem for one-dimensional vector addition systems with states.

Recommendations

• Long finite sequences
• scientific article; zbMATH DE number 1092064
• Elementary sequences, sub-Fibonacci sequences
• Extremal functions for sequences
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes

Cites work

• A multiparameter analysis of the boundedness problem for vector addition systems
• Parallel program schemata

Cited in

(3)

• The reverse mathematics of non-decreasing subsequences
• Non-dominating sequences of vectors using only resets and increments
• Long finite sequences

This page was built for publication: Nondecreasing subsequences of t-sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908917)