Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434343 | Theoretical Computer Science | 2014 | 18 Pages |
Abstract
We prove that the isomorphism of scattered tree-automatic linear orders as well as the existence of automorphisms of scattered word-automatic linear orders are undecidable. For the existence of automatic automorphisms of word- or tree-automatic linear orders, we determine the exact level of undecidability in the arithmetical hierarchy.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dietrich Kuske,