Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kuske, Dietrich http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-36906
URL:

Isomorphisms of scattered automatic linear orders

pdf-format:


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.

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 =		{http://dx.doi.org/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: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI