On optimal representatives of finite coloured linear orders (Q1732807)

A colored linear order \((A, <, F)\) is a linear order \((A, <)\) equipped with a mapping \(F: A\to C\) where \(C\) is a set (of colors). Two colored linear orders are \(n\)-equivalent, written \(A\equiv_n B\), if Player 2 wins the \(n\)-move Ehrenfeucht-Fraïssé game. Starting with a finite colored linear order \(A\), the paper describes how to determine if the \(\equiv_2\)-class of \(A\) is finite or infinite. The paper gives an algorithm to locate an optimal (= smallest) member of the \(\equiv_2\)-class of \(A\). The algorithm starts with a colored linear order \(A\) and successively removes pieces, retaining \(2\)-equivalence, until an optimal colored linear order is found in the \(\equiv_2\)-class of \(A\). One consequence of the algorithm is that, if \(A\) is a finite colored linear order, then there is a \textit{suborder} of \(A\) that is an optimal member of the \(\equiv_2\)-class of \(A\). In the final section of the paper, the authors explain why it may be that a finite linear order \(A\) may not contain a suborder that is an optimal member of the \(\equiv_3\)-class of \(A\).