Classification of Finite Coloured Linear Orderings

Abstract

This paper concerns the classification of finite coloured linear orders up to n-equivalence. Ehrenfeucht–Fraïssé games are used to define what this means, and also to help analyze such structures. We give an explicit bound for the least number g(m, n) such that any finite m-coloured linear order is n-equivalent to some orderingof size ≤ g(m, n), from which it follows that g is computable. We give exact values for g(m, 1) and g(m, 2). The method of characters is developed and used.