The isomorphism problem for tree-automatic ordinals with addition

Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht*, Frank Stephan

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

36 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)19-24
Number of pages6
JournalInformation Processing Letters
Volume149
Early online date29 May 2019
DOIs
Publication statusPublished - 1 Sep 2019

Keywords

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

Fingerprint Dive into the research topics of 'The isomorphism problem for tree-automatic ordinals with addition'. Together they form a unique fingerprint.

Cite this