\section{Introduction}

The fact that three flavors of neutrinos should be massive and mixed has been confirmed by various neutrino oscillation experiments \cite{pdg2018}. Moreover, the neutrinos should be extremely light to satisfy the cosmological constraints \cite{pdg2018}.  The tiny but nonzero neutrino masses can be naturally explained by the famous seesaw mechanism \cite{minkowski1977,yanagida1979,grs1979,ms1980}. Some seesaw models such as the type-I  \cite{minkowski1977,yanagida1979,grs1979,ms1980}, type-II  \cite{mw1980,sv1980,cl1980,lsw1981,ms1981} and type-III \cite{flhj1989} seesaw can further accommodate a leptogenesis mechanism \cite{fy1986} to understand the cosmic baryon asymmetry \cite{pdg2018}, which is much much bigger than the value induced in the standard model (SM). In this seesaw-leptogenesis framework, additionally heavy particles couple to the SM lepton and Higgs doublets so that their decays can produce a lepton asymmetry stored in the SM leptons \cite{fy1986,lpy1986,fps1995,ms1998,bcst1999,hambye2001,di2002,gnrrs2003,hs2004,bbp2005}. In association with the sphaleron processes \cite{krs1985}, the produced lepton asymmetry can be partially converted to a baryon asymmetry. Meanwhile, the small neutrino masses can be induced by integrating out the heavy particles from the same interactions.

The inverse seesaw mechanism is another attractive seesaw scenario \cite{mv1986}. In the inverse seesaw models, several right-handed neutrinos can have a sizable mass term with the same number of other neutral fermions which are assigned to a small Majorana mass term. Due to such small Majorana masses, the right-handed neutrinos can be allowed to significantly mix with the left-handed neutrinos. The right-handed neutrinos thus may be verified experimentally. Remarkably, the small Majorana mass term of the neutral fermions is crucial to the testability of the inverse seesaw. It has been shown such small Majorana masses can be suppressed by additionally heavy fermion \cite{adefhv2018,gu2019} and/or scalar \cite{gu2019} singlets after a $U(1)_X^{}$ global symmetry is spontaneously broken. The same interactions can also account for the generation of the baryon asymmetry.

In this paper we shall develop our recent work \cite{gu2019} to solve the dark matter puzzle, which is another big challenge to the SM. Specifically, the SM $SU(3)_c^{}\times SU(2)_L^{}\times U(1)_Y^{}$ gauge symmetries will be extended by a $U(1)_{B-L}^{}$ gauge symmetry. In order to cancel the gauge anomalies, we introduce seven neutral fermions including two usual right-handed neutrinos. After a Higgs singlet develops its vacuum expectation value (VEV) for spontaneously breaking the $U(1)_{B-L}^{}$ symmetry, two neutral fermions can obtain their small Majorana masses by integrating out some heavy scalar or fermion singlets, meanwhile, they can have a sizable mass term with the right-handed neutrinos. After the SM Higgs doublet drives the electroweak symmetry breaking, the two right-handed neutrinos and the three left-handed neutrinos can acquire their Dirac masses. We thus can realize an inverse seesaw to give a rank-2 neutrino mass matrix with two nonzero eigenvalues. Within this framework, the heavy scalar or fermion singlet decays can explain the cosmic baryon asymmetry in association with the sphaleron processes. On the other hand, another two neutral fermions can form a Dirac particle due to their Yukawa coupling with the $U(1)_{B-L}^{}$ Higgs singlet. This Dirac fermion can serve as a stable dark matter particle. As for the seventh neutral fermion, it keeps massless but decouples early.

\section{Fermions and scalars}

The SM fermions now are gauged by a $U(1)_{B-L}^{}$ symmetry besides the $SU(3)_c^{} \times SU(2)^{}_{L}\times U(1)_Y^{}$ groups,
\begin{eqnarray}
&&\begin{array}{l}q^{}_{L}(3,2,+\frac{1}{6},+\frac{1}{3}),\end{array} \!\!
\begin{array}{l}d^{}_{R}(3,1,-\frac{1}{3},+\frac{1}{3}),\end{array}  \!\!
 \begin{array}{l}u^{}_{R}(3,1,+\frac{2}{3},+\frac{1}{3});\end{array} \nonumber\\
[2mm]
&&\begin{array}{l}l^{}_{L}(1,2,-\frac{1}{2},-1),\end{array} \!\!
\begin{array}{l}e^{}_{R}(1,1,-1,-1).\end{array}
\end{eqnarray}
Here and thereafter the brackets following the fields describe the transformations under the $SU(3)_c^{} \times SU(2)^{}_{L}\times U(1)_Y^{}\times U(1)_{B-L}^{}$ gauge groups. For simplicity, we do not show the indices of the three generations of fermions. In order to cancel the gauge anomalies, we can introduce some neutral fermions with appropriate $U(1)_{B-L}^{}$ charges \cite{mp2007,pry2016,gu2019-2}. In the present work, we take seven neutral fermions including two usual right-handed neutrinos,
\begin{eqnarray}
&&\begin{array}{l}
\nu^{}_{R1,2}(1,1,0,-1),\end{array}  \begin{array}{l}S^{}_{R1,2}(1,1,0,+\frac{1}{2}),\end{array} \nonumber\\
&& \begin{array}{l}\chi^{}_{R1}(1,1,0,\frac{1+\sqrt{153}}{4}),\end{array}  \begin{array}{l}\chi^{}_{R2}(1,1,0,\frac{1-\sqrt{153}}{4}),\end{array} \nonumber\\
&&\begin{array}{l}
\zeta^{}_{R}(1,1,0,-\frac{5}{2}).\end{array}\end{eqnarray}

While the SM Higgs doublet,
\begin{eqnarray}
\begin{array}{l}\phi^{}(1,2,-\frac{1}{2},0),\end{array}
\end{eqnarray}
is responsible for the electroweak symmetry breaking as usual, we introduce a Higgs singlet,
\begin{eqnarray}
\begin{array}{l}
\xi(1,1,0,+\frac{1}{2}),\end{array}
\end{eqnarray}
to spontaneously break the $U(1)_{B-L}^{}$ symmetry. Furthermore, our model contains some heavy SM-singlet scalars or fermions,
\begin{eqnarray}
\begin{array}{l}X^{}_{Ra}(1,1,0,0)\,,~~\Sigma_b^{}(1,1,0,+1)\,,~~(a,b=1,...)\,.\end{array}
\end{eqnarray}

For simplicity, we do not write down the full Yukawa and scalar interactions. Indeed, we will show later the inverse seesaw and the leptogenesis only depend on the following terms,
\begin{eqnarray}
\label{lag}
\mathcal{L}&\supset& \mathcal{L}_{\textrm{I}/\textrm{II}}^{}- \left(y \bar{l}_{L}^{} \phi \nu_R^{} + f \xi \bar{\nu}_R^{c} S_R^{} +\textrm{H.c.}\right)~~\textrm{with}\nonumber\\
&&\mathcal{L}_{\textrm{I}}\supset -\frac{1}{2}M_X^{} \bar{X}_R^{}X_R^{c} -g_X^{} \xi \bar{S}_R^{} X_R^{c} +\textrm{H.c.}\,,\nonumber\\
&&
\mathcal{L}_{\textrm{II}}^{}\supset -M_\Sigma^2 \Sigma^\dagger_{}\Sigma + \rho_\Sigma^{}\Sigma \xi \xi+ \frac{1}{2}g_\Sigma^{}\Sigma \bar{S}_R^c S_R^{} +\textrm{H.c.}\,.\nonumber\\
&&
\end{eqnarray}
Without loss of generality and for convenience, we can take the mass matrices $M_\Sigma^{}$ and $M_{X}^{}$ to be real and diagonal. Accordingly, we can define the Majorana fermions as below,
\begin{eqnarray}
X_a^{}= X_{Ra}^{} + X_{Ra}^c = X^c_{a}\,.
\end{eqnarray}
Note if the heavy scalar singlet(s) $\Sigma_b^{}$ and the heavy fermion singlet(s) $X_{Ra}^{}$ are both introduced to the models, they should have the Yukawa interactions of the form $\Sigma \bar{\nu}_{R}^{c}X_R^{} +\textrm{H.c.}$. However, such terms are harmful for the realisation of an inverse seesaw. So, we will not consider this case. Instead, we will focus on the case with either the heavy scalar singlet(s) $\Sigma_b^{}$ or the heavy fermion singlet(s) $X_{Ra}^{}$.

We then move to the other neutral fermions $\chi_{R1,2}^{}$ and $\zeta_R^{}$. We can easily find that because of the $U(1)_{B-L}^{}$ symmetry, the $\zeta_R^{}$ fermion is forbidden to have any Yukawa coupling, but the $\chi_{R1,2}^{}$ fermions are allowed to have a Yukawa coupling as below,
\begin{eqnarray}
\label{dm}
\mathcal{L}&\supset& - y_\chi^{} \left(\xi \bar{\chi}_{R1}^{} \chi_{R2}^c +\textrm{H.c.}\right)\,.
\end{eqnarray}
We will show in the following that the $\chi_{R1,2}^{}$ fermions provide a dark matter candidate while the $\zeta_R^{}$ fermion keeps massless and decouples safely.

\section{Minimal inverse seesaw}

\begin{figure*}
\vspace{8cm} \epsfig{file=numass, bbllx=7.5cm, bblly=6.0cm,
bburx=17.5cm, bbury=16cm, width=8cm, height=8cm, angle=0,
clip=0} \vspace{-6cm} \caption{\label{numass} The inverse seesaw mechnasim for generating the tiny neutrino masses. The interactions in the boxes provide an additional seesaw mechanism for generating a small Majorana mass term which is crucial to the inverse seesaw mechanism. }
\end{figure*}

