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

Kitti Gelle; Szabolcs Ivan

arxiv: 1907.11573 · v1 · pith:7C5DFDRNnew · submitted 2019-07-26 · 💻 cs.FL

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

Kitti Gelle , Szabolcs Ivan This is my paper

Pith reviewed 2026-05-24 15:15 UTC · model grok-4.3

classification 💻 cs.FL

keywords context-free languagesscattered linear orderingsorder typesdecidabilityHausdorff ranklexicographic ordering

0 comments

The pith

It is decidable whether a context-free ordering has scattered rank at most one, and if so its order type is effectively computable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows a procedure that takes a context-free grammar or automaton and decides whether the induced lexicographic ordering is scattered of Hausdorff rank at most one. When the answer is yes, the same procedure outputs a concrete description of the order type. This matters because the isomorphism problem for scattered context-free orderings is already known to be undecidable once any input has rank two or higher, so the result carves out a computable fragment.

Core claim

A linear ordering is context-free when it arises as the lexicographic ordering of a context-free language. For any such ordering that is scattered and has rank at most one, membership in this class is decidable from a grammar presentation, and the order type itself is effectively computable from the same presentation.

What carries the argument

The lexicographic ordering induced by a context-free language together with the standard Hausdorff derivative process that assigns the scattered rank.

If this is right

Isomorphism is decidable between any two scattered context-free orderings that both have rank at most one.
The order types arising at rank one can be written in a normal form built from finite sums and copies of the integers.
The same decision procedure yields an algorithm that classifies all rank-zero and rank-one cases uniformly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The undecidability threshold for context-free orderings therefore occurs exactly when rank reaches two.
The method may extend to deciding rank for other language classes that induce linear orderings, such as regular languages.
One can test the procedure on the lexicographic ordering of the Dyck language to obtain an explicit order type.

Load-bearing premise

The context-free language is supplied by a grammar or automaton that supports effective manipulation of its lexicographic ordering and the associated scattered rank.

What would settle it

A concrete context-free grammar whose induced ordering has scattered rank exactly one, yet the decision procedure either rejects it or outputs an order type that fails to match the actual ordering.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper proves decidability and effective computation of order type for scattered context-free orderings of rank at most one, cleanly separating it from the undecidable higher-rank cases.

read the letter

The main thing to know is that this paper establishes decidability for whether a scattered context-free ordering has rank at most one, and shows that the order type can be computed effectively in that case. This gives a clean positive result that stops short of the undecidable territory for higher ranks. The new part is the effective procedure for the low-rank case. It separates the rank-1 situation from the known undecidability when rank is two or more, using properties of context-free languages to handle the lexicographic orders and their scattered ranks. The work builds directly on the prior undecidability theorem without circularity. What the paper does well is to identify and resolve this boundary case with a computability claim that appears constructive. If the full proof supplies an algorithm based on grammar analysis or similar, that counts as real progress in organizing the decidability landscape for these orderings. The soft spots are minor at this stage. The abstract does not detail the construction, so one would check in the body whether the decision procedure avoids non-effective choices when manipulating the context-free grammar to determine the rank via successive derivatives. No obvious gaps in the stated claim, but the effectiveness needs to hold for all cases of rank one. This is for readers interested in automata theory, particularly those studying linear orders induced by formal languages. Someone working on isomorphism problems or ordinal ranks in computability would get value from the separation result. It deserves peer review because the result is specific, builds on existing work, and provides a positive decidability outcome worth verifying. Recommendation: send it out for review.

Referee Report

0 major / 2 minor

Summary. The paper claims that it is decidable whether a scattered context-free ordering (i.e., the lexicographic ordering of a context-free language with no dense subordering) has Hausdorff rank at most one; moreover, when the rank is at most one the order type itself is effectively computable from a grammar or automaton presenting the language. This is contrasted with the known undecidability of the isomorphism problem for scattered context-free orderings of rank at least two.

Significance. If the claimed decision procedure and computability result hold, the paper supplies a clean separation between the rank-1 case (decidable and computable) and all higher ranks (undecidable). This supplies a positive algorithmic result at the base of the Hausdorff hierarchy for context-free orderings and may serve as a building block for further work on automatic and context-free linear orders.

minor comments (2)

