Synchronous orders on the set of integers

Abstract

A binary relation over a free monoid is synchronous if it can be recognized by a synchronous automaton that reads its two tapes simultaneously. We consider the case where the free monoid is generated by a single element (which makes it isomorphic to the additive monoid of integers) and where the binary relation recognized is a strict order. Our main results are: given such an automaton it is possible to determine whether or not is has infinite chains or antichains; we characterize the orders that are linear; given two linear synchronous orders we show how to determine whether or not they are equivalent.