When the Higgs singlet $\xi$ acquires its VEV for the spontaneous $U(1)_{B-L}^{}$ symmetry breaking, the two neutral fermions $S_{R1,2}^{}$ can obtain a Majorana mass term by integrating out the Majorana fermions $X_a^{}$ or the Higgs singlets $\Sigma_b^{}$ in Eq. (\ref{lag}), i.e.
\begin{eqnarray}
\mathcal{L}&\supset&- \frac{1}{2}\sum_{i,j=1,2}^{}\left(\mu_S^{}\right)_{ij}^{} \bar{S}_{Ri}^c S_{Rj}^{} +\textrm{H.c.}~~\textrm{with}\nonumber\\
&&\left(\mu_S^{}\right)_{ij}^{}=- \sum_{b=1}^{n\geq 2}\left(g_{X}^{\ast}\right)_{ib}^{} \frac{ \langle\xi\rangle^2_{}}{M_{X_b}^{}} \left(g_{X}^{\dagger}\right)_{bj}^{}~~\textrm{or}\nonumber\\
&&\left(\mu_S^{}\right)_{ij}^{} = - \sum_{a=1}^{n\geq 2}\left(g_{\Sigma_{a}}^{} \right)_{ij}^{}\frac{\rho_{\Sigma_a}^{} \langle\xi\rangle^2_{}}{M_{\Sigma_a}^2}\,.
\end{eqnarray}
Clearly, as the Majorana fermions $X_a^{}$ or the Higgs singlets $\Sigma_b^{}$ are assumed to be much heavier than the $U(1)_{B-L}^{}$ breaking scale $\langle\xi\rangle$, the above Majorana masses $\mu_S^{}$ can be highly suppressed in a natural way. This Majorana mass generation is similar to the conventional type-I or type-II seesaw mechanism.

At this stage, the two neutral fermions $S_{R1,2}^{}$ can also mix with the two right-handed neutrinos $\nu_{R1,2}^{}$ to form the quasi-Dirac fermions, i.e.
\begin{eqnarray}
\mathcal{L}&\supset& -\sum_{i,j=1,2}^{}(m_N^{})_{ij} \bar{N}_{Ri}^{} N_{Lj}^{} +\textrm{H.c.}^{} ~~\textrm{with}\nonumber\\
&&N=\nu_R^{}+S_R^c\,,~~m_N^{} = f\langle\xi\rangle\,.
\end{eqnarray}
Subsequently, the Higgs doublet $\phi$ develops its VEV for the electroweak symmetry breaking. The two right-handed neutrinos $\nu_{R1,2}^{}$ can further have a Dirac mass term with and the three left-handed neutrinos $\nu_{L\alpha}^{}(\alpha=e,\mu,\tau)$, i.e.
 \begin{eqnarray}
\mathcal{L}&\supset& -\sum_{\alpha=e,\mu,\tau \atop i=1,2}^{} (m_D^{})_{\alpha i} \bar{\nu}_{L\alpha}^{} \nu_{Ri}^{} +\textrm{H.c.}^{} ~~\textrm{with}~~m_D^{} = y\langle\phi\rangle\,. \nonumber\\
&&
\end{eqnarray}

In the limiting case,
 \begin{eqnarray}
m_N^{}\gg m_D^{}\,,~\mu_S^{}\,,
\end{eqnarray}
the left-handed neutrinos $\nu_L^{}$ can obtain a tiny Majorana mass term,
 \begin{eqnarray}
 \label{num}
\mathcal{L}&\supset& -\frac{1}{2}m_\nu^{} \bar{\nu}_L^{} \nu_L^c +\textrm{H.c.}~~\textrm{with}\nonumber\\
&&m_\nu^{}=m_D^{} \frac{1}{m_N^\dagger}\mu_S^{}\frac{1}{m_N^{\ast}}m_D^{T}\,.
\end{eqnarray}
This is an application of the so-called inverse seesaw mechanism.

The neutrino masses (\ref{num}) can be understood in Fig. \ref{numass}. It should be noted that only two right-handed neutrinos $\nu_{R1,2}^{}$ and the same number of fermion singlets $S_{R1,2}^{}$ participate in the neutrino mass generation. Such rank-2 neutrino mass matrix can only have two nonzero eigenvalues. In this sense, we may refer to our model as a minimal inverse seesaw \cite{sv1980}.

\section{Baryon asymmetry}

In this section we shall demonstrate how to generate the baryon asymmetry in our models.

\subsection{The heavy fermion or Higgs singlet decays}

\begin{figure*}
\vspace{7.5cm} \epsfig{file=fdecay, bbllx=8cm, bblly=6.0cm,
bburx=18cm, bbury=16cm, width=8cm, height=8cm, angle=0,
clip=0} \vspace{-8.5cm} \caption{\label{fdecay} The heavy fermion singlet decays.}
\end{figure*}

As shown in  Fig. \ref{fdecay}, the heavy fermion singlet $X_b^{}$ have two decay modes,
\begin{eqnarray}
X_b^{} \rightarrow S_R^{c}+\xi\,,~~ X_b^{} \rightarrow S_R^{}+ \xi^\ast_{} \,.
\end{eqnarray}
As long as the CP is not conserved, we can expect a CP asymmetry in the above decays,
\begin{eqnarray}
\varepsilon_{X_b}^{}&=& \frac{\Gamma(X_b^{} \rightarrow S_R^c+\xi)- \Gamma(X_b^{} \rightarrow S_R^{}+\xi^\ast_{})}{\Gamma_{X_b^{}}^{}}\,,
\end{eqnarray}
with $\Gamma_{\Sigma_a}^{}$ being the total decay width,
\begin{eqnarray}
\Gamma_{X_b}^{}&=& \Gamma(X_b^{} \rightarrow S_R^{c}+\xi)+\Gamma( X_b^{} \rightarrow S_R^{}+ \xi^\ast_{})\,.
\end{eqnarray}
We can calculate the decay width at tree level and the CP asymmetry at one-loop order, i.e.
\begin{eqnarray}
\Gamma_{X_b}^{}&=&\frac{1}{16\pi} \left(g_X^\dagger g_X^{}\right)_{bb}^{}M_{X_b}^{}\\
[2mm]
\varepsilon_{X_b}^{}&=&-\frac{1}{16\pi} \sum_{d\neq b}^{}\frac{\textrm{Im}\left\{\left[\left(g_{X}^T g_{X}^{\ast}\right)_{bd}\right]^2_{}\right\}}{\left(g_X^\dagger g_X^{}\right)_{bb}^{}}\left\{\frac{M_{X_b}^{}M_{X_d}^{}}{M_{X_d}^2- M_{X_b}^2}\right.\nonumber\\
&&\left.+\frac{2M_{X_d}^{}}{M_{X_b}^{}}\left[1-\left(1+\frac{M_{X_d}^{2}}{M_{X_b}^{2}}\right)\ln\left(1+\frac{M_{X_b}^{2}}{M_{X_d}^{2}}\right)\right]\right\}\,.\nonumber\\
&&
\end{eqnarray}
For a nonzero CP asymmetry $\varepsilon_{X_b}^{}$, we need at least two heavy fermion singlets $X_{1,...,n\geq 2}^{}$.

\begin{figure*}
\vspace{9cm} \epsfig{file=sdecay, bbllx=5.5cm, bblly=6.0cm,
bburx=15.5cm, bbury=16cm, width=8cm, height=8cm, angle=0,
clip=0} \vspace{-8.5cm} \caption{\label{sdecay} The heavy Higgs singlet decays.}
\end{figure*}

As for the heavy Higgs singlet $\Sigma_a^{}$, their decay modes are
\begin{eqnarray}
\Sigma_a^{} \rightarrow  S_R^{c}+S_R^{c}\,,~~ \Sigma_a^{} \rightarrow \xi^\ast_{}+\xi^\ast_{} \,.
\end{eqnarray}
The relevant diagrams are shown in Fig. \ref{sdecay}. The tree-level decay width and the one-loop CP asymmetry can be calculated by
\begin{eqnarray}
\Gamma_{\Sigma_a}^{}&=&\Gamma(\Sigma_a^{} \rightarrow S_R^{c}+S_R^{c})  + \Gamma( \Sigma_a^{} \rightarrow \xi^\ast_{}+\xi^\ast_{})\nonumber\\
&=&\Gamma( \Sigma_a^{\ast} \rightarrow  S_R^{}+S_R^{}  )+\Gamma( \Sigma^\ast_{a} \rightarrow \xi+\xi)\nonumber\\
&=&\frac{1}{8\pi}\left[\textrm{Tr}\left(g_{\Sigma_a^{}}^\dagger g_{\Sigma_a}^{}\right)+\frac{\rho_{\Sigma_a}^2}{M_{\Sigma_b}^2}\right]M_{\Sigma_a}^{}\,,
\end{eqnarray}
\begin{eqnarray}
\varepsilon_{\Sigma_a}^{}&=&2 \frac{\Gamma(\Sigma_a^{} \rightarrow S_R^{c}+S_R^{c}  )-\Gamma( \Sigma_a^{\ast} \rightarrow  S_R^{}+S_R^{}  )}{\Gamma_{\Sigma_a^{}}^{}}\nonumber\\
&=&2\frac{\Gamma( \Sigma^\ast_{a} \rightarrow \xi+\xi)-\Gamma( \Sigma_a^{} \rightarrow \xi^\ast_{}+\xi^\ast_{})}{\Gamma_{\Sigma_a^{}}^{}}\nonumber\\
&=& -\frac{1}{\pi}\sum_{c\neq a}^{}\frac{\textrm{Im}\left[\textrm{Tr}\left(g_{\Sigma_a}^\dagger g_{\Sigma_c}^{}\right)\rho_{\Sigma_a}^{}\rho_{\Sigma_c}^{}\right]}{\textrm{Tr}\left(g^\dagger_{\Sigma_a} g_{\Sigma_a}^{}\right)+ \frac{\rho_{\Sigma_a}^2}{M_{\Sigma_a}^{2}}}\frac{1}{M_{\Sigma_c}^2-M_{\Sigma_a}^2}\,.\nonumber\\
&&
\end{eqnarray}
A nonzero CP asymmetry $\varepsilon_{\Sigma_a}^{}$ requires the existence of at least two heavy Higgs singlets $\Sigma_{1,...,n\geq 2}^{}$.

