Isomorphisms of scattered automatic linear orders

2012/04/25 by Dietrich Kuske, Kuske, Dietrich
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1204.5653

openalex publication_date 2012/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 automatic linear orders, we determine the exact level of undecidability in the arithmetical hierarchy.

Citations

• The FC-rank of a context-free language

Related

• The Isomorphism Problem On Classes of Automatic Structures
• The order type of scattered context-free orderings of rank one is computable
• Isomorphism of regular trees and words
• Word Automaticity of Tree Automatic Scattered Linear Orderings Is\n Decidable
• Structures Without Scattered-Automatic Presentation