TY - JOUR
T1 - The isomorphism problem for tree-automatic ordinals with addition
AU - Jain, Sanjay
AU - Khoussainov, Bakhadyr
AU - Schlicht, Philipp
AU - Stephan, Frank
PY - 2019/9/1
Y1 - 2019/9/1
N2 - 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.
AB - 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.
KW - Automatic structures
KW - Ordinals
KW - Theory of computation
KW - Tree-automatic structures
UR - http://www.scopus.com/inward/record.url?scp=85066401260&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2019.05.004
DO - 10.1016/j.ipl.2019.05.004
M3 - Article (Academic Journal)
AN - SCOPUS:85066401260
VL - 149
SP - 19
EP - 24
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
ER -