The isomorphism problem for tree-automatic ordinals with addition

Sanjay Jain; Bakhadyr Khoussainov; Philipp Schlicht; Frank Stephan

doi:10.1016/j.ipl.2019.05.004

The isomorphism problem for tree-automatic ordinals with addition

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

^*Corresponding author for this work

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

34 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 language	English
Pages (from-to)	19-24
Number of pages	6
Journal	Information Processing Letters
Volume	149
Early online date	29 May 2019
DOIs	https://doi.org/10.1016/j.ipl.2019.05.004
Publication status	Published - 1 Sep 2019

Keywords

Automatic structures
Ordinals
Theory of computation
Tree-automatic structures

Access to Document

10.1016/j.ipl.2019.05.004

Full-text PDF (accepted author manuscript)
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, 175 KBLicence: CC BY-NC-ND

Cite this

@article{3645c515886b4e0ebf21783b17f03feb,

title = "The isomorphism problem for tree-automatic ordinals with addition",

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.",

keywords = "Automatic structures, Ordinals, Theory of computation, Tree-automatic structures",

author = "Sanjay Jain and Bakhadyr Khoussainov and Philipp Schlicht and Frank Stephan",

year = "2019",

month = sep,

day = "1",

doi = "10.1016/j.ipl.2019.05.004",

language = "English",

volume = "149",

pages = "19--24",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "North-Holland Publishing Company",

}

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 -

The isomorphism problem for tree-automatic ordinals with addition

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this