The order type of scattered context-free orderings of rank one is computable
Kitti Gelle Szabolcs Ivan
cs.FL

	
	
	Department of Computer Science, University of Szeged, Hungary
 {kgelle,szabivan}@inf.u-szeged.hu
	
	The order type of scattered context-free orderings of rank one is computable
    Kitti Gelle, Szabolcs Iván
    December 30, 2023
============================================================================


	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.
	



§ INTRODUCTION

If an alphabet Σ is equipped by a linear order <, this order can be extended to the lexicographic
ordering <_ℓ on Σ^* as u<_ℓ v if and only if either u is a proper prefix of v or
u=xay and v=xbz for some x,y,z∈Σ^* and letters a<b. So any language L⊆Σ^*
can be viewed as a linear ordering (L,<_ℓ). Since {a,b}^* contains the dense ordering
(aa+bb)^*ab and every countable linear ordering can be embedded into any countably infinite dense ordering,
every countable linear ordering is isomorphic to one of the form (L,<_ℓ) for some language L⊆{a,b}^*.
A linear ordering (or an order type) is called regular or context-free
if it is isomorphic to the linear ordering (or, is the order type) of some language of the appropriate type.
It is known <cit.> that an ordinal is regular if and only if it is less than ω^ω
and is context-free if and only if it is less than ω^ω^ω. Also, the Hausdorff rank <cit.>
of any scattered regular (context-free, resp.) ordering is less than ω (ω^ω, resp) <cit.>.

It is known <cit.> that the order type of a well-ordered language generated by a prefix grammar (i.e. in which
each nonterminal generates a prefix-free language)
is computable,
thus the isomorphism problem of context-free ordinals is decidable if the ordinals in question are given as the lexicograpic
ordering of prefix grammars.
Also, the isomorphism problem of regular orderings is decidable as well <cit.>.
At the other hand, it is undecidable for a context-free grammar whether it generates a dense language,
hence the isomorphism problem of context-free orderings in general is undecidable <cit.>.

Algorithms that work for the well-ordered case can in many cases be “tweaked” somehow
to make them work for the scattered case as well:
e.g. it is decidable whether (L,<_ℓ) is well-ordered or scattered <cit.>
and the two algorithms are quite similar.
In an earlier paper <cit.> we showed that it is undecidable for a scattered context-free ordering
of rank 2
whether its order type is ω+(ω+ζ)×ω, even if it is given by a prefix grammar – so
the complexity of the isomorphism problem
is quite different when one makes the step from well-ordered languages to scattered ones.

In the current paper we complement this result by showing that if the rank of a scattered context-free
ordering is at most one (we also show that this property is decidable as well), then its order type is
effectively computable (as a finite sum of the order types 1, ω and -ω).
	


§ NOTATION

A linear ordering is a pair (Q,<), where Q is some set and the < is a transitive, antisymmetric and connex 
(that is, for each x,y∈ Q exactly one of x<y, y<x or x=y holds) binary relation on Q.
The pair (Q,<) is also written simply Q if the ordering is clear from the context.
A (necessarily injective) function h: Q_1→ Q_2, where (Q_1,<_1) and (Q_2,<_2) are some linear orderings,
is called an (order) embedding
if for each x,y∈ Q_1, x<_1 y implies h(x) <_2 h(y). If Q_1 can be embedded into Q_2, then
this is denoted by Q_1≼ Q_2.
If h is also surjective, h is an isomorphism, in which case the two orderings are isomorphic.
An isomorphism class is called an order type. The order type of the linear ordering Q is denoted by o(Q).

For example, the class of all linear orderings contain all the finite linear orderings
and the orderings of the integers (ℤ), the positive integers (ℕ) and the negative integers (ℕ_-) whose order type is denoted ζ, ω and -ω respectively.
Order types of the finite sets are denoted by their cardinality, and [n] denotes {1,…,n} for each n≥ 0, ordered in the standard way.

The ordered sum ∑_x∈ Q Q_x, where Q is some linear ordering and for each x ∈ Q, Q_x is a linear ordering,
is defined as the ordering with domain {(x,q):x∈ Q,q∈ Q_x} and ordering relation
(x,q)<(y,p) if and only if either x<y, or x=y and q<p in the respective Q_x. 
If each Q_x has the same order type o_1 and Q has order type o_2, then the above sum has order type o_1× o_2.
If Q=[2], then the sum is usally written as Q_1+Q_2.

If (Q,<) is a linear ordering and Q'⊆ Q, we also write (Q',<) for the subordering of (Q,<), that is, to ease notation we also use < for the restriction of < to Q'.

