Article ID Journal Published Year Pages File Type
434343 Theoretical Computer Science 2014 18 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,