#### Vol. 9, No. 3, 2020

 Recent Issues Volume 13, Issue 3 Volume 13, Issue 2 Volume 13, Issue 1 Volume 12, Issue 4 Volume 12, Issue 3 Volume 12, Issue 2 Volume 12, Issue 1 Volume 11, Issue 4 Volume 11, Issue 3 Volume 11, Issue 2 Volume 11, Issue 1 Volume 10, Issue 4 Volume 10, Issue 3 Volume 10, Issue 2 Volume 10, Issue 1 Volume 9, Issue 4 Volume 9, Issue 3 Volume 9, Issue 2 Volume 9, Issue 1 Volume 8, Issue 4 Volume 8, Issue 3 Volume 8, Issue 2 Volume 8, Issue 1
 Older Issues Volume 7, Issue 4 Volume 7, Issue 3 Volume 7, Issue 2 Volume 7, Issue 1 Volume 6, Issue 4 Volume 6, Issue 2-3 Volume 6, Issue 1 Volume 5, Issue 4 Volume 5, Issue 3 Volume 5, Issue 1-2 Volume 4, Issue 4 Volume 4, Issue 3 Volume 4, Issue 2 Volume 4, Issue 1 Volume 3, Issue 3-4 Volume 3, Issue 2 Volume 3, Issue 1 Volume 2, Issue 4 Volume 2, Issue 3 Volume 2, Issue 2 Volume 2, Issue 1 Volume 1, Issue 4 Volume 1, Issue 3 Volume 1, Issue 2 Volume 1, Issue 1
 The Journal About the journal Ethics and policies Peer-review process Submission guidelines Submission form Editorial board founded and published with the scientific support and advice of mathematicians from the Moscow Institute of Physics and Technology Subscriptions ISSN (electronic): 2996-220X ISSN (print): 2996-2196 Author Index To Appear Other MSP Journals
On defining linear orders by automata

### Bruno Courcelle, Irène Durand and Michael Raskin

Vol. 9 (2020), No. 3, 253–291
##### Abstract

Motivated by enumeration problems, we define linear orders ${\le }_{Z}$ on Cartesian products $Z:={X}_{1}×{X}_{2}×\cdots ×{X}_{n}$ and on subsets of ${X}_{1}×{X}_{2}$ where each component set ${X}_{i}$ is $\left[0,p\right]$ or $ℕ$, ordered in the natural way. We require that $\left(Z,{\le }_{Z}\right)$ be isomorphic to $\left(ℕ,\le \right)$ if it is infinite. We want linear orderings of $Z$ such that, in two consecutive tuples $z$ and ${z}^{\prime }$, at most two components differ, and they differ by at most 1.

We are interested in algorithms that determine the next tuple in $Z$ by using local information, where “local” is meant with respect to certain graphs associated with $Z$. We want these algorithms to work as well for finite and infinite components ${X}_{i}$. We will formalise them by deterministic graph-walking automata and compare their enumeration powers according to the finiteness of their sets of states and the kinds of moves they can perform.

##### Keywords
enumeration algorithm, diagonal enumeration, graph-walking automaton, linear order
##### Mathematical Subject Classification 2010
Primary: 06A05, 05C38, 68R10, 68P10