A linear ordering (Q,<) is called dense if it has at least two elements and for each x,y∈ Q where x<y there exists a z∈ Q such that x<z<y.
A linear ordering is scattered if no dense ordering can be embedded into it.
It is well-known that every scattered sum of scattered linear orderings is scattered, and any finite union of scattered linear orderings is scattered.
A linear ordering is called a well-ordering if it has no subordering of type -ω. Clearly, any well-ordering is scattered. Since isomorphism preserves well-orderedness
or scatteredness, we can call an order type well-ordered or scattered as well,
or say that an order type embeds into another. We also write o_1≼ o_2 to denote o_1 embeds into o_2.
The well-ordered order types are called ordinals.
For any set Ω of ordinals, (Ω,<) is well-ordered by the relation o_1≺ o_2 ⇔ “o_1 can be embedded injectively into o_2 but not vice versa”.
Amongst ordinals, it is common to use the notation o_1<o_2 instead of o_1≺ o_2.
The principle of well-founded induction can be formulated as follows. Assume P is a property of ordinals such that for any ordinal o, if P holds for all ordinals
smaller than o, then P holds for o. Then P holds for all the ordinals.

For standard notions and useful facts about linear orderings see e.g. <cit.> or <cit.>.

Hausdorff classified the countable scattered linear orderings with respect to their rank.
We will use the definition of the Hausdorff rank from <cit.>,
which slightly differs from the original one (in which H_0 contains only the empty ordering and the singletons,
and the classes H_α are not required to be closed under finite sum, see e.g. <cit.>).
For each countable ordinal α, we define the class H_α of countable linear orderings as follows.
H_0 consists of all finite linear orderings, and
when α> 0 is a countable ordinal,
then H_α is the least class of linear orderings closed under finite ordered sum and isomorphism
which contains all linear orderings of the form ∑_i∈ℤ Q_i,
where each Q_i is in H_β_i for some β_i < α.

By Hausdorff's theorem, a countable linear order Q is scattered if and only if it belongs to H_α for some countable ordinal α.
The rank r(Q) of a countable scattered linear ordering is the least ordinal α with Q ∈ H_α.

As an example, ω, ζ, -ω and ω+ζ or any finite sum of the form ∑_i∈[n]o_i with o_i∈{ω, -ω,1} for each i∈[n]
each have rank 1 while (ω+ζ)×ω has rank 2.

Let Σ be an alphabet (a finite nonempty set) and let Σ^* (Σ^+, resp) stand for the set of all (all nonempty, resp)
finite words over Σ, ε for the empty word, |u| for the length of the word u, u· v or simply uv for the concatenation of u and v. A language is an arbitrary subset L of Σ^*. 
We assume that each alphabet is equipped by some (total) linear order.
Two (strict) partial orderings, the strict ordering <_s and the prefix ordering <_p are defined over Σ^* as
follows:

	
  * u <_s v if and only if u = u_1au_2 and v = u_1bv_2 for some words u_1, u_2, v_2∈Σ^* and letters a < b,
	
  * u <_p v if and only if v = uw for some nonempty word w∈Σ^*.
 
The union of these partial orderings is the lexicographical ordering <_ℓ = <_s ∪ <_p.
We call the language L well-ordered or scattered,
if (L,<_ℓ) has the appropriate property and we define the rank r(L) of a scattered language L
as r(L,<_ℓ). The order type o(L) of a language L is the order type of (L,<_ℓ).
For example, if a<b, then o({a^kb:k≥ 0})=-ω and o({(bb)^ka:k≥ 0})=ω.

When ϱ is a relation over words (like <_ℓ or <_s), we write Kϱ L if uϱ v for each word u∈ K and v∈ L.

An ω-word over Σ is an ω-sequence a_1a_2… of letters a_i∈Σ. The set of all ω-words over Σ is denoted Σ^ω.
The orderings <_ℓ and <_p are extended to ω-words. An ω-word w is called regular if w=uv^ω=uvvvv… for some finite words
u∈Σ^* and v∈Σ^+. When w is a (finite or ω-) word over Σ and L⊆Σ^* is a language, then L_<w
stands for the language {u∈ L:u<w}. Notions like L_≥ w, L_<_sw are also used as well, with the analogous semantics.


A context-free grammar is a tuple G=(N,Σ,P,S), where N is the alphabet of the nonterminal symbols, Σ is the alphabet of terminal symbols (or letters) which is disjoint from N, S∈ N is the start symbol and P is a finite set of productions of the form A→α, where A∈ N and α is a sentential form, that is, α = X_1X_2… X_k for some k≥ 0 and X_1,…,X_k∈ N∪Σ. The derivation relations ⇒, ⇒_ℓ, ⇒^* and ⇒_ℓ^* are defined as usual
(where the subscript ℓ stands for “leftmost”).
The language generated by a grammar G is defined as L(G) = {u∈Σ^*  |  S⇒^*u}.
Languages generated by some context-free grammar are called context-free languages. 
For any set Δ of sentential forms, the language generated by Δ is L(Δ) = {u ∈Σ^*  | α⇒^* u for some α∈Δ}. 
As a shorthand, we define o(Δ) as o(L(Δ)).
When X,Y∈ N∪Σ are symbols of a grammar G, we write Y≼ X if X⇒^*uYv for some words u and v; X≈ Y if X≼ Y and Y≼ X both hold;
and Y≺ X if Y≼ X but not X≼ Y. A production of the form X→ X_1… X_n with X_i≺ X
for each i∈[n] is called an escaping production.

