On defining linear orders by automata
Moscow Journal of Combinatorics and Number Theory, 9 (3):
253-291 (2020)Preprint: <a href="https://hal.archives-ouvertes.fr/hal-02397982/">Link</a><br>#journal.DOI: 10.2140/moscow.2020.9.253
Abstract
We define linear orders ≤Z on product sets Z := X1 × X2 × ... × Xn and on subsets Z of X1 × X2 where each composing set Xi is 0, p or N, and ordered in the natural way. We require that (Z, ≤Z) be isomor-phic to (N, ≤) if it is infinite. We want linear orderings of Z such that, in two consecutive tuples z = (z1, ..., zn) and z = (z 1 , ..., z n), we have |zi − z i | ≤ 1 for each i. Furthermore, we define their distance d(z, z) as the number of indices i such that zi = z i. We will consider orderings where the distance of two consecutive tuples is at most 2. We are interested in algorithms that determine the tuple in Z following z by using local information, where "local" is meant with respect to graphs associated with Z, and that work as well for finite and infinite components Xi, without knowing whether the components Xi are finite or not. We will formalize these algorithms by deterministic graph-walking automata.