Non-dominating sequences of vectors using only resets and increments

DOI10.3233/FI-2015-1247MaRDI QIDQ3187002zbMATH OpenOpenAlexFDO

Authors Wojciech Czerwiński, Tomasz Gogacz, Eryk Kopczyński

Publication date 15 August 2016

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.05279

zbMATH Keywords

Dickson's lemma

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We consider a variant of Dickson lemma, where each entry of a vector can be reseted or incremented by 1 in respect to the previous one. We give an example of non dominating sequence of length $2^{2^{heta(n)}}$. It perfectly match the previously known upperbound.

Recommendations

• Nondecreasing subsequences of t-sequences
• Numeration of non-decreasing and non-increasing \(n\)-valued serial sequences
• Reset Sequences for Monotonic Automata
• A multidimensional generalization of the Erdős-Szekeres lemma on monotone subsequences.
• scientific article; zbMATH DE number 522852

Cited in

(1)

• On the upper bound for the density of any injective vector

This page was built for publication: Non-dominating sequences of vectors using only resets and increments

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