Euclidean algorithm for a class of linear orders

DOI10.1016/J.DISC.2023.113639MaRDI QIDQ6056733zbMATH OpenFDO

Authors Shashwat Agrawal, Amit Kuber, Esha Gupta

Publication date 4 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

discrete linear order Euclidean algorithm finitely presented linear order isomorphism problem signed trees

Mathematics Subject Classification ID

Total orders (06A05)

Abstract: Borrowing inspiration from Marcone and Mont'{a}lban's one-one correspondence between the class of signed trees and the equimorphism classes of indecomposable scattered linear orders, we find a subclass of signed trees which has an analogous correspondence with equimorphism classes of indecomposable finite rank discrete linear orders. We also introduce the class of emph{finitely presented linear orders}-- the smallest subclass of finite rank linear orders containing

m a t h b f 1

,

o m e g a

and

o m e g a^{*}

and closed under finite sums and lexicographic products. For this class we develop a generalization of the Euclidean algorithm where the emph{width} of a linear order plays the role of the Euclidean norm. Using this as a tool we classify the isomorphism classes of finitely presented linear orders in terms of an equivalence relation on their presentations using emph{3-signed trees}.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Euclidean algorithm for a class of linear orders

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