Skip to content

The isomorphism problem for tree-automatic ordinals with addition

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)19-24
Number of pages6
JournalInformation Processing Letters
Volume149
Early online date29 May 2019
DOIs
DateAccepted/In press - 27 May 2019
DateE-pub ahead of print - 29 May 2019
DatePublished (current) - 1 Sep 2019

Abstract

This paper studies tree-automatic ordinals (or equivalently, well-founded linearly ordered sets) together with the ordinal addition operation +. Informally, these are ordinals such that their elements are coded by finite trees for which the linear order relation of the ordinal and the ordinal addition operation can be determined by tree automata. We describe an algorithm that, given two tree-automatic ordinals with the ordinal addition operation, decides if the ordinals are isomorphic.

    Research areas

  • Automatic structures, Ordinals, Theory of computation, Tree-automatic structures

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the accepted author manuscript (AAM). The final published version (version of record) is available online via Elsevier at https://doi.org/10.1016/j.ipl.2019.05.004 . Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 174 KB, PDF document

    Embargo ends: 29/05/20

    Request copy

    Licence: CC BY-NC-ND

DOI

View research connections

Related faculties, schools or groups