A regular language over Σ is one which can be built up from the singleton languages {a}, a∈Σ
and the empty language ∅ with finitely many applications of taking (finite) union,
concatenation KL={uv:u∈ K,v∈ L} and iteration K^*={u_1… u_n:n≥ 0,u_i∈ K}. 
For standard notions on regular and context-free languages the reader is referred to any standard textbook, such as <cit.>.

Linear orderings which are isomorphic to the lexicographic ordering of some context-free (regular, resp.) language
are called context-free (regular, resp.) orderings.	


§ LIMITS OF LANGUAGES

In this section we introduce the notion of a limit of a language and establish a connection:
the main contribution of this concept is that one can decide whether a context-free language has a finite
number of limits and if so, one can effectively compute the limits themselves (Lemma <ref>),
and that a language has a finite number of limits if and only if its order type is scattered of rank at most one
(Theorem <ref>).

Firstly, we recall (and prove for the sake of completeness) that Σ^∞ forms a complete lattice
with the partial ordering ≤_ℓ (which can be turned into a metric space as well).

	
	(Σ^∞, ≤_ℓ) is a complete lattice.


	Let L be an infinite language. If L has a maximal element, then it is the supremum, otherwise we generate the word a_1a_2a_3…∈Σ^ω in the following way: let u_0 = ε and u_i = a_1… a_i.
	We choose the largest possible letter a_i+1 with (u_ia_i+1)^-1L being nonempty.
	The word generated by this way is the supremum of L. 




 §.§ Limits in general

Though limits of a language could be defined as limits of Cauchy sequences in the aforementioned metric space,
the following (equivalent) definition is more convenient for our purposes.

	The word w∈Σ^ω is a limit of an infinite language L, if for each w_0<_p w there exists a word u∈ L such that w_0<_p u.


If L ⊆Σ^* is a language, then we denote the limits of L with L. 


	If w is a limit of an infinite language L, then for each w_0<_p w there exist infinitely many words u∈ L with w_0<_p u.


	We construct two sequences w_0 <_p w_1 <_p … <_p w and u_0, u_1, …∈ L such that w_i <_p u_i for each i with mutual induction.
	Now w_0 is given. By definition for each i there exists an u_i∈ L such that w_i<_p u_i and w_i∈𝐏𝐫𝐞𝐟(w) is constructed such that |u_i-1|+1<|w_i|.
	
	It is clear the words u_i are pairwise different, since each w_i has different length. So we get that w_0 is a prefix of each u_i, so w_0 is a prefix of infinitely many words in L.	


	

	For each infinite language L, the set L is nonempty.


	We construct a limit word w=a_1a_2…∈Σ^ω. Let u_0 = ε and u_i = a_1… a_i and we choose a_i+1∈Σ such that u_ia_i+1 is a prefix of infinitely many words in L. Since L is infinite there exists such a letter. Thus we can construct an infinite word which is a limit of L.    


Now we justify using the name “limit”: any supremum or infimum of a chain (which is a Cauchy sequence) of words
of a language is a limit of the language.
 
	
	If w_0, w_1, … is a <_ℓ (or >_ℓ respectively) chain in L, then its supremum (infimum, resp.) is a limit of L.


	Let w be the supremum of the <_ℓ chain in L. We only have to show that for each w'<_p w there exists a member u of the chain with w'<_p u.
	First, as the chain is infinite, there are infinitely many words w_i with |w_i|>|w'| and the supremum of these words w_i is w as well.
	For these words we cannot have w'<_pw_i.
	As w>w' is the supremum of the words w_i, we have w_i<_ℓ w for each of them, moreover, there exists some word w_i with w'<_ℓ w_i<_ℓ w.
	Since we know that w'<_pw, it has to be the case that w'<_pw_i<_ℓ w and the claim is proved.
	
	For the other case, let w be the infimum of the >_ℓ chain in L and let w'<_pw be a prefix of w.
	We again have to show that w'<_pw_i for some i. Again, we can take the subchain consisting of those words w_i with |w_i|>|w'|,
	this does not change their infimum. Now we have w'<_pw<_sw_i for each of these words w_i. We claim that w'<_pw_i for at least one
	index i. Assume to the contrary that w'<_sw_i for each i and let us write w'=u_0az^t where z is the largest letter of Σ,
	and a<z.
	(Since there exist words with w'<_sw_i, w' cannot have the form z^t). Let b be the successor letter of a and consider
	the word w”=u_0b. Obviously, w” is the least word with w'<_sw”, thus w”≤_ℓ w_i for each i. Since w is the infimum of
	these words w_i, we should have w”≤_ℓ w but this contradicts to w'<_pw and w'<_sw” as these two imply w<_sw”.


Now we recall from <cit.> that for any context-free language, we can compute a supremum or infimum
of the language.


	
	For each sentential form α with L(α) being infinite, we can generate a sequence w_0,w_1,…∈ L(α) and a regular word w∈Σ^ω satisfying one of the following cases:
	
		
  i) w_1<_sw_2<_s… and w=⋁_i≥ 0w_i
		
  ii) w_1>_sw_2>_s… and w=⋀_i≥ 0w_i
		
  iii) w_1<_pw_2<_p… and w=⋁_i≥ 0w_i
	

