Isomorphisms of scattered automatic linear orders

Author Dietrich Kuske



PDF
Thumbnail PDF

File

LIPIcs.CSL.2012.455.pdf
  • Filesize: 1.08 MB
  • 15 pages

Document Identifiers

Author Details

Dietrich Kuske

Cite AsGet BibTex

Dietrich Kuske. Isomorphisms of scattered automatic linear orders. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 455-469, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.CSL.2012.455

Abstract

We prove the undecidability of the existence of an isomorphism between scattered tree-automatic linear orders as well as the existence of automorphisms of scattered word automatic linear orders. For the existence of automatic automorphisms of word automatic linear orders, we determine the exact level of undecidability in the arithmetical hierarchy.
Keywords
  • Automatic structures
  • isomorphism
  • automorphism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail