Tree-automatic scattered linear orders

Abstract

Tree-automatic linear orders on regular tree languages are studied. It is shown that there is no tree-automatic scattered linear order, and therefore no tree-automatic well-order, on the set of all finite labeled trees, and that a regular tree language admits a tree-automatic scattered linear order if and only if for some n, no binary tree of height n can be embedded into the union of the domains of its trees. Hence the problem whether a given regular tree language can be ordered by a scattered linear order or a well-order is decidable. Moreover, sharp bounds for tree-automatic well-orders on some regular tree languages are computed by connecting tree automata with automata on ordinals. The proofs use elementary techniques of automata theory. © 2016 Elsevier B.V.