Hence, Lemma <ref> in conjunction with Lemma <ref>
ensure that whenever L is an infinite context-free language,
then one of its limits can be effectively computed, and this particular limit will be a regular word.

Next, we show how to compute limits of unions and products:


	
	For any languages K and L K∪ L = K∪L.


	Assume w is a limit of L. Then for each w_0<_pw, there exists some u∈ L with w_0<_p u.
	Since then u∈ K∪ L as well, w is a limit of K∪ L as well.
	
	For the other direction, assume w is a limit of K∪ L. Then for each w_0<_pw, there exists
	some u∈ K∪ L with w_0<_pu. Thus, either there exists infinitely many prefixes w_0 of w
	for which there exists some u∈ K with w_0<_pu or there exists infinitely many prefixes w_0 of 
	w for which there exists some u∈ L with w_0<_pu. In the former case, w is a limit of K,
	in the latter, w is a limit of L.




	
	KL = K∪ KL if K, L≠∅.


	 Let u∈ K be a word and w be a limit of L. To prove that uw is a limit of KL we only have to show that for each prefix w' of uw there exist a word w^*∈ KL with w' <_p w^*. Let w'∈𝐏𝐫𝐞𝐟(uw), and since it is enough to see the prefixes which are longer than u, the word w' can be written as uw_0. Since w is a limit of L there exists a word v∈ L such that w_0<_p v. Thus there is a word uv∈ KL such that w'<_puv.
	 
	 Now let w be a limit of K. To prove that w is a limit of KL, let u be a word in L and w_0 be a prefix of w. Since w is a limit of K there exists a word v∈ K with w_0 <_p v by definition. So vu ∈ KL and w_0 is a prefix of vu as well.
	 
	 For the other direction, we have to prove that there are no more limits of KL. Let w be a limit of KL and w_i be the prefix of w with length i. Since w is a limit of KL there exist a word u_iv_i∈ KL such that w_i <_p u_iv_i where u_i∈ K and v_i∈ L. Consider for each i>0 the lengths of these words u_i.
	 There are two cases: either there is a finite upper bound on |u_i| or there is not.
	 
	 If |u_i| is not upperbounded, then w is a limit of K, since for each prefix w_i there exists
	 some long enough u_j with w_i<_pu_j.

	In the case where the lengths of these u_i words is bounded, let ℓ = max|u_i| be the maximal length.
	Since there are only finitely many words of length at most ℓ, there has to be some u=u_j such that
	u=u_i for infinitely many indices i. Hence in particular, w=uw' for some w'∈Σ^ω.
	We show that w'∈ L, yielding w∈ K L. Indeed, if w^*<_pw' is a prefix of w', then
	uw^*<_pw and thus there exists some v_i with uw^*<_puv_i, that is, w^*<_pv_i and so w^* is a limit of L.



	
	For any language L and letter a∈Σ,
	L=La and a·L=aL.



	
	For any language L⊆Σ^* and words u,v∈Σ^*, uLv=u·L.




 §.§ Unique limits

In this part we establish the decidability of the problem whether a context-free language has a unique limit.
(In this case, the limit itself is computable as well, thanks to Lemma <ref>.)

In the rest of the paper when grammars are involved, we assume the grammar G=(N,Σ,P,S)
contains no left recursive nonterminals,
and for each X∈ N, X is usable and L(X) is an infinite language of nonempty words.
Moreover, each nonterminal but possibly S is assumed to be recursive.
Any context-free grammar can effectively be transformed into such a form, see e.g. <cit.>.

It is also known <cit.> that if the context-free grammar G generates
a scattered language, then for each recursive nonterminal X there exists a unique (and computable)
primitive word u_X such that whenever X⇒^+uXα for some u∈Σ^* and sentential form
α, then u∈ u_X^+. Moreover, for each pair X≈ Y of recursive nonterminals there exists
a (computable) word u_X,Y∈Σ^* such that whenever X⇒^+ uYv, then u∈ u_X,Yu_Y^*.


	
	The word w∈Σ^ω is the unique limit of an infinite language L if and only if for each w_0<_p w there exists only finitely many words u∈ L such that u<_s w_0 or w_0<_s u.


	We will see just the case where w_0 <_s u, the other one can be done analogously.
	
	Suppose for the sake of contradiction there exist infinitely many words u∈ L with w_0 <_s u. 
	Let w_0 be the shortest such word, it can be written as w_0 = w_0'a. Since there are just finitely many words u∈ L with w_0'<_s u, it has to be the case that w_0'<_p u and w_0'a<_s u for infinitely many u∈ L. Then there exists a letter b∈Σ such that b>a and infinitely many words u∈ L such that w_0'b <_p u. But any limit of these words is in w_0'bΣ^ω
	(and by Lemma <ref> at least one limit exists), which cannot be equal to w, so the language L has two different limits which is a contradiction. 




	
	If L has a unique limit w, then o(L_<w) ≼ω and o(L_>w) ≼ -ω.
	Moreover, in this case both o(L_<w) and o(L_>w) are effectively computable
	(and hence so is o(L)=o(L_<w)+o(L_>w)).


	In the o(L_<w) case, if L_<w is finite (and thus its size is computable),
	we are done. Otherwise L_<w is infinite, which means it has a limit, and this limit has to be the w (since it is unique for L). By Lemma <ref> the supremum
	⋁ L_<w of this language is w as well, moreover,
	each infinite K⊆ L_<w has ⋁ K = w, so the order type of L_<w has to be ω.
	
	In the o(L_>w) case, if L_>w is finite, it can be embedded into -ω so we are done. Otherwise L_>w is infinite, so it has to have a limit which is w. Since this limit should be an infimum of a descending chain, each infinite K⊆ L_>w has ⋀ K = w, so the order type of L_>w has to be -ω.