After the heavy fermion singlets $X_b^{}$ or the heavy Higgs singlets $\Sigma_a^{}$ go out of equilibrium, their decays can generate an asymmetry $A_S^{}$ stored in the fermion singlets $S_R^{}$. For demonstration, we can simply assume the lightest heavy fermion singlet $X_1^{}$ or the lightest heavy Higgs singlet $\Sigma_1^{}$ to be much lighter than the other heavy Higgs or fermion singlets. The $A_S^{}$ asymmetry then should mainly come from the $X_1^{}$ or $\Sigma_1^{}$  decays, i.e.
\begin{eqnarray}
\label{xasymmetry}
A_S^{}&=& \varepsilon_{X_1/\Sigma_1 }^{}\left(\frac{n^{eq}_{\Sigma_1/X_1} }{s}\right)\left|_{T=T_D^{}}^{}\right.,
\end{eqnarray}
where the symbols $n^{eq}_{X_1/\Sigma_1}$ and $T_D^{}$ respectively are the equilibrium number density and the decoupled temperature of the lightest heavy Higgs or fermion singlets, while the character $s$ is the entropy density of the universe. In this case, the CP asymmetries $\varepsilon_{X_1/\Sigma_1}^{}$ can be simplified by
\begin{eqnarray}
\varepsilon_{X_1}^{}&\simeq & \frac{1}{8\pi}\frac{\textrm{Im}\left[\left(g_{X}^T \mu_S^{} g_{X}^{}\right)_{11}\right] M_{X_1}^{}}{\left(g_X^\dagger g_X^{}\right)_{11}^{}\langle\xi\rangle^2_{}}\nonumber\\
&\lesssim& \frac{1}{8\pi}\frac{\mu_{\textrm{max}}^{} M_{X_1}^{}}{\langle\xi\rangle^2_{}} \,,
\end{eqnarray}
\begin{eqnarray}
\varepsilon_{\Sigma_1}^{}&\simeq & \frac{1}{\pi}\frac{\textrm{Im}\left[\textrm{Tr}\left(g_{\Sigma_1}^\dagger \mu_S^{} \right)\right] \rho_{\Sigma_1}^{}}{\left[\textrm{Tr}\left(g^\dagger_{\Sigma_1} g_{\Sigma_1}^{}\right)+ \frac{\rho_{\Sigma_1^{}}^2}{M_{\Sigma_1}^{2}} \right] \langle\xi\rangle^2_{} }\nonumber\\
&\leq&  \frac{1}{\pi}\frac{\textrm{Im}\left[\textrm{Tr}\left(g_{\Sigma_1}^\dagger \mu_S^{} \right)\right] \rho_{\Sigma_1}^{}}{2\sqrt{\textrm{Tr}\left(g^\dagger_{\Sigma_1} g_{\Sigma_1}^{}\right)\frac{\rho_{\Sigma_1}^2}{M_{\Sigma_1}^{2}} } \langle\xi\rangle^2_{} }\nonumber\\
&\lesssim&   \frac{1}{2\pi}\frac{ \mu_{\textrm{max}}^{} M_{\Sigma_1}^{}}{ \langle\xi\rangle^2_{} }\,,
\end{eqnarray}
with $\mu_{\textrm{max}}^{} $ being the largest eigenvalue of the Majorana mass matrix $\mu_S^{}$.

