On Optimal Representatives of Finite Coloured Linear Orders

Abstract

Two structures A and B are n-equivalent if player II has a winning strategy in the n-move Ehrenfeucht-Fra¨ıss´e game on A and B. We extend earlier results about equivalence classes for finite colored linear orders, describing an algorithm for reducing to canonical form under 2-equivalence, and concentrating on the cases of 2 and 3 moves