Before proceeding to the case of concatenation, we recall the notion of prefix chains from <cit.>.
For a word w∈Σ^ω, let 𝐏𝐫𝐞𝐟(w) stand for the set {u∈Σ^*:u<_pw} of
proper prefixes of w. A language L⊆Σ^* is called a prefix chain if L⊆𝐏𝐫𝐞𝐟(w)
for some ω-word ω. Lemma 2 from <cit.> states that it is decidable for
any context-free language L whether L is a prefix chain and if so, a suitable w∈Σ^ω 
can be effectively computed.


	
	Assume we know that for the nonterminals X_1 and X_2
	whether the languages L_1=L(X_1) and L_2=L(X_2) have a unique limit.	
	Then it is computable whether L=L(X_1X_2) has a unique limit.


	By assumption, the nonterminals X_1 and X_2 each generate an infinite language so they have at
	least one limit by Lemma <ref>.	
	By Lemma <ref>, if either L_1 or L_2 has at least two limits, then so have
	L and we can stop.
	
	Assume both L_1 and L_2 have a unique limit.
	As they are both context-free languages,
	their limits are computable regular words by Lemma <ref>. Let u_1v_1^ω and u_2v_2^ω
	respectively be the limits of L_1 and L_2.
	If L_1 is not a prefix chain, that is, x<_sy for some x,y∈ L_1, then both xu_2v_2^ω
	and yu_2v_2^ω are limits of L by Lemma <ref>
	and these two words are different by x<_sy. So in this case we can stop.
	
	From this point we can assume that L_1 is a prefix chain, that is, L_1⊆𝐏𝐫𝐞𝐟(u_1v_1^ω).
	By Lemma <ref>, u_1v_1^ω is also a limit of L,
	and for each u∈ L_1, the word uu_2v_2^ω is also a limit of L.
	Thus, we have to decide whether u_1v_1^ω=uu_2v_2^ω holds for each u∈ L_1.
	
	Now consider the direct product automaton M=M_u_1,v_1× M_u_2,v_2, where in the automaton
	corresponding to L_2 we use primed states q' in place of each state q.
	
	Obviously, u_1v_1^ω≠ uu_2v_2^ω if and only if from the state (q_0· u,q'_0)
	some state of the form (,q') or (q,') is reachable for some q≠.
	Thus, it suffices to determine the set of states q in M_1 for which q_0· u=q for some u∈ L_1,
	that is, for which M_1(q)∩ L_1 is nonempty, which is decidable since L_1 is context-free
	and M_1(q) is regular. Then, for each such state q we test whether a state of the form
	(,p') or (p,') is reachable from (q,q'_0) and if so, then uu_2v_2^ω≠ u_1v_1^ω
	for some u∈ L_1 and thus L has at least two different limits.
	
	Now assume uu_2v_2^ω=u_1v_1^ω for each u∈ L_1. We claim that in this case L has the unique
	limit u_1v_1^ω. To see this, we first prove that for each prefix w_0<_pu_1v_1^ω,
	there are only a finite number of words v∈ L with either w_0<_sv or v<_sw_0.
	Suppose for the sake of contradiction that for some prefix w_0 of u_1v_1^ω there are
	infinitely many such words and let w_0 be the shortest such prefix. 
	By assumption, there are infinitely many words xy∈ L, x∈ L_1, y∈ L_2,
	with either xy<_sw_0 or w_0<_sxy. Since L_1⊆𝐏𝐫𝐞𝐟(u_1v_1^ω) and w_0<_pu_1v_1^ω,
	this can happen only if x<_pw_0. Since there are only finitely many prefixes of w_0,
	for some u<_pw_0 in L_1 there has to be an infinite number of words y∈ L_2 with
	either uy<_sw_0 or w_0<_suy. Let us write w_0=uv.
	The condition uy<_sw_0 or w_0<_suy is then equivalent y<_sv or v<_sy for infinitely many y∈ L_2.
	But since we know that uu_2v_2^ω=u_1v_1^ω, v is a prefix of u_2v_2^ω,
	which is the unique limit of L_2 and thus only finitely many words y∈ L_2 exist with 
	y<_sv or v<_sy by Lemma <ref>, yielding a contradiction.
	
	Hence in this case, u_1v_1^ω is the unique limit of L.	



	
	Assume n≥ 0 and X_1,…,X_n∈ N∪Σ are symbols so that for each X_i we know
	whether L(X_i) has a unique limit. Then it is computable whether L(X_1… X_n) has a unique limit.


	Let us introduce the fresh nonterminals Y_1,…,Y_n-1 and productions
	Y_1→ X_1Y_2, Y_2→ X_2Y_3,…, Y_n-1→ X_n-1X_n. Applying Lemma <ref>
	or Corollary <ref> (depending on whether X_i is a nonterminal or a letter)
	for the nonterminals Y_n-1, Y_n-2, …, Y_1 in this order we can successively decide whether
	each L(Y_i) has a unique limit, proving the statement since L(X_1… X_n)=L(Y_1).



	
	Let X be a nonterminal X→α_1 | … | α_k be the collection of all the escaping productions
	with left-hand side X. Assume we already know for each Y≺ X whether L(Y) has a unique limit.
	Then it is computable whether L({α_1,…,α_k}) has a unique limit.


	By Corollary <ref>, it is computable for each α_i whether each L(α_i)
	is finite or has a unique limit.
	If not, then neither has their union (by Lemma <ref>).
	If each of the languages L(α_i) is either finite or has a unique limit, then their union
	has a unique limit if and only if all the limits are the same.
	But this is decidable since these languages are context-free, hence their unique limit is a computable
	regular word by Lemma <ref>, and the equivalence of these words is decidable.



	
	Assume X is a recursive nonterminal, L(X) is not a prefix chain
	and for some nonterminal X'≈ X there exists a 
	production X'→α X”β with β containing at least one nonterminal.
	
	Then L(X) has at least two limits.	


	Let u<_sv be members of L(X). Since β contains a nonterminal, L(β) is
	infinite and has a limit w by Lemma <ref>. By the conditions on the
	recursive nonterminal X, we get X⇒^*u_1Xu_2β u_3 for some words u_1,u_2,u_3∈Σ^*.
	By Lemma <ref>, both u_1uu_2w and u_1vu_2w are limits of L(X) and they are
	distinct by u<_sv.



	
	Assume L(G) is scattered.
	Then it is decidable for each nonterminal X whether L(X) has a unique limit.


	We prove the statement by induction on ≺. So let X be a nonterminal and 
	assume we already know for each Y≺ X whether L(Y) has a unique limit.
	
	If X is nonrecursive, and X→α_1 | … | α_k are all the alternatives of X,
	then the question is decidable by Corollary <ref>.
	
	So let X be a recursive nonterminal. If L(Y) has at least two limits for some Y≺ X,
	then by Corollary <ref> so does L(X) and we are done. So we can assume from now on
	that each L(Y) with Y≺ X has exactly one limit. This limit is a computable regular word.
	
	If L(X) is a prefix chain, then its supremum is its
	unique limit and we can stop. So we can assume that L(X) is not a prefix chain.
	Now if there exist some production of the form X'→α X”β with X'≈ X”≈ X
	and β containing at least one nonterminal, then by Lemma <ref>,
	L(X) has at least two limits and we can stop. 
	
	Otherwise, we can assume that each component production in the component of X has the form
	X'→α X”u for some u∈Σ^*, X'≈ X”≈ X. Since L(X) is scattered,
	for each such α it has to be the case that L(α)⊆ u_X',X”^u_X”^*.
	
	Now let X'≈ X be a nonterminal and α_1,…,α_k all the escaping alternatives
	of X'. If L({α_1,…,α_k}) has at least two limits, then so does L(X') and L(X)
	and we are done. Otherwise, if L({α_1,…,α_k}) is infinite, then its unique limit
	is a computable word. On the other hand, for each recursive nonterminal X' the word u_X'^ω
	is a limit of L(X'), and by L({α_1,…,α_k})⊆ L(X'), the two limits has to
	coincide (which is decidable). If they are not the same, then again, L(X) has at least two limits
	and we can stop.
	
	Hence we can assume that for each X'≈ X, the language L(X') has the limit u_X'^ω
	which is the same as the unique limit of L({α_1,…,α_k}) if this latter language is infinite.	
	
	We claim that in this case, L(X) has the unique limit u_X^ω. To see this, we apply
	Lemma <ref> and show that for each prefix w_0 of u_X^ω,
	there are only finitely many words u∈ L(X) with either w_0<_su or u<_sw_0.
	
	Assume to the contrary that w_0<_pu_X^ω and there are infinitely many words u∈ L(X) with
	either w_0<_su or u<_sw_0. Each word u∈ L(X) can be derived from X using a leftmost
	derivation sequence resulting in a sentential form u_X^tu_X,X'α v for some t≥ 0
	so that X'→α is an
	escaping production from the component of X and u∈ u_X^tu_X,X'L(α)v.
	Since u and w_0<_pu_X^ω are not related by <_p, we have an upper bound for t,
	which, as G does not contain left-recursive nonterminals, places an upper bound for |v|.
	Hence, there are only finitely many possibilities for picking t≥ 0, X', α and v,
	thus for some combination of them, there are infinitely many such words u belonging to the
	same language u_X^tu_X,X'L(α)v. So we can write each such u as u=u_X^tu_X,X'u'v
	with u'∈ L(α), and we can write w_0 as w_0=u_X^tu_X,X'w'_0, that is, w'_0<_p u_X'^ω.
	This yields that u'v<_sw'_0 or w'_0<_su'v for infinitely many words u'∈ L(α).
	Thus, there are infinitely words u'∈ L(α) of length at least |w'_0| with either u'v<_sw'_0 or
	w'_0<_su'v, hence with either u'<_sw'_0 or w'_0<_su', which is a contradiction, since
	by Lemma <ref> this would yield that L(α) has at least two
	limits, which we already handled in a former case.




 §.§ Finitely many limits