Note the Majorana masses $\mu_S^{}$ can lead to an $S_R^{}-S_R^c$ oscillation, which tends to wash out the $A_S^{}$ asymmetry. However, this oscillation will not go into equilibrium before the sphalerons stop working, i.e.\begin{eqnarray}
\label{ssbar}
&&\left[\Gamma_{S_R^{}-S_R^c}^{}>H(T)\right]\left|_{T\ll  100\,\textrm{GeV}}^{}\right.\nonumber\\
&&\textrm{with}~~\Gamma_{S_R^{}-S_R^c}^{}\sim\left\{\begin{array}{cc} \frac{\mu_S^2}{T}&\textrm{for}~~T>m_N^{}\,,\\
[2mm]
\frac{\mu_S^2}{m_N^{}}&\textrm{for}~~T<m_N^{}\,.\end{array}\right.
\end{eqnarray}
Here $H(T)$ is the Hubble constant to be given later. This means we need not take the Majorana masses $\mu_S^{}$ into account before the electroweak symmetry breaking.

\subsection{The lepton-to-baryon conversion}

The asymmetry $A_S^{}$ stored in the fermion singlets $S_R^{}$ will lead to a lepton asymmetry stored in the SM lepton doublets $l_L^{}$ because of the related Yukawa interactions in Eq. (\ref{lag}). The sphaleron processes then can partially transfer this lepton asymmetry to a baryon asymmetry. We can impose a global symmetry of lepton number under which the right-handed neutrinos $\nu_R^{}$ and the fermion singlets $S_{R}^{}$ carry the lepton numbers $+1$ and $-1$, respectively. The global lepton number in our models (\ref{lag}) then is softly broken by the Majorana masses of the heavy fermion singlets $X_R^{}$ or the cubic couplings of the heavy Higgs singlets $\Sigma$ to the $U(1)_{B-L}^{}$ Higgs singlet $\xi$. For such global lepton number, the $A_S^{}$ asymmetry equals to a lepton asymmetry $L_S^{}$ stored in the fermion singlets $S_R^{}$. The lepton-to-baryon conversion thus will not be affected by the $U(1)_{B-L}^{}$ gauge symmetry breaking. Therefore, we can conveniently analysize the lepton-to-baryon conversion after the $U(1)_{B-L}^{}$ symmetry breaking. For this purpose, we denote $\mu_{q}^{}$, $\mu_d^{}$, $\mu_u^{}$, $\mu_l^{}$, $\mu_e^{}$, $\mu_\nu^{}$, $\mu_S^{}$ and $\mu_\phi^{}$ for the chemical potentials of the fields $q_{L}^{}$, $d_{R}^{}$, $u_{R}^{}$, $l_L^{}$, $e_R^{}$, $\nu_R^{}$, $S_R^{}$ and $\phi$. The SM Yukawa interactions are in equilibrium and hence yield \cite{ht1990},
\begin{eqnarray}
\label{chemical1}
-\mu_{q}^{}+\mu_{d}^{}-\mu_{\phi}^{}&=&0\,,\\
\label{chemical2}
 -\mu_{q}^{}+\mu_{u}^{}+\mu_{\phi}^{}&=&0\,,\\
 \label{chemical3}
 -\mu_{l}^{}+\mu_{e}^{}-\mu_{\phi}^{}&=&0\,,\\
 -\mu_{l}^{}+\mu_{\nu}^{} + \mu_\phi^{}&=&0\,,
\end{eqnarray}
the fast sphalerons constrain \cite{ht1990},
\begin{eqnarray}
\label{chemical4}
3\mu_{q}^{}+\mu_{l}^{}&=&0\,,
\end{eqnarray}
while the neutral hypercharge in the universe requires \cite{ht1990},
\begin{eqnarray}
\label{chemical5}
3\left( \mu_{q}^{} -\mu_{d}^{}+2\mu_{u}^{}-\mu_{l}^{} -\mu_{e}^{}\right)-2\mu_{\phi}^{} =0\,.
\end{eqnarray}
In addition, the mass term between the right-handed neutrinos $\nu_R^{}$ and the fermion singlets $S_R^{}$ are also in equilibrium. This means
\begin{eqnarray}
\label{chemical6}
\mu_S^{}+\mu_\nu^{}&=&0\,.
\end{eqnarray}
In the above Eqs. (\ref{chemical1}-\ref{chemical6}), we have identified the chemical potentials of the different-generation fermions because the Yukawa interactions establish an equilibrium between the different generations. By solving Eqs. (\ref{chemical1}-\ref{chemical6}), we can express the chemical potentials by
\begin{eqnarray}
\!\!\!\!&&\mu_\phi^{}=-\frac{4}{7}\mu_l^{}\,,~~\mu_q^{}=-\frac{1}{3}\mu_l^{}\,,~~\mu_d^{}=-\frac{19}{21}\mu_l^{}\,,~~\mu_u^{}=\frac{5}{21}\mu_l^{}\,,\nonumber\\
\!\!\!\!&&\mu_{e}^{}=\frac{3}{7}\mu_l^{}\,,~~\mu_{\nu}^{}=\frac{11}{7}\mu_l^{}\,,~~\mu_S^{}=-\frac{11}{7}\mu_l^{}\,.
\end{eqnarray}

Now the global baryon number can be given by
\begin{eqnarray}
B= 3(2\mu_q^{} + \mu_d^{} + \mu_u^{}) = -4 \mu_l^{}\,.
\end{eqnarray}
As for the global lepton number, it should be
\begin{eqnarray}
\label{lll}
L= 3(2\mu_L^{}+\mu_e^{}) + 2(\mu_\nu^{}-\mu_S^{}) = \frac{95}{7}\mu_l^{}\,.
\end{eqnarray}
The baryon and lepton numbers then can be transferred from a conserved $B-L$ number, i.e.
\begin{eqnarray}
\label{bl1}
B=\frac{28}{123}(B-L)\,,~~L=-\frac{95}{123}(B-L)\,.
\end{eqnarray}
If the quasi-Dirac fermions $N=\nu_R^{}+S_R^c$ keep relativistic before the electroweak symmetry breaking, the final baryon number can be given by (\ref{bl1}). Alternatively, the $N$ fermions have become non-relativistic and have completely decayed before the electroweak symmetry breaking. In this case, the global lepton number (\ref{lll}) should be modified as
\begin{eqnarray}
L= 3(2\mu_L^{}+\mu_e^{}) = \frac{51}{7}\mu_l^{}\,,
\end{eqnarray}
and hence the baryon and lepton numbers from the conserved $B-L$ number should be
\begin{eqnarray}
\label{bl2}
B=\frac{28}{79}(B-L)\,,~~L=-\frac{51}{79}(B-L)\,.
\end{eqnarray}

\subsection{A numerical example}

For simplicity, we consider the weak washout condition \cite{kt1990},
\begin{eqnarray}
\label{weak}
\!\!\!\!\left.\left[\Gamma_{\Sigma_1/X_1}^{}< H(T)=\left[\frac{8\pi^{3}_{}g_{\ast}^{}(T)}{90}\right]^{\frac{1}{2}}_{}\frac{T^2_{}}{M_{\textrm{Pl}}^{}}\right]\right|_{T=M_{\Sigma_1^{}/X_1^{}}}^{}\,.
\end{eqnarray}
The final baryon asymmetry then can approximate to \cite{kt1990}
\begin{eqnarray}
\label{bauf4}
B^f_{}\sim c \frac{\varepsilon_{\Sigma_1/X_1}^{}}{g_\ast^{}}~~\textrm{with}~~c=-\frac{28}{79}~\textrm{or}~-\frac{28}{123}\,.
\end{eqnarray}
Here $H(T)$ is the Hubble constant with $M_{\textrm{Pl}}^{}\simeq 1.22\times 10^{19}_{}\,\textrm{GeV}$ being the Planck mass and $g_{\ast}^{}(T)=123$ being the relativistic degrees of freedom (the SM fields plus the seven neutral fermions ($\nu_{R1,2}^{},S_{R1,2}^{},\chi_{R1,2}^{},\zeta_R^{}$), the $U(1)_{B-L}^{}$ Higgs singlet $\xi$ and the $U(1)_{B-L}^{}$ gauge boson.).

As an example, we choose
\begin{eqnarray}
\langle\xi\rangle= 40\,\textrm{TeV}\,,
\end{eqnarray}
and then take
\begin{eqnarray}
\!\!\!\!\!\!\!\!\!\!\!\!&&M_{\Sigma_1^{}}^{}=10^{14}_{}\,\textrm{GeV}\,,~\rho_{\Sigma_1^{}}^{}=3\times 10^{12}_{}\,\textrm{GeV}\,, ~g_{\Sigma_1^{}}^{}= \mathcal{O}(0.03)\,; \nonumber\\
\!\!\!\!\!\!\!\!\!\!\!\!&&\textrm{or}~~M_{X_1^{}}^{}=10^{14}_{}\,\textrm{GeV}\,,~g_{X}^{}= \mathcal{O}(0.03)\,.
\end{eqnarray}
With these inputting, we can have
\begin{eqnarray}
\label{output1}
\mu_S^{}= \mathcal{O}(10\,\textrm{eV})\,,
\end{eqnarray}
as well as
\begin{eqnarray}
\frac{\Gamma_{\Sigma_1^{}/X_1^{}}^{}}{H(T)}\left|_{T=M_{\Sigma_1^{}/X_1^{}}^{}}^{}\right.=\mathcal{O}(0.1)\,,~~\varepsilon_{\Sigma_1^{}/X_1^{}}^{\textrm{max}}=\mathcal{O}( 10^{-5}) \,.
\end{eqnarray}
So, the final baryon asymmetry (\ref{bauf4}) can arrive at the observed value $B^f_{}\sim 10^{-10}_{}$.

We further take
\begin{eqnarray}
f\sim \mathcal{O}(10^{-3}_{}-0.1)\,,~y\sim \mathcal{O}(10^{-2}_{}-1)\,,
\end{eqnarray}
to give
\begin{eqnarray}
\label{output2}
\!\!m_N^{} \sim \mathcal{O}(10-1000\,\textrm{GeV})\,, ~~m_D^{}\sim \mathcal{O}(1-100\,\textrm{GeV})\,.
\end{eqnarray}
By inserting the outputs (\ref{output1}) and (\ref{output2}) into the inverse seesaw (\ref{num}), we can obtain the neutrino masses $m_\nu^{}=\mathcal{O}(0.1\,\textrm{eV})$.

For the above parameter choice, we also check the $S_R^{}-S_R^c$ oscillation (\ref{ssbar}) induced by the Majorana masses $\mu_S^{}$. We find this oscillation can not go into equilibrium before the electroweak symmetry breaking and hence it will not affect the production of the baryon asymmetry.

\section{Dark fermions}

As shown in Eq. (\ref{dm}), the two neutral fermions $\chi_{R1,2}^{}$ have a Yukawa coupling with the $U(1)_{B-L}^{}$ Higgs singlet $\xi$ so that they can form a Dirac particle \cite{pry2016,gu2019-2,gu2019-3} after the $U(1)_{B-L}^{}$ symmetry breaking, i.e.
\begin{eqnarray}
\mathcal{L} &\supset&  i \bar{\chi}\gamma^\mu_{}\partial_\mu^{} \chi - m_\chi^{} \bar{\chi}\chi \nonumber\\
&& \textrm{with}~~ \chi = \chi_{R1}^{}+\chi_{R2}^{c}\,,~~ m_\chi^{}= y_{\chi}^{} \langle\xi\rangle\,.
 \end{eqnarray}
Meanwhile, the another neutral fermion $\zeta_R^{}$ has no Yukawa couplings so that it should be massless.

Now the Dirac fermion $\chi$ is stable and hence leaves a dark matter relic density. The dark matter annihilation and scattering could be determined by the gauge interactions,
\begin{eqnarray}
\mathcal{L} &\supset &g_{B-L}^{} Z_{B-L}^\mu \left[\sum_{i=1}^{3}\left(\frac{1}{3}\bar{d}_i^{}\gamma_\mu^{} d_i^{} + \frac{1}{3}\bar{u}_{i}^{}\gamma_\mu^{}u_{i}^{}-\bar{e}_{i}^{}\gamma_\mu^{} e_{i}^{}  \right.\right.\nonumber\\
&&\left.\left.-\bar{\nu}_{Li}^{}\gamma_\mu^{}\nu_{Li}^{}\right)-\bar{\nu}_{R1}^{}\gamma_\mu^{}\nu_{R1}^{} -\bar{\nu}_{R1}^{}\gamma_\mu^{}\nu_{R1}^{} \right.\nonumber\\
&&\left.+\frac{1}{2}\bar{S}_{R1}^{}\gamma_\mu^{} S_{R1}^{}+\frac{1}{2}\bar{S}_{R1}^{}\gamma_\mu^{} S_{R1}^{}-\frac{5}{2} \bar{\zeta}_{R}^{}\gamma_\mu^{}\zeta_{R}^{} \right.\nonumber\\
&&\left. + \frac{1}{4} \bar{\chi}\gamma_\mu^{}\left(\sqrt{153}+\gamma_5^{}\right)\chi \right]\,.
\end{eqnarray}
The gauge coupling $g_{B-L}^{}$ then should have an upper bound from the perturbation requirement, i.e.
\begin{eqnarray}
\label{gbl}
\frac{\sqrt{153}}{4}g_{B-L}^{} < \sqrt{4\pi} \Rightarrow g_{B-L}^{}< \sqrt{ \frac{64\,\pi}{153}}\,,
\end{eqnarray}
while the gauge boson mass $M_{Z_{B-L}}^{}$ should be
\begin{eqnarray}
M_{Z_{B-L}^{}}^{}&= &\frac{1}{ \sqrt{2}} g_{B-L}^{} \langle \xi\rangle \,.
\end{eqnarray}
Currently the experimental constraints on the $U(1)_{B-L}^{}$ symmetry breaking is \cite{afpr2017,klq2016}
\begin{eqnarray}
\label{low}
\frac{M_{Z_{B-L}^{}}^{}}{g_{B-L}^{} }  \gtrsim 7 \,\textrm{TeV} \Rightarrow \langle \xi \rangle \gtrsim 10 \,\textrm{TeV}\,.
\end{eqnarray}

The thermally averaging dark matter annihilating cross section can be given by \cite{bhkk2009}
\begin{eqnarray}
\label{ann}
\langle\sigma_{\textrm{A}}^{} v_{\textrm{rel}}^{} \rangle&=& \sum_{f=d,u,e,\nu_{L}^{},\nu_R^{},S_R^{},\zeta_R^{}}^{}\langle\sigma(\chi+\chi^c_{}\rightarrow f+f^c_{}) v_{\textrm{rel}}^{}\rangle \nonumber\\
&\simeq &\frac{ 13311 g_{B-L}^4}{128\pi} \frac{m_\chi^2}{M_{Z_{B-L}^{}}^4} \nonumber\\
&=& \frac{13311}{32\pi} \frac{m_\chi^2}{\langle\xi\rangle^4_{}} =  \frac{13311}{32\pi} \frac{y_{\chi}^2}{\langle\xi\rangle^2_{}}  \,,
\end{eqnarray}
where we have assumed
\begin{eqnarray}
\label{y34}
4m_\chi^2 \ll M_{Z_{B-L}^{}}^2 &\Rightarrow & y_{\chi}^{2}\ll \frac{1}{8} g_{B-L}^{2} < \frac{8\pi}{153}\nonumber\\
&\Rightarrow& y_\chi^{}< \sqrt{\frac{8\pi}{153}}\,.
\end{eqnarray}
The dark matter relic density then can approximate to \cite{pdg2018}
\begin{eqnarray}
\label{relic}
\Omega_\chi^{} h^2 \simeq \frac{0.1\,\textrm{pb}}{\langle \sigma_{\textrm{A}}^{} v_{\textrm{rel}}^{} \rangle} &=&0.1\,\textrm{pb}\times \frac{32\pi \langle\xi\rangle^4_{}}{13311 m_{\chi}^2}\nonumber\\
&=&0.1\,\textrm{pb}\times \frac{32\pi \langle\xi\rangle^2_{}}{13311 y_{\chi}^2} \,.
\end{eqnarray}

Due to Eq. (\ref{y34}), the VEV $\langle\xi\rangle$ should have an upper bound,
\begin{eqnarray}
\langle\xi\rangle &\simeq& \left(\frac{13311 y_{\chi}^2 \Omega_\chi^{} h^2}{32 \pi \times  0.1\,\textrm{pb}} \right)^{\frac{1}{2}}_{}\nonumber\\
&=& 97 \,\textrm{TeV}\left(\frac{y_{\chi}^{}}{\sqrt{8\pi/153}}\right) \left(\frac{\Omega_\chi^{} h^2}{0.11}\right)^{\frac{1}{2}}_{}\nonumber\\
&<&97\,\textrm{TeV}\left(\frac{\Omega_\chi^{} h^2}{0.11}\right)^{\frac{1}{2}}_{}\,,
\end{eqnarray}
besides the experimental limit (\ref{low}). The dark matter mass,
\begin{eqnarray}
\label{dm1}
m_\chi^{} &\simeq &\left(0.1\,\textrm{pb}\times \frac{32\pi\langle\xi\rangle^4_{}}{13311 \Omega_\chi^{} h^2} \right)^{\frac{1}{2}}_{} \nonumber\\
&=& 5\,\textrm{TeV}\left(\frac{\langle \xi\rangle }{34.5\,\textrm{TeV}}\right)^2_{}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{} \,,
\end{eqnarray}
thus should be in the range,
\begin{eqnarray}
\label{dm2}
&&420\,\textrm{GeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\lesssim
m_\chi^{} < 40\,\textrm{TeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\nonumber\\
&&\textrm{for}~~10\,\textrm{TeV} \lesssim \langle\xi\rangle < 97\,\textrm{TeV}\,.
\end{eqnarray}

The gauge interactions can also result in a dark matter scattering off nucleons. The spin-independent cross section is given by \cite{jkg1996}
\begin{eqnarray}
\sigma_{\chi N}^{}&=& \frac{153 g_{B-L}^4}{16 \pi} \frac{\mu_r^2 }{M_{Z_{B-L}^{}}^4} \nonumber\\
&=& \frac{153 }{4\pi} \frac{\mu_r^2 }{\langle\xi\rangle^4_{}}= \frac{8}{87} \frac{\mu_r^2 }{m_\chi^2} \frac{0.1\,\textrm{pb}}{\Omega_\chi^{} h^2_{} }\,.
\end{eqnarray}
Here $\mu_r^{}=m_N^{}m_\chi^{}/(m_N^{}+m_\chi^{})$ is a reduced mass with $m_N^{}$ being the nucleon mass. As the dark matter is much heavier than the nucleon, we can simply read
\begin{eqnarray}
\sigma_{\chi N}^{}&=& 3\times 10^{-45}_{}\,\textrm{cm}^2_{}\left(\frac{\mu_r^{}}{940\,\textrm{MeV}}\right)^2_{} \left(\frac{0.11}{\Omega_\chi^{} h^2_{}}\right)\nonumber\\
&&\times \left( \frac{5\,\textrm{TeV}}{m_\chi^{}}\right)^2_{} \,.
\end{eqnarray}
To satisfy the dark matter direct detection results \cite{cui2017,aprile2018}, the dark matter mass should have a low limit,
\begin{eqnarray}
\label{dm3}
m_\chi^{} \gtrsim 5\,\textrm{TeV}\,.
\end{eqnarray}
Therefore, the allowed dark matter mass should be
\begin{eqnarray}
\label{range}
&&5\,\textrm{TeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\lesssim
m_\chi^{} < 40\,\textrm{TeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\nonumber\\
&&\textrm{for}~~34.5\,\textrm{TeV} \lesssim \langle\xi\rangle < 97\,\textrm{TeV}\,.
\end{eqnarray}

The fermion $\zeta_R^{}$ is massless so that it will affect the effective neutrino number which is stringently constrained by the BBN. We hope the massless $Z_R^{}$ can decouple above the QCD scale and hence give a negligible contribution to the effective neutrino number. For this purpose, we need consider the annihilations of the $\zeta_R^{}$ fermion into the light species,
\begin{eqnarray}
\sigma_{\zeta}^{} &=&\sum_{f=d,u,s,e,\mu,\nu_L^{}}^{}\sigma(\zeta_R^{}+\zeta_R^c\rightarrow f+f^c) \nonumber\\
&=& \frac{75}{32\pi}\frac{g_{B-L}^4}{M_{Z_{B-L}}^4}s =  \frac{75}{8\pi}\frac{s}{\langle\xi\rangle^4_{}}\,,
\end{eqnarray}
with $s$ being the Mandelstam variable. The interaction rate then should be \cite{gnrrs2003}
\begin{eqnarray}
\Gamma_{\zeta}^{} &=&\frac{\frac{T}{32\pi^4_{}}\int^{\infty}_{0} s^{3/2}_{} K_1^{}\left(\frac{\sqrt{s}}{T}\right) \sigma_{\zeta}^{}ds }{\frac{2}{\pi^2_{}}T^3_{}}= \frac{18}{\pi^3_{}} \frac{T^5_{}}{\langle\xi\rangle^4_{}}\,,
\end{eqnarray}
with $K_1^{}$ being a Bessel function. We take $g_\ast^{}(300\,\textrm{MeV})\simeq 59.75$ and then find
\begin{eqnarray}
\left[\Gamma_{\zeta}^{} < H(T)\right]_{T\gtrsim 300\,\textrm{MeV}}^{}~~\textrm{for}~~\langle\xi\rangle \gtrsim 37\,\textrm{TeV}\,.
\end{eqnarray}
So, if the massless $\zeta_R^{}$ is harmless, the dark matter mass (\ref{range}) should be modified, i.e.
\begin{eqnarray}
&&5.7\,\textrm{TeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\lesssim
m_\chi^{} < 40\,\textrm{TeV}\left(\frac{0.11}{\Omega_\chi^{} h^2}\right)^{\frac{1}{2}}_{}\nonumber\\
&&\textrm{for}~~37\,\textrm{TeV} \lesssim \langle\xi\rangle < 97\,\textrm{TeV}\,.
\end{eqnarray}

\section{Conclusion}

In this paper, we have simultaneously explained the neutrino mass, the baryon asymmetry and the dark matter by resorting to a $U(1)_{B-L}^{}$ gauge symmetry. In order to cancel the gauge anomalies, we introduce seven neutral fermions including two usual right-handed neutrinos. After a Higgs singlet develops its VEV for spontaneously breaking the $U(1)_{B-L}^{}$ symmetry, two neutral fermions can obtain their small Majorana masses by integrating out some heavy scalar or fermion singlets, meanwhile, they can have a sizable mass term with the right-handed neutrinos. After the SM Higgs doublet drives the electroweak symmetry breaking, the two right-handed neutrinos and the three left-handed neutrinos can acquire their Dirac masses. We thus can realize an inverse seesaw to give a neutrino mass matrix with two nonzero eigenvalues. Within this framework, the heavy scalar or fermion singlet decays can generate the cosmic baryon asymmetry in association with the sphaleron processes. On the other hand, another two neutral fermions can form a stable Dirac particle due to their Yukawa coupling with the $U(1)_{B-L}^{}$ Higgs singlet. This Dirac fermion can serve as a dark matter particle. As for the seventh neutral fermion, it keeps massless but decouples early.

\textbf{Acknowledgement}: This work was supported by the National Natural Science Foundation of China under Grant No. 11675100 and the Recruitment Program for Young Professionals under Grant No. 15Z127060004.


\section{Introduction}
If an alphabet $\Sigma$ is equipped by a linear order $<$, this order can be extended to the lexicographic
ordering $<_\ell$ on $\Sigma^*$ as $u<_\ell v$ if and only if either $u$ is a proper prefix of $v$ or
$u=xay$ and $v=xbz$ for some $x,y,z\in\Sigma^*$ and letters $a<b$. So any language $L\subseteq \Sigma^*$
can be viewed as a linear ordering $(L,<_\ell)$. 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,<_\ell)$ for some language $L\subseteq\{a,b\}^*$.
A linear ordering (or an order type) is called \emph{regular} or \emph{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~\cite{DBLP:journals/fuin/BloomE10} that an ordinal is regular if and only if it is less than $\omega^\omega$
and is context-free if and only if it is less than $\omega^{\omega^\omega}$. Also, the Hausdorff rank~\cite{rosenstein}
of any scattered regular (context-free, resp.) ordering is less than $\omega$ ($\omega^\omega$, resp)~\cite{ITA_1980__14_2_131_0,10.1007/978-3-642-29344-3_25}.

It is known~\cite{GelleIvanTCS} 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 \emph{prefix} grammars.
Also, the isomorphism problem of regular orderings is decidable as well~\cite{DBLP:journals/ita/Thomas86,BLOOM200555}.
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~\cite{ESIK2011107}.

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,<_\ell)$ is well-ordered or scattered~\cite{10.1007/978-3-642-22321-1_19}
and the two algorithms are quite similar.
In an earlier paper~\cite{GelleIvanGandalf} we showed that it is undecidable for a scattered context-free ordering
of rank $2$
whether its order type is $\omega+(\omega+\zeta)\times\omega$, 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$, $\omega$ and $-\omega$).

\section{Notation}
A \emph{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\in 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\to Q_2$, where $(Q_1,<_1)$ and $(Q_2,<_2)$ are some linear orderings,
is called an \emph{(order) embedding}
if for each $x,y\in 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\preceq Q_2$.
If $h$ is also surjective, $h$ is an \emph{isomorphism}, in which case the two orderings are \emph{isomorphic}.
An isomorphism class is called an \emph{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 ($\mathbb{Z}$), the positive integers ($\mathbb{N}$) and the negative integers ($\mathbb{N}_{-}$) whose order type is denoted $\zeta$, $\omega$ and $-\omega$ respectively.
Order types of the finite sets are denoted by their cardinality, and $[n]$ denotes $\{1,\ldots,n\}$ for each $n\geq 0$, ordered in the standard way.

The ordered sum $\sum_{x\in Q} Q_x$, where $Q$ is some linear ordering and for each $x \in Q$, $Q_x$ is a linear ordering,
is defined as the ordering with domain $\{(x,q):x\in Q,q\in 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\times o_2$.
If $Q=[2]$, then the sum is usally written as $Q_1+Q_2$.

If $(Q,<)$ is a linear ordering and $Q'\subseteq 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 \emph{dense} if it has at least two elements and for each $x,y\in Q$ where $x<y$ there exists a $z\in Q$ such that $x<z<y$.
A linear ordering is \emph{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 \emph{well-ordering} if it has no subordering of type $-\omega$. 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\preceq o_2$ to denote $o_1$ embeds into $o_2$.
The well-ordered order types are called \emph{ordinals}.
For any set $\Omega$ of ordinals, $(\Omega,<)$ is well-ordered by the relation $o_1\prec o_2~\Leftrightarrow~\hbox{``}o_1\hbox{ 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\prec 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.~\cite{rosenstein} or~\cite{jalex}.

Hausdorff classified the countable scattered linear orderings with respect to their rank.
We will use the definition of the Hausdorff rank from \cite{10.1007/978-3-642-29344-3_25},
which slightly differs from the original one (in which $H_0$ contains only the empty ordering and the singletons,
and the classes $H_\alpha$ are not required to be closed under finite sum, see e.g.~\cite{rosenstein}).
For each countable ordinal $\alpha$, we define the class $H_\alpha$ of countable linear orderings as follows.
$H_0$ consists of all finite linear orderings, and
when $\alpha> 0$ is a countable ordinal,
then $H_\alpha$ is the least class of linear orderings closed under finite ordered sum and isomorphism
which contains all linear orderings of the form $\sum_{i\in\mathbb{Z}} Q_i$,
where each $Q_i$ is in $H_{\beta_i}$ for some $\beta_i < \alpha$.

By Hausdorff's theorem, a countable linear order $Q$ is scattered if and only if it belongs to $H_\alpha$ for some countable ordinal $\alpha$.
The \emph{rank} $r(Q)$ of a countable scattered linear ordering is the least ordinal $\alpha$ with $Q \in H_\alpha$.

As an example, $\omega$, $\zeta$, $-\omega$ and $\omega+\zeta$ or any finite sum of the form $\mathop\sum\limits_{i\in[n]}o_i$ with $o_i\in\{\omega, -\omega,1\}$ for each $i\in[n]$
each have rank $1$ while $(\omega+\zeta)\times\omega$ has rank $2$.

Let $\Sigma$ be an alphabet (a finite nonempty set) and let $\Sigma^*$ ($\Sigma^+$, resp) stand for the set of all (all nonempty, resp)
finite words over $\Sigma$, $\varepsilon$ for the empty word, $|u|$ for the length of the word $u$, $u\cdot v$ or simply $uv$ for the concatenation of $u$ and $v$. A \emph{language} is an arbitrary subset $L$ of $\Sigma^*$.
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 $\Sigma^*$ as
follows:
\begin{itemize}
	\item $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\in\Sigma^*$ and letters $a < b$,
	\item $u <_p v$ if and only if $v = uw$ for some nonempty word $w\in\Sigma^*$.
\end{itemize}
The union of these partial orderings is the lexicographical ordering $<_\ell = <_s \cup <_p$.
We call the language $L$ well-ordered or scattered,
if $(L,<_\ell)$ has the appropriate property and we define the rank $r(L)$ of a scattered language $L$
as $r(L,<_\ell)$. The order type $o(L)$ of a language $L$ is the order type of $(L,<_\ell)$.
For example, if $a<b$, then $o\Bigl(\{a^kb:k\geq 0\}\Bigr)=-\omega$ and $o\Bigl(\{(bb)^ka:k\geq 0\}\Bigr)=\omega$.

When $\varrho$ is a relation over words (like $<_\ell$ or $<_s$), we write $K\varrho L$ if $u\varrho v$ for each word $u\in K$ and $v\in L$.

An \emph{$\omega$-word} over $\Sigma$ is an $\omega$-sequence $a_1a_2\ldots$ of letters $a_i\in\Sigma$. The set of all $\omega$-words over $\Sigma$ is denoted $\Sigma^\omega$.
The orderings $<_\ell$ and $<_p$ are extended to $\omega$-words. An $\omega$-word $w$ is called \emph{regular} if $w=uv^\omega=uvvvv\ldots$ for some finite words
$u\in\Sigma^*$ and $v\in\Sigma^+$. When $w$ is a (finite or $\omega$-) word over $\Sigma$ and $L\subseteq\Sigma^*$ is a language, then $L_{<w}$
stands for the language $\{u\in L:u<w\}$. Notions like $L_{\geq w}$, $L_{<_sw}$ are also used as well, with the analogous semantics.

A \emph{context-free grammar} is a tuple $G=(N,\Sigma,P,S)$, where $N$ is the alphabet of the \emph{nonterminal symbols}, $\Sigma$ is the alphabet of \emph{terminal symbols} (or \emph{letters}) which is disjoint from $N$, $S\in N$ is the \emph{start symbol} and $P$ is a finite set of \emph{productions} of the form $A\to\alpha$, where $A\in N$ and $\alpha$ is a \emph{sentential form}, that is, $\alpha = X_1X_2\ldots X_k$ for some $k\geq 0$ and $X_1,\ldots,X_k\in N\cup \Sigma$. The derivation relations $\Rightarrow$, $\Rightarrow_\ell$, $\Rightarrow^*$ and $\Rightarrow_\ell^*$ are defined as usual
(where the subscript $\ell$ stands for ``leftmost'').
The \emph{language generated by} a grammar $G$ is defined as $L(G) = \{u\in\Sigma^* ~|~ S\Rightarrow^*u\}$.
Languages generated by some context-free grammar are called \emph{context-free languages}.
For any set $\Delta$ of sentential forms, the language generated by $\Delta$ is $L(\Delta) = \{u \in \Sigma^* ~|~ \alpha\Rightarrow^* u\hbox{ for some } \alpha\in\Delta\}$.
As a shorthand, we define $o(\Delta)$ as $o(L(\Delta))$.
When $X,Y\in N\cup\Sigma$ are symbols of a grammar $G$, we write $Y\preceq X$ if $X\Rightarrow^*uYv$ for some words $u$ and $v$; $X\approx Y$ if $X\preceq Y$ and $Y\preceq X$ both hold;
and $Y\prec X$ if $Y\preceq X$ but not $X\preceq Y$. A production of the form $X\to X_1\ldots X_n$ with $X_i\prec X$
for each $i\in[n]$ is called an \emph{escaping production}.

A \emph{regular language} over $\Sigma$ is one which can be built up from the singleton languages $\{a\}$, $a\in\Sigma$
and the empty language $\emptyset$ with finitely many applications of taking (finite) union,
concatenation $KL=\{uv:u\in K,v\in L\}$ and iteration $K^*=\{u_1\ldots u_n:n\geq 0,u_i\in K\}$.
For standard notions on regular and context-free languages the reader is referred to any standard textbook, such as~\cite{Hopcroft+Ullman/79/Introduction}.

Linear orderings which are isomorphic to the lexicographic ordering of some context-free (regular, resp.) language
are called \emph{context-free (regular, resp.) orderings}.
\section{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{lem-limx-finite}),
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{thm-finite-limits-imply-computability}).

Firstly, we recall (and prove for the sake of completeness) that $\Sigma^\infty$ forms a complete lattice
with the partial ordering $\leq_\ell$ (which can be turned into a metric space as well).
\begin{lemma}
	\label{lem-lattice}
	$(\Sigma^\infty, \leq_\ell)$ is a complete lattice.
\end{lemma}
\begin{proof}
	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\ldots\in\Sigma^\omega$ in the following way: let $u_0 = \varepsilon$ and $u_i = a_1\ldots a_i$.
	We choose the largest possible letter $a_{i+1}$ with $(u_ia_{i+1})^{-1}L$ being nonempty.
	The word generated by this way is the supremum of $L$.
\end{proof}

\subsection{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.
\begin{definition}
	The word $w\in\Sigma^\omega$ is a \emph{limit} of an infinite language $L$, if for each $w_0<_p w$ there exists a word $u\in L$ such that $w_0<_p u$.
\end{definition}

If $L \subseteq \Sigma^*$ is a language, then we denote the limits of $L$ with $\blim{L}$.

\begin{lemma}
	If $w$ is a limit of an infinite language $L$, then for each $w_0<_p w$ there exist infinitely many words $u\in L$ with $w_0<_p u$.
\end{lemma}
\begin{proof}
	We construct two sequences $w_0 <_p w_1 <_p \ldots <_p w$ and $u_0,\ u_1, \ldots \in 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\in L$ such that $w_i<_p u_i$ and $w_i\in \mathbf{Pref}(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$.
\end{proof}

\begin{lemma}
\label{lem-infinite}
	For each infinite language $L$, the set $\blim{L}$ is nonempty.
\end{lemma}
\begin{proof}
	We construct a limit word $w=a_1a_2\ldots\in\Sigma^\omega$. Let $u_0 = \varepsilon$ and $u_i = a_1\ldots a_i$ and we choose $a_{i+1}\in\Sigma$ 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$.
\end{proof}

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.
\begin{lemma}
	\label{lem-sup-is-limit}
	If $w_0, w_1, \ldots$ is a $<_\ell$ (or $>_\ell$ respectively) chain in $L$, then its supremum (infimum, resp.) is a limit of $L$.
\end{lemma}
\begin{proof}
	Let $w$ be the supremum of the $<_\ell$ 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<_\ell w$ for each of them, moreover, there exists some word $w_i$ with $w'<_\ell w_i<_\ell w$.
	Since we know that $w'<_pw$, it has to be the case that $w'<_pw_i<_\ell w$ and the claim is proved.

	For the other case, let $w$ be the infimum of the $>_\ell$ 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 $\Sigma$,
	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''\leq_\ell w_i$ for each $i$. Since $w$ is the infimum of
	these words $w_i$, we should have $w''\leq_\ell w$ but this contradicts to $w'<_pw$ and $w'<_sw''$ as these two imply $w<_sw''$.
\end{proof}

Now we recall from~\cite{GelleIvanGandalf} that for any context-free language, we can compute a supremum or infimum
of the language.

\begin{lemma}[\cite{GelleIvanGandalf}, Lemma 1]
	\label{lem-sequence}
	For each sentential form $\alpha$ with $L(\alpha)$ being infinite, we can generate a sequence $w_0,w_1,\ldots \in L(\alpha)$ and a regular word $w\in\Sigma^\omega$ satisfying one of the following cases:
	\begin{itemize}
		\item[i)] $w_1<_sw_2<_s\ldots$ and $w=\mathop\bigvee\limits_{i\geq 0}w_i$
		\item[ii)] $w_1>_sw_2>_s\ldots$ and $w=\mathop\bigwedge\limits_{i\geq 0}w_i$
		\item[iii)] $w_1<_pw_2<_p\ldots$ and $w=\mathop\bigvee\limits_{i\geq 0}w_i$
	\end{itemize}
\end{lemma}
Hence, Lemma~\ref{lem-sup-is-limit} in conjunction with Lemma~\ref{lem-sequence}
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:

\begin{lemma}
	\label{lem-union}
	For any languages $K$ and $L$ $\blim{K\cup L} = \blim{K}\cup\blim{L}$.
\end{lemma}
\begin{proof}
	Assume $w$ is a limit of $L$. Then for each $w_0<_pw$, there exists some $u\in L$ with $w_0<_p u$.
	Since then $u\in K\cup L$ as well, $w$ is a limit of $K\cup L$ as well.

	For the other direction, assume $w$ is a limit of $K\cup L$. Then for each $w_0<_pw$, there exists
	some $u\in K\cup L$ with $w_0<_pu$. Thus, either there exists infinitely many prefixes $w_0$ of $w$
	for which there exists some $u\in K$ with $w_0<_pu$ or there exists infinitely many prefixes $w_0$ of
	$w$ for which there exists some $u\in L$ with $w_0<_pu$. In the former case, $w$ is a limit of $K$,
	in the latter, $w$ is a limit of $L$.
\end{proof}

\begin{lemma}
	\label{lem-limits-of-product}
	$\blim {KL} = \blim{K} \cup K\blim{L}$ if $K, L\neq \emptyset$.
\end{lemma}
\begin{proof}
	 Let $u\in 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^*\in KL$ with $w' <_p w^*$. Let $w'\in \mathbf{Pref}(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\in L$ such that $w_0<_p v$. Thus there is a word $uv\in 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\in K$ with $w_0 <_p v$ by definition. So $vu \in 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\in KL$ such that $w_i <_p u_iv_i$ where $u_i\in K$ and $v_i\in 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 $\ell = \max|u_i|$ be the maximal length.
	Since there are only finitely many words of length at most $\ell$, 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'\in\Sigma^\omega$.
	We show that $w'\in\blim L$, yielding $w\in K\blim 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$.
\end{proof}

\begin{corollary}
	\label{cor-la-al}
	For any language $L$ and letter $a\in\Sigma$,
	$\blim{L}=\blim{La}$ and $a\cdot\blim{L}=\blim{aL}$.
\end{corollary}

\begin{corollary}
	\label{cor-uLv}
	For any language $L\subseteq\Sigma^*$ and words $u,v\in\Sigma^*$, $\blim{uLv}=u\cdot \blim{L}$.
\end{corollary}

\subsection{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{lem-sequence}.)

In the rest of the paper when grammars are involved, we assume the grammar $G=(N,\Sigma,P,S)$
contains no left recursive nonterminals,
and for each $X\in 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.~\cite{GelleIvanTCS}.

It is also known~\cite{10.1007/978-3-642-22321-1_19} 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\Rightarrow^+uX\alpha$ for some $u\in\Sigma^*$ and sentential form
$\alpha$, then $u\in u_X^+$. Moreover, for each pair $X\approx Y$ of recursive nonterminals there exists
a (computable) word $u_{X,Y}\in\Sigma^*$ such that whenever $X\Rightarrow^+ uYv$, then $u\in u_{X,Y}u_Y^*$.

\begin{lemma}
	\label{lem-finite-strict-unique-limit}
	The word $w\in\Sigma^\omega$ 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\in L$ such that $u<_s w_0$ or $w_0<_s u$.
\end{lemma}
\begin{proof}
	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\in 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\in 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\in L$. Then there exists a letter $b\in\Sigma$ such that $b>a$ and infinitely many words $u\in L$ such that $w_0'b <_p u$. But any limit of these words is in $w_0'b\Sigma^\omega$
	(and by Lemma~\ref{lem-infinite} at least one limit exists), which cannot be equal to $w$, so the language $L$ has two different limits which is a contradiction.
\end{proof}

\begin{lemma}
	\label{lem-unique-limit-embeds-into-omega-plus-minusomega}
	If $L$ has a unique limit $w$, then $o(L_{<w}) \preceq \omega$ and $o(L_{>w}) \preceq -\omega$.
	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})$).
\end{lemma}
\begin{proof}
	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{lem-sup-is-limit} the supremum
	$\bigvee L_{<w}$ of this language is $w$ as well, moreover,
	each infinite $K\subseteq L_{<w}$ has $\bigvee K = w$, so the order type of $L_{<w}$ has to be $\omega$.

	In the $o(L_{>w})$ case, if $L_{>w}$ is finite, it can be embedded into $-\omega$ 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\subseteq L_{>w}$ has $\bigwedge K = w$, so the order type of $L_{>w}$ has to be $-\omega$.
\end{proof}

Before proceeding to the case of concatenation, we recall the notion of prefix chains from~\cite{GelleIvanGandalf}.
For a word $w\in\Sigma^\omega$, let $\mathbf{Pref}(w)$ stand for the set $\{u\in\Sigma^*:u<_pw\}$ of
proper prefixes of $w$. A language $L\subseteq\Sigma^*$ is called a \emph{prefix chain} if $L\subseteq\mathbf{Pref}(w)$
for some $\omega$-word $\omega$. Lemma 2 from~\cite{GelleIvanGandalf} states that it is decidable for
any context-free language $L$ whether $L$ is a prefix chain and if so, a suitable $w\in\Sigma^\omega$
can be effectively computed.

\begin{lemma}
	\label{lem-x1x2}
	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.
\end{lemma}
\begin{proof}
	By assumption, the nonterminals $X_1$ and $X_2$ each generate an infinite language so they have at
	least one limit by Lemma~\ref{lem-infinite}.
	By Lemma~\ref{lem-limits-of-product}, 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{lem-sequence}. Let $u_1v_1^\omega$ and $u_2v_2^\omega$
	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\in L_1$, then both $xu_2v_2^\omega$
	and $yu_2v_2^\omega$ are limits of $L$ by Lemma~\ref{lem-limits-of-product}
	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\subseteq\mathbf{Pref}(u_1v_1^\omega)$.
	By Lemma~\ref{lem-limits-of-product}, $u_1v_1^\omega$ is also a limit of $L$,
	and for each $u\in L_1$, the word $uu_2v_2^\omega$ is also a limit of $L$.
	Thus, we have to decide whether $u_1v_1^\omega=uu_2v_2^\omega$ holds for each $u\in L_1$.

	Now consider the direct product automaton $M=M_{u_1,v_1}\times 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^\omega\neq uu_2v_2^\omega$ if and only if from the state $(q_0\cdot u,q'_0)$
	some state of the form $(\bot,q')$ or $(q,\bot')$ is reachable for some $q\neq\bot$.
	Thus, it suffices to determine the set of states $q$ in $M_1$ for which $q_0\cdot u=q$ for some $u\in L_1$,
	that is, for which $M_1(q)\cap 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
	$(\bot,p')$ or $(p,\bot')$ is reachable from $(q,q'_0)$ and if so, then $uu_2v_2^\omega\neq u_1v_1^\omega$
	for some $u\in L_1$ and thus $L$ has at least two different limits.

	Now assume $uu_2v_2^\omega=u_1v_1^\omega$ for each $u\in L_1$. We claim that in this case $L$ has the unique
	limit $u_1v_1^\omega$. To see this, we first prove that for each prefix $w_0<_pu_1v_1^\omega$,
	there are only a finite number of words $v\in 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^\omega$ there are
	infinitely many such words and let $w_0$ be the shortest such prefix.
	By assumption, there are infinitely many words $xy\in L$, $x\in L_1$, $y\in L_2$,
	with either $xy<_sw_0$ or $w_0<_sxy$. Since $L_1\subseteq\mathbf{Pref}(u_1v_1^\omega)$ and $w_0<_pu_1v_1^\omega$,
	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\in 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\in L_2$.
	But since we know that $uu_2v_2^\omega=u_1v_1^\omega$, $v$ is a prefix of $u_2v_2^\omega$,
	which is the unique limit of $L_2$ and thus only finitely many words $y\in L_2$ exist with
	$y<_sv$ or $v<_sy$ by Lemma~\ref{lem-finite-strict-unique-limit}, yielding a contradiction.

	Hence in this case, $u_1v_1^\omega$ is the unique limit of $L$.
\end{proof}

\begin{corollary}
	\label{cor-unique-alpha-limit}
	Assume $n\geq 0$ and $X_1,\ldots,X_n\in N\cup\Sigma$ 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\ldots X_n)$ has a unique limit.
\end{corollary}
\begin{proof}
	Let us introduce the fresh nonterminals $Y_1,\ldots,Y_{n-1}$ and productions
	$Y_1\to X_1Y_2$, $Y_2\to X_2Y_3$,\ldots, $Y_{n-1}\to X_{n-1}X_n$. Applying Lemma~\ref{lem-x1x2}
	or Corollary~\ref{cor-la-al} (depending on whether $X_i$ is a nonterminal or a letter)
	for the nonterminals $Y_{n-1}$, $Y_{n-2}$, \ldots, $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\ldots X_n)=L(Y_1)$.
\end{proof}

\begin{corollary}
	\label{cor-alpha}
	Let $X$ be a nonterminal $X\to\alpha_1~|~\ldots~|~\alpha_k$ be the collection of all the escaping productions
	with left-hand side $X$. Assume we already know for each $Y\prec X$ whether $L(Y)$ has a unique limit.
	Then it is computable whether $L(\{\alpha_1,\ldots,\alpha_k\})$ has a unique limit.
\end{corollary}
\begin{proof}
	By Corollary~\ref{cor-unique-alpha-limit}, it is computable for each $\alpha_i$ whether each $L(\alpha_i)$
	is finite or has a unique limit.
	If not, then neither has their union (by Lemma~\ref{lem-union}).
	If each of the languages $L(\alpha_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{lem-sequence}, and the equivalence of these words is decidable.
\end{proof}

\begin{lemma}
	\label{lem-recursive-nonprefix-alpha-x-beta}
	Assume $X$ is a recursive nonterminal, $L(X)$ is not a prefix chain
	and for some nonterminal $X'\approx X$ there exists a
	production $X'\to \alpha X''\beta$ with $\beta$ containing at least one nonterminal.

	Then $L(X)$ has at least two limits.
\end{lemma}
\begin{proof}
	Let $u<_sv$ be members of $L(X)$. Since $\beta$ contains a nonterminal, $L(\beta)$ is
	infinite and has a limit $w$ by Lemma~\ref{lem-infinite}. By the conditions on the
	recursive nonterminal $X$, we get $X\Rightarrow^*u_1Xu_2\beta u_3$ for some words $u_1,u_2,u_3\in\Sigma^*$.
	By Lemma~\ref{cor-uLv}, both $u_1uu_2w$ and $u_1vu_2w$ are limits of $L(X)$ and they are
	distinct by $u<_sv$.
\end{proof}

\begin{lemma}
	\label{lem-recursive-x}
	Assume $L(G)$ is scattered.
	Then it is decidable for each nonterminal $X$ whether $L(X)$ has a unique limit.
\end{lemma}
\begin{proof}
	We prove the statement by induction on $\prec$. So let $X$ be a nonterminal and
	assume we already know for each $Y\prec X$ whether $L(Y)$ has a unique limit.

	If $X$ is nonrecursive, and $X\to\alpha_1~|~\ldots~|~\alpha_k$ are all the alternatives of $X$,
	then the question is decidable by Corollary~\ref{cor-alpha}.

	So let $X$ be a recursive nonterminal. If $L(Y)$ has at least two limits for some $Y\prec X$,
	then by Corollary~\ref{cor-uLv} so does $L(X)$ and we are done. So we can assume from now on
	that each $L(Y)$ with $Y\prec 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'\to \alpha X''\beta$ with $X'\approx X''\approx X$
	and $\beta$ containing at least one nonterminal, then by Lemma~\ref{lem-recursive-nonprefix-alpha-x-beta},
	$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'\to \alpha X''u$ for some $u\in\Sigma^*$, $X'\approx X''\approx X$. Since $L(X)$ is scattered,
	for each such $\alpha$ it has to be the case that $L(\alpha)\subseteq u_{X',X''}^{}u_{X''}^*$.

	Now let $X'\approx X$ be a nonterminal and $\alpha_1,\ldots,\alpha_k$ all the escaping alternatives
	of $X'$. If $L(\{\alpha_1,\ldots,\alpha_k\})$ has at least two limits, then so does $L(X')$ and $L(X)$
	and we are done. Otherwise, if $L(\{\alpha_1,\ldots,\alpha_k\})$ is infinite, then its unique limit
	is a computable word. On the other hand, for each recursive nonterminal $X'$ the word $u_{X'}^\omega$
	is a limit of $L(X')$, and by $L(\{\alpha_1,\ldots,\alpha_k\})\subseteq 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'\approx X$, the language $L(X')$ has the limit $u_{X'}^\omega$
	which is the same as the unique limit of $L(\{\alpha_1,\ldots,\alpha_k\})$ if this latter language is infinite.

	We claim that in this case, $L(X)$ has the unique limit $u_X^\omega$. To see this, we apply
	Lemma~\ref{lem-finite-strict-unique-limit} and show that for each prefix $w_0$ of $u_X^\omega$,
	there are only finitely many words $u\in L(X)$ with either $w_0<_su$ or $u<_sw_0$.

	Assume to the contrary that $w_0<_pu_X^\omega$ and there are infinitely many words $u\in L(X)$ with
	either $w_0<_su$ or $u<_sw_0$. Each word $u\in L(X)$ can be derived from $X$ using a leftmost
	derivation sequence resulting in a sentential form $u_X^tu_{X,X'}\alpha v$ for some $t\geq 0$
	so that $X'\to\alpha$ is an
	escaping production from the component of $X$ and $u\in u_X^tu_{X,X'}L(\alpha)v$.
	Since $u$ and $w_0<_pu_X^\omega$ 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\geq 0$, $X'$, $\alpha$ 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(\alpha)v$. So we can write each such $u$ as $u=u_X^tu_{X,X'}u'v$
	with $u'\in L(\alpha)$, and we can write $w_0$ as $w_0=u_X^tu_{X,X'}w'_0$, that is, $w'_0<_p u_{X'}^\omega$.
	This yields that $u'v<_sw'_0$ or $w'_0<_su'v$ for infinitely many words $u'\in L(\alpha)$.
	Thus, there are infinitely words $u'\in L(\alpha)$ 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{lem-finite-strict-unique-limit} this would yield that $L(\alpha)$ has at least two
	limits, which we already handled in a former case.
\end{proof}

\subsection{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.

\begin{lemma}
	\label{lem-uvomega-islimit-decidable}
	It is decidable for any context-free language $L$ and regular word $w=uv^\omega$
	whether $w$ is a limit of $L$.
\end{lemma}
\begin{proof}
	Let $L\subseteq\Sigma^*$ be a context-free language and
	consider the generalized sequential mapping $f:\Sigma^*\to a^*$ defined as
	\[f(x)=\begin{cases}a\cdot f(y)&\hbox{if }x=vy\hbox{ for some }y\in\Sigma^*\\\varepsilon&\hbox{otherwise}.\end{cases}\]
	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^\omega$ is a limit of a language $L'$ if and only if $f(L')$ is infinite;
	hence, by Corollary~\ref{cor-uLv}, $w=uv^\omega$ is a limit of $L$ if and only if $f(u^{-1}L)$ 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.
\end{proof}

\begin{lemma}
	\label{lem-recursive-one-or-infinite}
	If $X$ is a recursive nonterminal, then $u_X^\omega \in \blim{X}$ and if some $w\neq u_X^\omega$ is also a member of $\blim{X}$, then $\blim{X}$ is infinite.
\end{lemma}
\begin{proof}
	Since $X\Rightarrow^* u_X^nX\alpha$ holds for each recursive nonterminals, there exists a word $v\in L(X)$ for each $u\in\mathbf{Pref}(u_X^\omega)$ such that $u<_p v$.

	If $w\neq u_X^\omega$ is also a limit of $L(X)$, then it can be written as $w=ubw'$, where $u<_pu_X^\omega$, $ub\not<_pu_X^\omega$ and $w'\in\Sigma^\omega$. So if we consider a derivation of the form
	$X\Rightarrow^* u_X^nX\alpha$, we get that each $(u_x^n)^kubw'$, $k>0$ is a limit, thus $\blim{X}$ is infinite
	as these words are pairwise different.
\end{proof}

\begin{lemma}
	\label{lem-kvomega-is-finite}
	Assume $K$ is a context-free language and $v$ is a nonempty word. Then it is decidable whether $Kv^\omega$ is finite
	and if so, its members (which are regular words) can be effectively enumerated.
\end{lemma}
\begin{proof}
Consider the generalized sequential mapping $f: \Sigma^*\to \Sigma^*$ defined as
$$f(x) = \begin{cases}
f(y)&\hbox{if } x=v^Ry \hbox{ for some } y\in\Sigma^*\\
x&\hbox{otherwise.}
\end{cases}$$

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\geq 0$,
that is, $f$ strips away the leading $v^R$s of its input.
So, we have that $\bigl(f(K^R)\bigr)^R$ consists of those words we get from members of $K$, stripping
away their trailing $v$s.
Now $u\in \bigl(f(K^R)\bigr)^R$ if and only if $u$ does not end with $v$ and $uv^\omega\in Kv^\omega$.
Moreover, $Kv^\omega$ is finite if and only if there exist some $u_1, u_2, \ldots, u_n\in \Sigma^*$ such that for each $i\in[n]$ the word $u_i$ does not end with $v$ and  $Kv^\omega = \{u_iv^\omega ~|~ i\in [n]\}$.
So we get that $Kv^\omega$ is finite if and only if so is $\bigl(f(K^R)\bigr)^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 $\bigl(f(K^R)\bigr)^R=\{u_1,\ldots,u_n\}$ can also be effectively enumerated and
$Kv^\omega=\{u_jv^\omega:j\in[n]\}$.
\end{proof}

\begin{lemma}
	\label{lem-kl-finite}
	Assume $K$ and $L$ are context-free languages such that $\blim{K} = \{u_iv_i^\omega ~|~ 1\leq i\leq k\}$ and $\blim{L} = \{u'_jw_j^\omega ~|~ 1\leq j\leq \ell \}$ are finite sets of regular words. Then it is decidable whether $\blim{KL}$ is finite and if so, then it is a computable (finite) set of regular words.
\end{lemma}
\begin{proof}
	By Lemma~\ref{lem-limits-of-product} $\blim{KL}=\blim{K}\cup K\blim{L}$. Since $\blim{K}$ is a finite set
	(and is of course computable since it is given as input),
	we only have to deal with $K\cdot\blim{L}$.
	Since \[K\cdot\blim{L}=K\cdot\bigl\{u_j'w_j^\omega:j\in[\ell]\bigr\}=\mathop\bigcup\limits_{j\in[\ell]}(Ku_j')w_j^\omega\]
	and this union is finite if and only if so is each language $(Ku'_j)w_j^\omega$, which is decidable by
	Lemma~\ref{lem-kvomega-is-finite} (since the languages $Ku'_j$ are each context-free), we get decidability
	and even computability if each of them is finite.
\end{proof}

\begin{corollary}
	\label{cor-finite-alpha-limit}
	Assume $n\geq 0$ and $X_1,\ldots,X_n\in N\cup\Sigma$ are symbols so that for each $X_i$,
	$\blim{X_i}$ is a known finite set.
	Then it is decidable whether $L(X_1\ldots X_n)$ has a finite number of limits and if so,
	$\blim{X_1\ldots X_n}$ is effectively computable.
\end{corollary}
\begin{proof}
	Let us introduce the fresh nonterminals $Y_1,\ldots,Y_{n-1}$ and productions
	$Y_1\to X_1Y_2$, $Y_2\to X_2Y_3$,\ldots, $Y_{n-1}\to X_{n-1}X_n$. Applying Lemma~\ref{lem-kl-finite}
	or Corollary~\ref{cor-la-al} (depending on whether $X_i$ is a nonterminal or a letter)
	for the nonterminals $Y_{n-1}$, $Y_{n-2}$, \ldots, $Y_1$ in this order we can decide whether
	each $L(Y_i)$ has a finite number of limits, and if so, we compute $\blim{Y_i}$ as well,
	proving the statement since $L(X_1\ldots X_n)=L(Y_1)$.
\end{proof}

\begin{corollary}
	\label{lem-limx-finite}
	It is decidable for any nonterminal $X$ whether $L(X)$ has a finite number of limits.
\end{corollary}
\begin{proof}
	There are two cases: either $X$ is recursive or not. If $X$ is recursive, then by Lemma~\ref{lem-recursive-one-or-infinite}
	$L(X)$ has a finite number of limits if and only it has a unique limit which is decidable due to Lemma~\ref{lem-recursive-x}.
	Hence we can decide for each nonterminal $X\neq S$ whether $\blim{ L(X) }$ is finite.

	Now suppose $X$ is not recursive (thus $X=S$ as $G$ is in normal form)
	and let ${\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_t$ be all the alternatives of $S$.
	By Corollary~\ref{cor-finite-alpha-limit} for each $\alpha_i$ $(1\leq i\leq t)$ it is decidable whether $L(\alpha_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(\alpha_i)$ has a finite number of limits and we can
	even compute each $\blim{\alpha_i}$.
	By Lemma~\ref{lem-union}, $\blim{X} = \bigcup_{i\in [t]}\blim{\alpha_i}$.
\end{proof}

\begin{theorem}
	\label{thm-finite-limits-imply-computability}
	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.
\end{theorem}
\begin{proof}
	We prove the statement by induction on the number of limits.

	If $L$ has no limits, then it is finite by Lemma~\ref{lem-infinite}, and so $o(L)=|L|$ is computable.

	If $L$ has a unique limit, then $o(L)$ can be embedded into $\omega+-\omega$ and is computable
	by Lemma~\ref{lem-unique-limit-embeds-into-omega-plus-minusomega}. Moreover, it is decidable
	whether $L$ has a unique limit by Lemma~\ref{lem-recursive-x}.

	Now assume $L$ has at least two limits. Since $L$ is infinite, we can compute a regular limit
	of the form $w=uv^\omega$ for $L$ by Lemma~\ref{lem-sequence}.
	By Lemma~\ref{lem-uvomega-islimit-decidable}, it is decidable whether $w$ is a limit
	of either $L_{<w}$ or $L_{>w}$ or both of them. (By Lemma~\ref{lem-union}, $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=\bigvee 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=\bigvee 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\geq 0$ such that $w'<_suv^n$,
	or equivalently, $L_{<uv^n}$ is infinite for some $n\geq 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}}_{\geq 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 $\omega$, $-\omega$ and $1$, that is, has to have rank at most $1$.
\end{proof}

\begin{corollary}
	\label{cor-hausdorff-one-computable}
	Suppose $L$ is a scattered context-free language of rank at most one.
	Then $o(L)$ is effectively computable.
\end{corollary}
\begin{proof}
	If $o(L)\in\{\omega,-\omega\}$, 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
	$\omega$, $-\omega$ and $1$, thus scattered languages of rank at most one are finite unions of
	languages of order type $\omega$, $-\omega$ or $1$, by Lemma~\ref{lem-union} we get that
	such languages have a finite number of limits, and thus their order type is effectively computable
	by Theorem~\ref{thm-finite-limits-imply-computability}.
\end{proof}

\begin{corollary}
	\label{cor-main}
	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$, $\omega$ and $-\omega$).
\end{corollary}

\section{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$, $\omega$
and $-\omega$. This complements our earlier result~\cite{GelleIvanGandalf} that for scattered
context-free orderings of rank (at least) two, it is undecidable whether their order type
is $\omega+(\omega+\zeta)\times\omega$, 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).