Non-dominating Sequences of Vectors Using only Resets and Increments

Article type: Research Article

Authors: Czerwiński, Wojciech^{a; *} | Gogacz, Tomasz^b | Kopczyński, Eryk^c

Affiliations: [a] Institute of Computer Science, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. wczerwin@duch.mimuw.edu.pl | [b] Institute of Computer Science, University of Wrocław, Joliot-Curie 15, Wrocław, Poland. gogo@cs.uni.wroc.pl | [c] Institute of Computer Science, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. erykk@mimuw.edu.pl

Note: [*] Address for correspondence: Institute of Computer Science, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland.

Abstract: We consider sequences of vectors from ℕd. Each coordinate of a vector can be reset or incremented by 1 with respect to the same coordinate of the preceding vector. We give an example of non-dominating sequence, like in Dickson’s Lemma, of length 22θ(n), what matches the previously known upper bound.

Keywords: Dickson’s Lemma

DOI: 10.3233/FI-2015-1247

Journal: Fundamenta Informaticae, vol. 140, no. 2, pp. 123-127, 2015