In this part we extend the results of the previous subsection for the context-free languages having
a finite number of limits and get the main result of the paper: it is decidable whether a context-free
language has a scattered order type of rank at most one, and if so, then its order type is 
effectively computable.


	
	It is decidable for any context-free language L and regular word w=uv^ω
	whether w is a limit of L.


	Let L⊆Σ^* be a context-free language and
	consider the generalized sequential mapping f:Σ^*→ a^* defined as
	
    f(x)=a· f(y)   if x=vy for some y∈Σ^*
    ε   otherwise.

	Now for any word x, f(x)=a^n for the unique n such that x=v^ny for some y not having v as prefix.
	Thus, v^ω is a limit of a language L' if and only if f(L') is infinite;
	hence, by Corollary <ref>, w=uv^ω is a limit of L if and only if f(u^-1L) is infinite.
	Since the class of context-free languages is effectively closed under left quotients and generalized
	sequential mappings, and their finiteness problem is decidable, the claim is proved.



	
	If X is a recursive nonterminal, then u_X^ω∈X and if some w≠ u_X^ω is also a member of X, then X is infinite.


	Since X⇒^* u_X^nXα holds for each recursive nonterminals, there exists a word v∈ L(X) for each u∈𝐏𝐫𝐞𝐟(u_X^ω) such that u<_p v.
	
	If w≠ u_X^ω is also a limit of L(X), then it can be written as w=ubw', where u<_pu_X^ω, ub≮_pu_X^ω and w'∈Σ^ω. So if we consider a derivation of the form
	X⇒^* u_X^nXα, we get that each (u_x^n)^kubw', k>0 is a limit, thus X is infinite
	as these words are pairwise different.



	
	Assume K is a context-free language and v is a nonempty word. Then it is decidable whether Kv^ω is finite
	and if so, its members (which are regular words) can be effectively enumerated.


