The order type of scattered context-free orderings of rank one is computable

DOI10.1007/978-3-030-38919-2_23MaRDI QIDQ3297776zbMATH OpenOpenAlexFDO

Authors Kitti Gelle, Szabolcs Iván

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Total orders (06A05) Formal languages and automata (68Q45)

Abstract: A linear ordering is called context-free if it is the lexicographic ordering of some context-free language and is called scattered if it has no dense subordering. Each scattered ordering has an associated ordinal, called its rank. It is known that the isomorphism problem of scattered context-free orderings is undecidable, if one of them has a rank at least two. In this paper we show that it is decidable whether a context-free ordering has rank at most one, and if so, its order type is effectively computable.

Recommendations

• Hausdorff rank of scattered context-free linear orders
• An undecidable property of context-free linear orders
• A context-free linear ordering with an undecidable first-order theory
• Isomorphisms of scattered automatic linear orders
• Tree-automatic scattered linear orders

Cites work

• Algebraic ordinals
• An undecidable property of context-free linear orders
• Hausdorff rank of scattered context-free linear orders
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3675332 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 7453084 (Why is no real title available?)
• Isomorphism of regular trees and words
• Scattered Context-Free Linear Orderings
• The equational theory of regular words
• The ordinal generated by an ordinal grammar is computable

Cited in

(6)

• An undecidable property of context-free linear orders
• The ordinal generated by an ordinal grammar is computable
• Hausdorff rank of scattered context-free linear orders
• A context-free linear ordering with an undecidable first-order theory
• Algebraic linear orderings
• Scattered Context-Free Linear Orderings

This page was built for publication: The order type of scattered context-free orderings of rank one is computable

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