Classification of Finite Coloured Linear Orderings

摘要

This paper concerns the classification of finite coloured linear orders up to n-equivalence. Ehrenfeucht-Fraisse 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 ordering of 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.