Consider the generalized sequential mapping f: Σ^*→Σ^* defined as

    f(x) = 
    f(y)   if  x=v^Ry  for some  y∈Σ^*
    
    x   otherwise.


Now for any word x, f(x)=y for some y not having v^R as prefix such that x=(v^R)^ky for some k≥ 0,
that is, f strips away the leading v^Rs of its input.
So, we have that (f(K^R))^R consists of those words we get from members of K, stripping
away their trailing vs.
Now u∈(f(K^R))^R if and only if u does not end with v and uv^ω∈ Kv^ω.
Moreover, Kv^ω is finite if and only if there exist some u_1, u_2, …, u_n∈Σ^* such that for each i∈[n] the word u_i does not end with v and  Kv^ω = {u_iv^ω |  i∈ [n]}.
So we get that Kv^ω is finite if and only if so is (f(K^R))^R which is decidable since the class of context-free
languages is effectively closed under reversal and generalized sequential mappings, and their finiteness problem is also
decidable. In this case, members of (f(K^R))^R={u_1,…,u_n} can also be effectively enumerated and
Kv^ω={u_jv^ω:j∈[n]}.




	
	Assume K and L are context-free languages such that K = {u_iv_i^ω |  1≤ i≤ k} and L = {u'_jw_j^ω |  1≤ j≤ℓ} are finite sets of regular words. Then it is decidable whether KL is finite and if so, then it is a computable (finite) set of regular words. 


	By Lemma <ref> KL=K∪ KL. Since K is a finite set
	(and is of course computable since it is given as input),
	we only have to deal with K·L.
	Since 
    K·L=K·{u_j'w_j^ω:j∈[ℓ]}=⋃_j∈[ℓ](Ku_j')w_j^ω

	and this union is finite if and only if so is each language (Ku'_j)w_j^ω, which is decidable by
	Lemma <ref> (since the languages Ku'_j are each context-free), we get decidability
	and even computability if each of them is finite.		



	
	Assume n≥ 0 and X_1,…,X_n∈ N∪Σ are symbols so that for each X_i,
	X_i is a known finite set.
	Then it is decidable whether L(X_1… X_n) has a finite number of limits and if so,
	X_1… X_n is effectively computable.


	Let us introduce the fresh nonterminals Y_1,…,Y_n-1 and productions
	Y_1→ X_1Y_2, Y_2→ X_2Y_3,…, Y_n-1→ X_n-1X_n. Applying Lemma <ref>
	or Corollary <ref> (depending on whether X_i is a nonterminal or a letter)
	for the nonterminals Y_n-1, Y_n-2, …, Y_1 in this order we can decide whether
	each L(Y_i) has a finite number of limits, and if so, we compute Y_i as well,
	proving the statement since L(X_1… X_n)=L(Y_1).




	
	It is decidable for any nonterminal X whether L(X) has a finite number of limits.


	There are two cases: either X is recursive or not. If X is recursive, then by Lemma <ref>
	L(X) has a finite number of limits if and only it has a unique limit which is decidable due to Lemma <ref>.
	Hence we can decide for each nonterminal X≠ S whether L(X) is finite.
	
	Now suppose X is not recursive (thus X=S as G is in normal form)
	and let _1,…,_t be all the alternatives of S.	
	By Corollary <ref> for each α_i (1≤ i≤ t) it is decidable whether L(α_i) has a finite number of limits. If one of them has infinite limits than so has X.
	So we can assume that each L(α_i) has a finite number of limits and we can
	even compute each α_i.
	By Lemma <ref>, X = ⋃_i∈ [t]α_i.
 




	
	Suppose L is a context-free language having a finite number of limits.
	Then o(L) is effectively computable and is scattered of rank at most one.


	We prove the statement by induction on the number of limits.
	
	If L has no limits, then it is finite by Lemma <ref>, and so o(L)=|L| is computable.
	
	If L has a unique limit, then o(L) can be embedded into ω+-ω and is computable
	by Lemma <ref>. Moreover, it is decidable
	whether L has a unique limit by Lemma <ref>.
	
	Now assume L has at least two limits. Since L is infinite, we can compute a regular limit
	of the form w=uv^ω for L by Lemma <ref>.
	By Lemma <ref>, it is decidable whether w is a limit
	of either L_<w or L_>w or both of them. (By Lemma <ref>, w is a limit of 
	at least one of them.) If w is not a limit of L_<w (L_>w, resp.), then this language
	has a smaller number of limits than L and we can proceed by induction. Suppose now w is a limit of
	L_<w – it has to be w=⋁ L_<w then.
	If L has a limit which is larger than w
	(that is, L_>w is infinite and either w is not a limit of L_>w or L_>w has at least two
	limits – this is decidable as well),
	then L_<w has a smaller number of limits than L
	(since no limit of L_<w can be strictly larger than its supremum)
	and we can proceed again by induction and get that L_<w is computable.
	It is also decidable whether L_<w has only one limit and if so, its order type is also computable
	and we are done.
	
	The last case is when w=⋁ L_<w is the largest limit of L and L_<w has at least two limits.
	Thus, there exists some limit w' of L_<w and an integer n≥ 0 such that w'<_suv^n,
	or equivalently, L_<uv^n is infinite for some n≥ 0. We can compute (say, the least) such n
	by starting from n=0 and iterating, eventually we will find an integer n with this property.
	Then, L_<uv^n has a smaller number of limits than L_<w so we can use induction and compute o(L_<uv^n);
	also, L_<w_≥ uv^n also has a smaller number of limits than L_<w (since w' is missing) and we can
	apply induction to this half as well and compute its order type. Then, o(L_<w) is the sum of
	the two already computed order types.
	
	Repeating the same argument (by appropriate modifications: taking infimum instead of supremum,
	splitting the case when w is the least limit of L) we get that o(L_>w) is also computable,
	and o(L), being the sum o(L_<w)+o(L_>w), is hence computable as well.
	
	We also got that the order type of such a language has to be a finite sum of
	the order types ω, -ω and 1, that is, has to have rank at most 1.



	
	Suppose L is a scattered context-free language of rank at most one.	
	Then o(L) is effectively computable.


	If o(L)∈{ω,-ω}, then L has one limit, while if o(L) is finite, then it has no limits.
	Since scattered order types of rank at most one are finite sums of the order types
	ω, -ω and 1, thus scattered languages of rank at most one are finite unions of
	languages of order type ω, -ω or 1, by Lemma <ref> we get that
	such languages have a finite number of limits, and thus their order type is effectively computable
	by Theorem <ref>.



	
	For any context-free language L, it is decidable whether L is a scattered language of rank at most one,
	and if so, o(L) can be effectively computed (as a finite sum of the order types 1, ω and -ω).




§ CONCLUSION

We showed that it is decidable whether a context-free ordering is scattered of rank at most one, and
if so, then its order type is effectively computable as a finite sum of the order types 1, ω
and -ω. This complements our earlier result <cit.> that for scattered
context-free orderings of rank (at least) two, it is undecidable whether their order type
is ω+(ω+ζ)×ω, thus the order type is not computable, even if the grammar
in question is a so-called prefix grammar.

An interesting question for further study is whether the rank of a scattered context-free ordering
is computable. Another, maybe easier one is to determine which rank-two scattered orderings are
context-free (as there are uncountably many such orderings, the vast majority of them cannot be
context-free).

A relatied notion is that of tree automatic orderings: these are the order types of regular tree languages
equipped with the lexicographic ordering (on trees). Through derivation trees, there is a tight connection
between context-free string languages and regular tree languages but as the two orderings differ (lexicographic
ordering of trees vs their frontiers), it is unclear whether there is a nontrivial inclusion between these
two classes of orderings (or at least for the scattered case).

splncs04
