Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2016.02.008 | Theor. Comput. Sci. |
Keywords | Field | DocType |
Tree automata,Linear orders,Automatic structures | Discrete mathematics,Range tree,Combinatorics,Tree traversal,K-ary tree,Binary tree,Order statistic tree,Tree structure,Random binary tree,Mathematics,Interval tree | Journal |
Volume | Issue | ISSN |
626 | C | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjay Jain | 1 | 1647 | 177.87 |
| Bakhadyr Khoussainov | 2 | 604 | 72.96 |
| Philipp Schlicht | 3 | 17 | 10.14 |
| Frank Stephan | 4 | 329 | 34.02 |