Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.455
URN: urn:nbn:de:0030-drops-36906
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3690/
Kuske, Dietrich
Isomorphisms of scattered automatic linear orders
| pdf-format: |
|
Abstract
We prove the undecidability of the existence of an isomorphism betweenscattered 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.
BibTeX - Entry
@InProceedings{kuske:LIPIcs:2012:3690,
author = {Dietrich Kuske},
title = {{Isomorphisms of scattered automatic linear orders}},
booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
pages = {455--469},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-42-2},
ISSN = {1868-8969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3690},
URN = {urn:nbn:de:0030-drops-36906},
doi = {10.4230/LIPIcs.CSL.2012.455},
annote = {Keywords: Automatic structures, isomorphism, automorphism}
}
| Keywords: | Automatic structures, isomorphism, automorphism | |
| Seminar: | Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL | |
| Issue date: | 2012 | |
| Date of publication: | 03.09.2012 |
