On defining linear orders by automata
Bruno Courcelle, Irène Durand, Mikhail Raskin · Moscow Journal of Combinatorics and Number Theory · 2020
Motivated by enumeration problems, we define linear orders [math] on Cartesian products [math] and on subsets of [math] where each component set [math] is [math] or [math] , ordered in the natural way. We require that [math] be isomorphic to [math] if it is infinite. We want linear orderings of [math] such that, in two consecutive tuples [math] and [math] , at most two components differ, and they differ by at most 1. ¶ We are interested in algorithms that determine the next tuple in [math] by using local information, where “local” is meant with respect to certain graphs associated with [math] . We want these algorithms to work as well for finite and infinite components [math] . 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.