[Abstract] The abstract states the main theorem clearly but does not name the precise representation of the input (grammar, pushdown automaton, etc.); the body should make this explicit in the first section that defines context-free orderings.
Notation for the rank function and for the effective translation from grammar to order type should be introduced once and used consistently; any ad-hoc notation introduced only in proofs should be avoided.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation to accept the paper. There are no major comments to address.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claim is that rank ≤1 for scattered context-free orderings is decidable with effective order-type computation, building explicitly on an external known undecidability result for rank ≥2. No self-definitional reductions, fitted inputs renamed as predictions, load-bearing self-citations, or ansatz smuggling appear in the stated derivation chain. The result is presented as independent of its own inputs and relies on standard effective manipulations of CFLs and Hausdorff rank, which are external to the paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the claim rests on the standard definitions of context-free languages, lexicographic order, scattered linear orders, and their ordinal ranks; no free parameters or invented entities are mentioned.

axioms (2)

standard math Scattered linear orders admit a well-defined ordinal rank.
Invoked when the paper associates each scattered ordering with its rank.
domain assumption Context-free languages admit effective representations (grammars or automata) that allow algorithmic manipulation of their lexicographic orderings.
Required for the existence of a decision procedure.

pith-pipeline@v0.9.0 · 5607 in / 1255 out tokens · 25965 ms · 2026-05-24T15:15:29.352946+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and Peano axioms from Law of Logic unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

it is decidable whether a context-free ordering has rank at most one, and if so, its order type is effectively computable
IndisputableMonolith/Foundation/AlexanderDuality.lean D=3 from circle linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Hausdorff rank of scattered context-free linear orders

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 1 internal anchor

[1]

Bloom, S.L., Ésik, Z.: Algebraic ordinals. Fundam. Infor m. 99(4), 383–407 (2010). https://doi.org/10.3233/FI-2010-255, https://doi.org/10.3233/FI-2010-255

work page doi:10.3233/fi-2010-255 2010
[2]

Information and Computation 197(1), 55 – 89 (2005)

Bloom, S.L., Ésik, Z.: The equational theory of regu- lar words. Information and Computation 197(1), 55 – 89 (2005). https://doi.org/https://doi.org/10.1016/j.ic .2005.01.004, http://www.sciencedirect.com/science/article/pii/S0890540105000192

work page doi:10.1016/j.ic 2005
[3]

In: M auri, G., Leporati, A

Ésik, Z.: Scattered context-free linear orderings. In: M auri, G., Leporati, A. (eds.) Developments in Language Theory. pp. 216–227. Sprin ger Berlin Heidelberg, Berlin, Heidelberg (2011) 14

work page 2011
[4]

Information Processing Letters 111(3), 107 – 109 (2011)

Ésik, Z.: An undecidable property of context-free linear or- ders. Information Processing Letters 111(3), 107 – 109 (2011). https://doi.org/https://doi.org/10.1016/j.ip l.2010.10.018, http://www.sciencedirect.com/science/article/pii/S0020019010003248

work page doi:10.1016/j.ip 2011
[5]

In: Fernández-Baca, D

Ésik, Z., Iván, S.: Hausdorﬀ rank of scattered context-fr ee linear orders. In: Fernández-Baca, D. (ed.) LATIN 2012: Theoretical Informat ics. pp. 291–302. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)

work page 2012
[6]

The ordinal generated by an ordinal grammar is computable

Gelle, K., Iván, S.: The ordinal generated by an ordinal gr ammar is computable. Theoretical Computer Science https://arxiv.org/abs/1811.03595, to appear. A vailable at https://arxiv.org/abs/1811.03595

work page internal anchor Pith review Pith/arXiv arXiv
[7]

In: The Tenth International Symposium on Games, Automata, Logics, and Formal Veriﬁ- cation, September 2-3, 2019

Gelle, K., Ivan, S.: On the order type of scattered context -free orderings. In: The Tenth International Symposium on Games, Automata, Logics, and Formal Veriﬁ- cation, September 2-3, 2019. pp. ?–? (2019)

work page 2019
[8]

RAIRO - Theoretical Informatics an d Appli- cations - Informatique Théorique et Applications 14(2), 131–141 (1980), http://www.numdam.org/item/ITA_1980__14_2_131_0

Heilbrunner, S.: An algorithm for the solution of ﬁxed-po int equa- tions for inﬁnite words. RAIRO - Theoretical Informatics an d Appli- cations - Informatique Théorique et Applications 14(2), 131–141 (1980), http://www.numdam.org/item/ITA_1980__14_2_131_0

work page 1980
[9]

Addison-Wesley Publishing Company (1979)

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata T heory, Languages, and Computation. Addison-Wesley Publishing Company (1979)

work page 1979
[10]

Pure and Applied Math ematics, Elsevier Science (1982), https://books.google.hu/books?id=y3YpdW-sbFsC

