The isomorphism problem for tree-automatic ordinals with addition

DOI10.1016/J.IPL.2019.05.004MaRDI QIDQ2274485zbMATH OpenOpenAlexFDO

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

Publication date 20 September 2019

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.13153

zbMATH Keywords

automatic structuresordinalstheory of computationtree-automatic structures

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Ordinal and cardinal numbers (03E10) Formal languages and automata (68Q45)

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.

Recommendations

• Automatic linear orders and trees
• Tree Automata Make Ordinal Theory Easy
• The isomorphism problem on classes of automatic structures with transitive relations
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees

Cites work

• A hierarchy of tree-automatic structures
• Automata on ordinals and automaticity of linear orders
• Automata Presenting Structures: A Survey of the Finite String Case
• Automata-based presentations of infinite structures
• Automatic linear orders and trees
• Automaticity of ordinals and of homogeneous graphs
• Describing Groups
• FA-presentable groups and rings
• Finite presentations of infinite structures: Automata and interpretations
• scientific article; zbMATH DE number 3136760 (Why is no real title available?)
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• Is Cantor's theorem automatic?
• Isomorphisms of scattered automatic linear orders
• Set Theory
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• Three lectures on automatic structures
• Tree-automatic scattered linear orders

Cited in

(6)

• Isomorphism of regular trees and words
• scientific article; zbMATH DE number 5560465 (Why is no real title available?)
• Algebraic ordinals
• Tree Automata Make Ordinal Theory Easy
• The isomorphism relation between tree-automatic structures
• Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by

This page was built for publication: The isomorphism problem for tree-automatic ordinals with addition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274485)