LIPIcs.CSL.2012.455.pdf
- Filesize: 1.08 MB
- 15 pages
Document
Isomorphisms of scattered automatic linear orders
Author
-
Part of:
Volume:
Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (CSL 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-09-03
Cite As Get 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.
Subject Classification
Keywords
- Automatic structures
- isomorphism
- automorphism
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads