کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435370 | 689899 | 2016 | 14 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 626, 2 May 2016, Pages 83–96