Rosenstein, J.: Linear Orderings. Pure and Applied Math ematics, Elsevier Science (1982), https://books.google.hu/books?id=y3YpdW-sbFsC

work page 1982
[11]

Stark, J.A.: Ordinal arithmetic (2015), https://jalexstark.com/notes/OrdinalArithmetic.pdf, available from https://jalexstark.com/notes/OrdinalAr ithmetic.pdf

work page 2015
[12]

ITA 20(4), 371–381 (1986) 15

Thomas, W.: On frontiers of regular trees. ITA 20(4), 371–381 (1986) 15

work page 1986

[1] [1]

Bloom, S.L., Ésik, Z.: Algebraic ordinals. Fundam. Infor m. 99(4), 383–407 (2010). https://doi.org/10.3233/FI-2010-255, https://doi.org/10.3233/FI-2010-255

work page doi:10.3233/fi-2010-255 2010

[2] [2]

Information and Computation 197(1), 55 – 89 (2005)

Bloom, S.L., Ésik, Z.: The equational theory of regu- lar words. Information and Computation 197(1), 55 – 89 (2005). https://doi.org/https://doi.org/10.1016/j.ic .2005.01.004, http://www.sciencedirect.com/science/article/pii/S0890540105000192

work page doi:10.1016/j.ic 2005

[3] [3]

In: M auri, G., Leporati, A

Ésik, Z.: Scattered context-free linear orderings. In: M auri, G., Leporati, A. (eds.) Developments in Language Theory. pp. 216–227. Sprin ger Berlin Heidelberg, Berlin, Heidelberg (2011) 14

work page 2011

[4] [4]

Information Processing Letters 111(3), 107 – 109 (2011)

Ésik, Z.: An undecidable property of context-free linear or- ders. Information Processing Letters 111(3), 107 – 109 (2011). https://doi.org/https://doi.org/10.1016/j.ip l.2010.10.018, http://www.sciencedirect.com/science/article/pii/S0020019010003248

work page doi:10.1016/j.ip 2011

[5] [5]

In: Fernández-Baca, D

Ésik, Z., Iván, S.: Hausdorﬀ rank of scattered context-fr ee linear orders. In: Fernández-Baca, D. (ed.) LATIN 2012: Theoretical Informat ics. pp. 291–302. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)

work page 2012

[6] [6]

The ordinal generated by an ordinal grammar is computable

Gelle, K., Iván, S.: The ordinal generated by an ordinal gr ammar is computable. Theoretical Computer Science https://arxiv.org/abs/1811.03595, to appear. A vailable at https://arxiv.org/abs/1811.03595

work page internal anchor Pith review Pith/arXiv arXiv

[7] [7]

In: The Tenth International Symposium on Games, Automata, Logics, and Formal Veriﬁ- cation, September 2-3, 2019

Gelle, K., Ivan, S.: On the order type of scattered context -free orderings. In: The Tenth International Symposium on Games, Automata, Logics, and Formal Veriﬁ- cation, September 2-3, 2019. pp. ?–? (2019)

work page 2019

[8] [8]

RAIRO - Theoretical Informatics an d Appli- cations - Informatique Théorique et Applications 14(2), 131–141 (1980), http://www.numdam.org/item/ITA_1980__14_2_131_0

Heilbrunner, S.: An algorithm for the solution of ﬁxed-po int equa- tions for inﬁnite words. RAIRO - Theoretical Informatics an d Appli- cations - Informatique Théorique et Applications 14(2), 131–141 (1980), http://www.numdam.org/item/ITA_1980__14_2_131_0

work page 1980

[9] [9]

Addison-Wesley Publishing Company (1979)

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata T heory, Languages, and Computation. Addison-Wesley Publishing Company (1979)

work page 1979

[10] [10]

Pure and Applied Math ematics, Elsevier Science (1982), https://books.google.hu/books?id=y3YpdW-sbFsC

Rosenstein, J.: Linear Orderings. Pure and Applied Math ematics, Elsevier Science (1982), https://books.google.hu/books?id=y3YpdW-sbFsC

work page 1982

[11] [11]

Stark, J.A.: Ordinal arithmetic (2015), https://jalexstark.com/notes/OrdinalArithmetic.pdf, available from https://jalexstark.com/notes/OrdinalAr ithmetic.pdf

work page 2015

[12] [12]

ITA 20(4), 371–381 (1986) 15

Thomas, W.: On frontiers of regular trees. ITA 20(4), 371–381 (1986) 15

work page 1986