Name
Abstract | ||
|---|---|---|
We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega(omega). Moreover, we make a step towards proving that the ranks of tree-automatic well-founded partial orders are bounded by omega(omega omega): we prove this bound for what we call upwards linear partial orders. As an application of our result, we show that the isomorphism problem for tree-automatic well-founded trees is complete for level Delta(0)(omega omega) of the hyperarithmetical hierarchy with respect to Turing-reductions. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.2168/LMCS-9(2:10)2013 | LOGICAL METHODS IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
hyperarithmetical hierarchy,isomorphism problem,ordinal rank,tree-automatic structures,well-founded trees | Journal | 9 |
Issue | ISSN | Citations |
2 | 1860-5974 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Huschenbett | 1 | 10 | 3.11 |
| Alexander Kartzow | 2 | 54 | 7.41 |
| Jiamou Liu | 3 | 49 | 23.19 |
| Markus Lohrey | 4 | 903 | 75.40 |