Structures without Scattered-Automatic Presentation
Alexander Kartzow\inst{1}
Universit\"at Leipzig
Germany
Mathematisches Institut
Universit\"at Bonn
Bruy\`ere and Carton lifted the notion of finite automata reading infinite words to finite automata reading words with shape an arbitrary linear order $\mathfrak{L}$. Automata on finite words can be used to represent infinite structures, the so-called word-automatic structures. Analogously, for a linear order $\mathfrak{L}$ there is the class of $\mathfrak{L}$-automatic structures. In this paper we prove the following limitations on the class of $\mathfrak{L}$-automatic structures for a fixed $\mathfrak{L}$ of finite condensation rank $1+\alpha$. Firstly, no scattered linear order with finite condensation rank above $\omega^{\alpha+1}$ is $\mathfrak{L}$-automatic. In particular, every $\mathfrak{L}$-automatic ordinal is below $\omega^{\omega^{\alpha+1}}$. Secondly, we provide bounds on the (ordinal) height of well-founded order trees that are $\mathfrak{L}$-automatic. If $\alpha$ is finite or $\mathfrak{L}$ is an ordinal, the height of such a tree is bounded by $\omega^{\alpha+1}$. Finally, we separate the class of tree-automatic structures from that of $\mathfrak{L}$-automatic structures for any ordinal $\mathfrak{L}$: the countable atomless boolean algebra is known to be tree-automatic, but we show that it is not $\mathfrak{L}$-automatic.
V4.2Scattered-Automatic-Structures.tex
\documentclass[envcountsame]{llncs}
%\documentclass{lmcslike}


\usepackage{amsmath}
%\usepackage[tbtags]{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{mathrsfs}
\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{url}
\usepackage{times}
\usepackage{xspace}


\usepackage{verbatim} 

\usepackage{hyperref}

\hypersetup{
colorlinks=false,
pdfauthor={Alexander Kartzow and Philipp Schlicht},
pdftitle={Structures without Scattered-Automatic Presentation},
pdfkeywords={}
}

%\usepackage[textsize=footnotesize,color=blue!40]{todonotes}
%\newcommand\fixme[1]{\todo[size=\scriptsize,color=red!40]{#1\\}\xspace}



\newcommand{\domain}[0]{\mathsf{dom}}
\newcommand{\supp}[0]{\mathsf{supp}}
\newcommand{\Cuts}[0]{\mathsf{Cuts}}
\newcommand{\Sc}[0]{\mathcal{S}}
\newcommand{\Ac}[0]{\mathcal{A}}
\newcommand{\Bc}[0]{\mathcal{B}}
\newcommand{\Cc}[0]{\mathcal{C}}
\newcommand{\Dc}[0]{\mathcal{D}}
\newcommand{\Fc}[0]{\mathcal{F}}
\newcommand{\Gc}[0]{\mathcal{G}}
\newcommand{\Af}{\mathfrak{A}}
\newcommand{\Bf}{\mathfrak{B}}
\newcommand{\Cf}{\mathfrak{C}}
\newcommand{\Ef}{\mathfrak{E}}
\newcommand{\Ff}{\mathfrak{F}}
\newcommand{\Lf}{\mathfrak{L}}
\newcommand{\Kf}{\mathfrak{K}}
\newcommand{\fr}{\mathsf{fr}}
\newcommand{\Gf}{\mathfrak{G}}
\newcommand{\infrank}{\ensuremath{\infty}\text{-}\ensuremath{\mathsf{rank}}}
\newcommand{\rank}{\ensuremath{\mathsf{rank}}}
\newcommand{\Pf}{\mathfrak{P}}
\newcommand{\Pc}{\mathcal{P}}
\newcommand{\Tf}{\mathfrak{T}}
\newcommand{\Tc}{\mathcal{T}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\KB}{\mathsf{KB}}
\newcommand{\FC}{\mathsf{FC}}
\newcommand{\FCstar}{\mathsf{FC_*}}
\newcommand{\image}{\mathsf{im}}
\newcommand{\Pgood}{\ensuremath{P_{\text{good}}}}
\newcommand{\nil}{\mathsf{nil}}

\newcommand{\suffix}[1]{\ensuremath{\overset{\rightarrow}{\sqsupseteq}}_{#1}}

\newcommand{\wordsim}[2]{\sim_{{#1}}^{{#2}}}
\newcommand{\run}[2]{\overset{{#1}}{\underset{{#2}}{\longrightarrow}}}
\newcommand{\LEFT}{\ensuremath{{\bf L}}}
\newcommand{\RIGHT}{\ensuremath{{\bf R}}}

\newcommand{\shuffle}{\mathsf{sh}}

\newcommand{\Words}[1]{\ensuremath{W({#1})}}


\pagestyle{plain}
\begin{document}

\title{Structures without Scattered-Automatic Presentation}


\author{Alexander Kartzow\inst{1} \and Philipp Schlicht\inst{2}
\thanks{The first  author is supported by the DFG  research project GELO.}
\institute{
Institut f\"ur Informatik, Universit\"at Leipzig, Germany
\and
 Mathematisches Institut, Universit\"at Bonn, Germany
\\
\email{kartzow@informatik.uni-leipzig.de, schlicht@math.uni-bonn.de}}}

\maketitle




\begin{abstract}
  Bruy\`ere and Carton lifted the notion of finite automata reading infinite
  words to finite automata reading words with shape an arbitrary
  linear order $\mathfrak{L}$. Automata on finite words can be used to
  represent infinite structures, the so-called 
  word-automatic structures. Analogously, for a linear order
  $\mathfrak{L}$ there is the class of $\mathfrak{L}$-automatic
  structures. In this paper we prove the following limitations on the
  class of $\mathfrak{L}$-automatic structures for a fixed
  $\mathfrak{L}$ of finite condensation rank $1+\alpha$.

  Firstly, no scattered linear order with finite condensation rank
  above  $\omega^{\alpha+1}$ is $\mathfrak{L}$-automatic. In particular,
  every $\mathfrak{L}$-automatic ordinal is  below
  $\omega^{\omega^{\alpha+1}}$. 
  Secondly, we provide bounds on the (ordinal) height of well-founded
  order trees that are 
  $\mathfrak{L}$-automatic. If $\alpha$ is finite or $\mathfrak{L}$ is
  an ordinal, the height of such a tree is bounded by $\omega^{\alpha+1}$. 
  Finally, we separate the class of tree-automatic structures from
  that of $\mathfrak{L}$-automatic structures for any ordinal
  $\mathfrak{L}$: the countable atomless boolean algebra is known to
  be tree-automatic, but we show that it is not
  $\mathfrak{L}$-automatic. 
\end{abstract}



\section{Introduction}
\label{sec:Intro}

Finite automata  play a crucial
role in many areas of computer science. In particular, finite automata
have been used to represent certain classes of possibly infinite
structures. The basic notion of this branch of research is the class of
automatic structures (cf. \cite{KhoussainovN94}): a
structure is automatic if its domain as well 
as its relations are recognised by (synchronous multi-tape) finite
automata processing finite words. This class has the remarkable
property that the first-order theory of any automatic structure is
decidable. One goal in the theory of automatic structures is a
classification of those structures that are automatic
(cf.~\cite{Delhomme04,KhoussainovRS05,DBLP:journals/lmcs/KhoussainovNRS07,DBLP:journals/apal/KhoussainovM09,KuLiLo11}). 
Besides finite automata reading \emph{finite} or \emph{infinite words}
there are also finite automata reading finite or infinite
\emph{trees}. Using such automata as representation of 
structures leads to the notion of tree-automatic structures
\cite{BLumensath1999}. The
classification of tree-automatic structures is less advanced but some
results have been obtained in the last years 
(cf.~\cite{Delhomme04,Huschenbett13,KaLiLo12}).  
Bruy\`ere and Carton \cite{BruyereC01} adapted the notion of finite
automata such that they can process words that have the shape 
of some fixed linear order. If the linear order is countable and
scattered, the corresponding class of languages possesses the 
good closure properties of the class of languages of finite automata
for finite words (i.e., closure under intersection, union, complement, and
projection) and emptiness of a given language is decidable. Thus, these
automata are also well-suited for representing structures. 
Given a fixed 
scattered linear order $\Lf$ this leads
to the notion of $\Lf$-automatic structures. In case that $\Lf$ is an
ordinal Schlicht and Stephan \cite{SchlichtS11} as well as Finkel and
Todorcevic \cite{FinkelT12} studied  the  classes of 
$\Lf$-automatic ordinals and $\Lf$-automatic linear orders.
Here we  study  $\Lf$-automatic linear orders for any 
scattered linear order $\Lf$ and we study 
$\Lf$-automatic
well-founded order forests,i.e., forests (seen as partial orders)
without infinite branches.
\begin{enumerate}
\item If a linear order is $\Lf$-automatic and $\Lf$ has finite
  condensation rank at most $1+\alpha$, then it is a finite sum of  linear
  orders of condensation rank below $\omega^{\alpha+1}$. As already
  shown in \cite{SchlichtS11}, this bound is optimal.
\item If a well-founded  order forest is $\Lf$-automatic for 
  some ordinal $\Lf$, then its ordinal height is bounded by $\Lf\cdot
  \omega$.
  
  If a well-founded  order forest is $\Lf$-automatic for $\Lf$ 
  some linear order of condensation rank $n\in\N$, 
  then its ordinal height is bounded by $\omega^{n+1}$. 

  These two bounds are optimal.
\item A well-founded $\Lf$-automatic order forest has ordinal height
  bounded by $\omega^{\omega\cdot (\alpha+1)}$ where $\alpha$ is the
    finite condensation rank of $\Lf$. 
\end{enumerate}
In order to prove  Claims 1 and 3 we observe that
the notion of \emph{finite-type products} from \cite{SchlichtS11} and
the notion of \emph{sum-augmentations of tamely colourable box-augmentations} 
from \cite{KaLiLo12,Huschenbett13}, even though defined in completely different
terms, have a common underlying idea. We introduce a new notion of
tamely colourable sum-of-box augmentations that refines both notions
and allows to prove a variant of Delhomm\'{e}'s decomposition method
(cf.~\cite{Delhomme04}) for the case of $\Lf$-automatic structures. 
The main results then follow as corollaries using results from
\cite{Huschenbett13} and \cite{KaLiLo12}. For the other two results,
we provide an $\Lf$-automatic scattered linear ordering of all
$\Lf$-shaped words if $\Lf$ has finite condensation rank
$n\in\N$ or if $\Lf$ is an ordinal. Extending work from \cite{KuLiLo11}, 
we provide a connection between the height of a
tree and the finite condensation rank of its Kleene-Brouwer ordering
(with respect to this $\Lf$-automatic ordering) that allows to derive
the better bounds  stated in Claim 2.

As a very sketchy summary of these results, one could say that we
adapt techniques 
previously used on trees to use them on linear orders. This raises the
question whether there is a deeper connection between $\Lf$-automatic
structures and tree-automatic structures. It is known that
all $\omega^n$-automatic structures are tree-automatic
(cf. \cite{FinkelT12}). Moreover, from
\cite{SchlichtS11} and \cite{Delhomme04} it follows that
$\omega^{\omega^\omega}$ is $\omega^\omega$-automatic but not
tree-automatic. It is open so far whether every tree-automatic
structure is $\Lf$-automatic for some linear order $\Lf$. We make a
first step towards a negative answer by showing that the countable atomless
boolean algebra is not $\Lf$-automatic for any ordinal $\Lf$ (while it
is tree-automatic \cite{BGR11}).



\section{Preliminaries}
\label{sec:preliminaries}


\subsection{Scattered Linear Orders}
\label{sec:ScatteredOrders}

In this section, we recall basic notions concerning scattered linear
orders. For a detailed introduction, we refer the reader to
\cite{rosenstein82}.
A linear order $(L, \leq)$ is \emph{scattered} if there is no
embedding of the rational numbers  into $(L, \leq)$. 

Given a scattered linear order $\Lf = (L, \leq)$, an equivalence relation
$\sim$ is called a \emph{condensation} if each $\sim$ class is an
interval of 
$\Lf$. We then write $\Lf/{\sim}:=(L/{\sim}, \leq')$ for
the linear order of the 
$\sim$ classes induced by $\leq$ (i.e., for $\sim$-classes $x,y$, 
$ x\leq' y$ iff there are $k\in x, l\in y$ such that $k
 \leq l$). 
As usual, for $\Lf$ a scattered linear order and $l,l'$ elements of
$\Lf$, we 
write $[l,l']$ for the closed interval between $l$ and $l'$. 
For each ordinal $\alpha$
we define the \emph{$\alpha$-th condensation} $\sim_\alpha$ by
$x \sim_0 y$ iff $x=y$,   $x \sim_{\alpha+1} y$ if the closed interval
$[x,y]$ in $\Lf/{\sim_\alpha}$ is finite and for a limit ordinal $\beta$, 
$x \sim_\beta y$ if there is an $\alpha<\beta$ such that
$x\sim_\alpha y$. 
The \emph{finite condensation rank}
$\FC(\Lf)$ is the minimal ordinal $\alpha$ such that 
$\Lf/{\sim_\alpha}$ is a one-element order. 
We also let $\FCstar(\Lf)$ be the minimal ordinal $\alpha$ such that
$\Lf/{\sim_\alpha}$ is a finite order. There is such an ordinal $\alpha$ if and only if $\Lf$ is scattered. 
It is obvious from these definitions that 
$\FCstar(\Lf)\leq \FC(\Lf) \leq \FCstar(\Lf)+1$.

As usual, for  a linear order $\Lf=(L, \leq)$ and 
a sequence of linear orders $(\Lf_i)_{i\in\Lf}$ we denote by
$\sum_{i\in L} \Lf_i$ the 
$\Lf$-sum of the $(\Lf_i)_{i\in\Lf}$. 

We conclude this section by recalling the notion of Dedekind cuts of a
linear order.
Let $\Lf=(L, \leq)$ be a linear order. A \emph{cut} of $\Lf$ is a
pair $c=(C, D)$ where $C$ is a downward closed subset $C\subseteq L$
and $D=L\setminus C$. We write $\Cuts(\Lf)$ for the 
\emph{set of all cuts  of $\Lf$}. 
For cuts $c,d$, we say that $c$ and $d$ are the consecutive cuts around
some $l\in L$ if $c=(C, D)$ and $d=(C', D')$ such that 
$C  =\{x\in L\mid x < l\}$ and
$C' =\{x\in L\mid x \leq l\}$. 
$\Cuts(\Lf)$ can be naturally equipped with an order (also denoted by
$\leq$) via
$c=(C,D) \leq d=(C',D')$ if $C\subseteq C'$. 
We say a cut $c=(C,D)$ has no
direct predecessor (or direct successor), if it has no direct predecessor
(or direct successor, respectively) with respect  to $\leq$. 
Let us finally introduce a notation for values appearing arbitrarily
close to some cut (from below or from above, respectively). 
\begin{definition}
  Let $\Lf=(L, \leq)$ be a linear order, and $w:\Cuts(\Lf)\to A$. For
  $c=(C,D)\in\Cuts(\Lf)$, set 
%  \begin{align*}
%    &\lim_{c^{-}} w:= \{a\in A \mid \forall l\in C
%    \exists l'\in C\quad l\leq l'\text{ and }w(l')=a\} \text{ and} \\
%    &\lim_{c^{+}} w:= \{a\in A \mid \forall l\in D
%    \exists l' \in D\quad l'\leq l\text{ and } w(l')= a\}.
%  \end{align*}
  $\lim_{c^{-}} w:= \{a\in A \mid \forall l\in C
    \exists l'\in C\quad l\leq l'\text{ and }w(l')=a\}$ \text{ and}
    $\lim_{c^{+}} w:= \{a\in A \mid \forall l\in D
    \exists l' \in D\quad l'\leq l\text{ and } w(l')= a\}$.
\end{definition}





\subsection{Automata for Scattered Words and 
  Scattered-Automatic Structures} 
\label{sec:Automata}

For this section, we fix an arbitrary linear order
$\Lf=(L, \leq)$.

\begin{definition}
  Let  $\Sigma_\diamond$
  be some finite alphabet with $\diamond\in\Sigma_\diamond$. 
  An $\Lf$-word (over $\Sigma$) is a map $L\to \Sigma_\diamond$. 
  An $\Lf$-word $w$ is \emph{finite} if 
  the support $\supp(w):=\{l\in L\mid w(l)\neq\diamond\}$
  of $w$ is finite.
  $\Words{\Lf}$ denotes  the set of $\Lf$-words.
\end{definition}

The usual notion of a convolution of finite words used in automata
theory can be easily lifted to the case of $\Lf$-words.

\begin{definition}
  Let $w_1,w_2$ be $\Lf$-words over alphabets $\Sigma_1$ and
  $\Sigma_2$, respectively. 
  The \emph{convolution}
  $w_1\otimes w_2$ is
  the $\Lf$-word over  $\Sigma_1\times \Sigma_2$ given by
  $[w\otimes v](l) := (w(l),v(l))$. 
\end{definition}


We  recall Bruy\`ere and Carton's definition
of automata for $\Lf$-words \cite{BruyereC01}. Then we introduce the
notion of (finite word) $\Lf$-automatic structures generalising the
notion of ordinal-automatic structures from \cite{SchlichtS11}. 



\begin{definition}
  An \emph{$\Lf$-automaton} is a tuple
  $\Ac= (Q, \Sigma, I, F, \Delta)$ where $Q$ is a finite set of states,
  $\Sigma$ a finite alphabet, $I \subseteq Q$ the initial and $F\subseteq Q$
  the final states and $\Delta$ is a subset of
    $
    \left(Q\times \Sigma \times Q \right) \cup
    \left( 2^Q\times Q  \right) \cup   \left( Q\times 2^Q  \right)
    $
  called the transition relation. 
\end{definition}
Transitions in $Q\times \Sigma \times Q$ are called 
\emph{successor transitions},
transitions in $2^Q\times Q$ are 
called \emph{right limit transitions}, and
transitions in $Q\times 2^Q$ are 
called \emph{left limit transitions}. 


\begin{definition}
  A \emph{run} of $\Ac$ on the $\Lf$-word $w$ is a map 
  $r:\Cuts(\Lf) \to Q$ such that
  \begin{itemize}
  \item $ \left( r(c), w(l), r(d)\right)\in \Delta$ for
    all $l\in L$ and all consecutive cuts $c,d$ around $l$,
  \item $(\lim_{c^-} r, r(c))\in\Delta$
    for all cuts $c\in\Cuts(\Lf)\setminus \{(\emptyset,L)\}$ without
    direct  predecessor, 
  \item $(r(c), \lim_{c^+} r )\in\Delta$
    for all cuts $c\in\Cuts(\Lf)\setminus \{(L,\emptyset)\}$ without
    direct successor. 
  \end{itemize}
%  Here the operators $\lim_{c^-}$ and $\lim_{c^+}$ are applied to the
%  order on $\Cuts(\Lf)$ as opposed to $\Lf$.  
  The run $r$ is \emph{accepting} if 
  $r((\emptyset,L))\in I$ and
  $r((L,\emptyset))\in F$. 
  The \emph{language} of $\Ac$ consists of all $\Lf$-words $w$ such
  that there is an accepting run of $\Ac$ on $w$. 
  For some $\Lf$-word $w$ and states $q,q'$ of $\Ac$ we write
  $q \run{w}{\Ac} q'$ if there is a run $r$ of $\Ac$ on $w$ such that
  $r((\emptyset,L))=q$ and $r((L,\emptyset))=q'$. 
\end{definition}

\begin{example} \label{exa:FiniteWordsRec} 
  The following $\Lf$-automaton accepts the set of finite
  $\Lf$-words over the alphabet $\Sigma$. Let $\Ac = (Q, \Sigma, I, F,
  \Delta)$
  with $Q= \{e_l, e_r, n, p\}$, $I=\{n\}, F=\{n,p\}$, and
  \begin{align*}
    \Delta&= \{ (n, \diamond, n), (p, \diamond, n)\}\cup 
    \{ (n,\sigma, p), (p, \sigma,p)\mid
    \sigma\in\Sigma\setminus\{\diamond\} \} \\
    &\cup
    \{(\{n\}, n), (n, \{n\}), 
    (p, \{n\}), 
    (\{p\}, e_l), (e_r, \{p\}),   
    (\{n,p\}, e_l), (e_r, \{n,p\})\}.
  \end{align*}
  For each $w\in \Words{\Lf}$, 
  \mbox{  $r((C,D))=
    \begin{cases}
      p & \text{if } \max(C) \text{ exists and } \max(C)\in\supp(w)\\
      n & \text{otherwise},
    \end{cases}$}
  defines an accepting run if $w$ is a finite $\Lf$-word.
  On an $\Lf$-word $w$ with infinite support, the successor
  transitions require infinitely many occurrences of state $p$. But
  then some limit position is marked with an error state $e_l$ or
  $e_r$ (where $l$ means 'from left' and $r$ 'from right') and the run
  cannot be continued (see Appendix \ref{sec:FiniteWordsRecognisable}
  for details). 
\end{example}



Automata on words (or infinite words or trees or infinite trees) have
been applied fruitfully for representing structures. This can be
lifted to the setting of $\Lf$-words and leads to the notion of
(oracle)-$\Lf$-automatic structures.   

\begin{definition} \label{definition: L-automatic structure} 
  Fix an $\Lf$-word $o$ (called an oracle).
  A structure $\Af=(A,R_1,R_2, \dots, R_m)$ is
  \emph{$\Lf$-$o$-automatic} 
  if there are $\Lf$-automata
  $\Ac, \Ac_1, \dots, \Ac_m$ such that
  \begin{itemize}
  \item $\Ac$ represents the domain of $\Af$ in the sense that
    $A= \{w \mid w\otimes o \in L(\Ac)\}$, and
  \item for each $i\leq m$, $\Ac_i$ represents $R_i$ in the sense that
    $R_i= \{ (w_1,w_2\dots, w_{r_i})\mid 
    w_1\otimes w_2\otimes\dots\otimes w_{r_i}\otimes o \in L(\Ac_i)\}$,
    where $r_i$ is the arity of relation $R_i$. 
  \end{itemize}
  We say that an $\Lf$-$o$-automatic structure is \emph{finite word}
  $\Lf$-$o$-automatic if its domain consists only of finite $\Lf$-words.
  Let $\Fc_\Lf$ denote the class of all
  finite word $\Lf$-oracle-automatic graphs. 
\end{definition}
For the constantly $\diamond$-valued oracle $o$ ($\forall x\in\Lf\
o(x)=\diamond$),
we call an $\Lf$-$o$-automatic structure  $\Lf$-automatic. 
We call some structure $\Af$  scattered-automatic
(scattered-oracle-automatic, respectively) if there is some 
scattered linear order $\Lf'$ (and some oracle $o$) such that $\Af$ is
finite word $\Lf'$-automatic ($\Lf'$-$o$-automatic, respectively). 


Rispal and Carton \cite{RispalC05} showed that $\Lf$-oracle-automata
are closed under complementation if $\Lf$ is countable and
scattered which implies the following Proposition.
%\fixme{Could be removed?}
\begin{proposition}
  If $\Lf$ is a countable scattered linear order, 
  the set of finite word $\Lf$-$o$-automatic structures is closed under
  first-order definable relations. 
\end{proposition}



\subsection{Order Forests}

\begin{definition}
  An (order) \emph{forest} is a partial order $\Af=(A, \leq)$ such that
  for each $a\in A$, the set $\{a'\in A\mid a\leq a'\}$ is a finite
  linear order. 
\end{definition}

Later we study the rank (also called ordinal height) of
$\Lf$-automatic well-founded
forests. For this purpose we recall the definition of rank.
Let $\Af=(A, \leq)$ be a well-founded partial order.
Setting
$\sup(\emptyset) = 0$ we define the \emph{rank} of $\Af$ by
$\rank(a, \Af)=\sup\{\rank(a',\Af)+1\mid a'<a \in A\}$ and
$\rank(\Af)=\sup\{\rank(a,\Af)+1 \mid a\in A\}$.





\section{Sum- and Box-Augmentation Technique} 
\label{sec:BoxDecomposition}


Delhomm\'{e} \cite{Delhomme04} characterised the set of ordinals that
can be represented by finite tree-automata. His results relies on a
decomposition of definable substructures into \emph{sum-} and
\emph{box-augmentations}. Huschenbett \cite{Huschenbett13} and  
Kartzow et al.~\cite{KaLiLo12} introduced a refined
notion of \emph{tamely colourable} 
box-augmentations in order to bound the ranks of tree-automatic
linear orders and well-founded order trees, respectively. We first
recall the definitions and then show that the decomposition technique
also applies to finite word scattered-oracle-automatic structures.

Before we go into details, let us sketch the ideas
underlying the sum- and box-augmentation technique. 
Given an $\Lf$-$o$-automatic structure $\Af$ with domain $A$ and
some automaton $\Ac$ (called \emph{parameter automaton}) that
recognises a subset of $A\times \Words{\Lf}$, let us denote by
$\Af_p$ the substructure of $\Af$ induced by $\Ac$ and $p$, i.e., with
domain $\{a\in A\mid a\otimes p\in L(\Ac)\}$. The main proposition of
this section says that there is a certain class $\Cc$ of structures
(independent of $p$) 
such that each $\Af_p$ is a tamely colourable sum-of-box augmentation
of structures 
from $\Cc$. $\Cc$ consists of finitely many $\Lf$-oracle-automatic
structures and scattered-oracle-automatic structures where the
underlying scattered linear order has finite condensation rank
strictly below that of $\Lf$. 
This allows to compute bounds on structural parameters (like finite
condensation rank of linear orders or ordinal height of well-founded
partial orders) by induction on the rank of $\Lf$. We say a structural
parameter $\varphi$ is compatible with sum-of-box augmentations if for
$\Af$ a sum-of-box augmentation of $\Af_1,
\dots, \Af_n$, there is a bound on $\varphi(\Af)$ in terms of
$\varphi(\Af_1), \dots, \varphi(\Af_n)$. 
The decomposition result tells us that some $\Lf$-automatic
structure $\Af$ is (mainly) a sum of boxes  of scattered-automatic
structures where the underlying orders have lower ranks. Thus, by
induction hypothesis $\varphi$ is bounded on these building blocks of
$\Af$. Thus, $\varphi(\Af)$ is also bounded if $\varphi$ is compatible
with sum- and box-augmentations. 


\subsection{Sums and Boxes}
\label{sec:sumBox}

The next definition recalls the notion of sum- and
box-augmentations. We restrict the presentation to structures with
one binary relation (but the general case is analogous).

\begin{definition}
  \begin{itemize}
  \item A structure $\Af$ is a \emph{sum-augmentation} of structures
    $\Af_1, \dots, 
    \Af_n$ if the domain of $\Af$ can be partitioned into $n$ pairwise
    disjoint sets such
    that the substructure induced by the $i$-th set is isomorphic to
    $\Af_i$. 
  \item 
    A structure $\Af=(A, \leq^A)$ is a \emph{box-augmentation} of structures
    $\Bf_1=(B_1, \leq^{B_1}),$  $\dots$,\mbox{$\Bf_n=(B_n, \leq^{B_n})$} if
    there is  a bijection 
    $\eta: \prod_{i=1}^n B_i \to A$ such that 
    for all $1\leq j \leq n$ and all $\bar b= (b_1, \dots, b_n)\in
    B_1\times\dots\times B_n$ 
    \begin{align*}
      \Bf_j \simeq \Af{\restriction}_{\eta(\{b_1\}\times \dots\times
        \{b_{j-1}\} \times B_j \times \{b_{j+1}\} \times \dots \times \{b_n\})}.
    \end{align*}
  \item   
    Let $\Cc_1, \dots, \Cc_n$ be classes of structures. A structure
    $\Af$ is a \emph{sum-of-box augmentation} of
    $(\Cc_1, \dots, \Cc_n)$ if $\Af$ is a 
    sum-augmentation of 
    structures $\Bf_1, \dots, \Bf_k$ such
    that each $\Bf_j$ is a box-augmentation of  structures $\Cf_{j,1},
    \dots, \Cf_{j,n}$ with  $\Cf_{j,i}\in \Cc_i$. 
  \end{itemize}
\end{definition}


\begin{definition}
  Let $\Af=(A, \leq)$ be a sum-of-box augmentation of structures 
  $\Bf_{i,j}=(B_{i,j}, \leq_{i,j} )$ via the map 
$
%  \begin{align*}
    \eta: \bigsqcup_{i=1}^n  \prod_{j=1}^k  B_{i,j}  \to A.
%  \end{align*}
$
  This sum-of-box augmentation is called 
  \emph{tamely colourable}
  if for each $1\leq j \leq k$ there is a function 
  $\varphi_j: (\bigsqcup_{i=1}^n B_{i,j})^2 \to C_j$
  with a finite range $C_j$  such that 
  the $(\varphi_j)_{1\leq j \leq k}$ determine the edges of $\Af$ in
  the sense that there is 
  a set $M \subseteq \prod_{j=1}^k C_j$ such that
  $\eta(b_1,\dots, b_k) \leq \eta(b_1',\dots,b_k')$ iff
  $\left( \varphi_1(b_1,b_1'), \dots, \varphi_k(b_k,b_k')\right)\in M$. 
\end{definition}





\subsection{Decomposition of Scattered-Automatic-Structures}
\label{sec:decomp-scattered}

In this section, we prove that the sum- and box-augmentation
technique applies to finite word scattered-oracle-automatic
structures. 
Fix an arbitrary scattered order $\Lf$ with 
$\FC(\Lf)=\alpha \geq 1$. Assume that 
$\Lf = \sum_{z\in \Z} \Lf_z$ where each $\Lf_z$ is a
(possibly empty) suborder with $\FC(\Lf_z) < \alpha$.
We first introduce notation concerning definable subgraphs.

\begin{definition}
  Let $o\in\Words{\Lf}$ be some oracle.
  Let $\Gf=(V, E)$ be a finite word $\Lf$-$o$-automatic graph. 
  For each parameter automaton $\Ac$ and parameter $p\in \Words{\Lf}$,
  we write  $\Gf^\Ac_p$ for the induced subgraph of $\Gf$ with domain   
$%  \begin{align*}
    V^\Ac_p:=\{w\in V\mid w\otimes p \in L(\Ac)\}.     
$%  \end{align*}
\end{definition}
We write $\Gf_p$ and $V_p$  for $\Gf^\Ac_p$ and $V^\Ac_p$  if $\Ac$ is
clear from the context. 


\begin{definition}
  Let $c_0=(C_0,D_0)$ and $c_1=(C_1,D_1)$ be cuts of $\Lf$. 
  For  a finite  $\Lf$-word $w$ we say $w$ is a 
  $(c_0,c_1)$-parameter if $\supp(w)\subseteq D_0\cap C_1$, i.e., 
  the support of $w$ is completely between $c_0$ and
  $c_1$. 
\end{definition}



\emph{For the rest of this section, we fix two numbers 
$z_0<z_1\in \Z$ and define the  cuts
$c_0:=(\sum_{z < z_0} \Lf_z, \sum_{z\geq z_0} \Lf_z)$ and
$c_1:=(\sum_{z \leq  z_1} \Lf_z, \sum_{z > z_1} \Lf_z)$.
We also define the scattered orders 
$\Lf_{\LEFT}:=\sum_{z < z_0} \Lf_z$ and
$\Lf_{\RIGHT}:=\sum_{z > z_1} \Lf_z$.}
The main result of this section is a uniform sum-of-box decomposition 
of all substructures defined by a given parameter automaton. 

\begin{theorem} \label{thm:Decomposition}
  Let  $\Gf$ be 
  some finite word $\Lf$-oracle-automatic graph $(V,E)$
  where $E$ is recognised by some automaton $\Ac_E$ with state set
  $Q_E$ and 
  let $\Ac$ be a parameter automaton with state set $Q$. 
  There are
  \begin{itemize}% \exp(n^2+ 2m^2)
  \item a set $\Cc_\LEFT$ of $\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$
    many $\Lf_{\LEFT}$-oracle-automatic graphs, and
  \item  a set $\Cc_\RIGHT$ of $\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$
    many $\Lf_{\RIGHT}$-oracle-automatic graphs,
  \end{itemize}
  such that for each $(c_0,c_1)$-parameter $p$ the subgraph 
  $\Gf^{\Ac}_p$ is a tamely-colourable sum-of-box-augmentation
  of $(\Cc_\LEFT, \Fc_{\Lf_{z_0}}, \Fc_{\Lf_{z_0+1}}, \dots, 
  \Fc_{\Lf_{z_1}}, \Cc_\RIGHT)$. \footnote{Recall that $\Fc_{\Lf}$ is the class of all finite word $\Lf$-oracle-automatic graphs, see Definition \ref{definition: L-automatic structure}.} 
\end{theorem} 
\begin{proof} 
  Let $o$ be the oracle such that $\Gf$ is finite word 
  $\Lf$-$o$-automatic. 
  By definition, we can write $\Lf$ as the sum 
$
%  \begin{align*}
    \Lf_{\LEFT} + \Lf_{z_0} + \Lf_{z_0+1} +\dots +
    \Lf_{z_1} + \Lf_{\RIGHT}.   
%  \end{align*}
$
  Induced by this decomposition there is a decomposition of 
  any $\Lf$-word $w$ as 
%  \begin{align*}
$    w = w_{\LEFT} w_{z_0} w_{z_0+1} \dots w_{z_1} w_{\RIGHT}
$
%  \end{align*}
  such that $w_j$ is an $\Lf_j$-word. In particular, our parameter
  and oracle decompose as
  \begin{align*}
    p = p_{\LEFT} p_{z_0} p_{z_0+1} \dots p_{z_1} p_{\RIGHT}\text{\quad
      and\quad }
    o = o_{\LEFT} o_{z_0} o_{z_0+1} \dots o_{z_1} o_{\RIGHT}.
  \end{align*}
  Independently of the choice of the $(c_0,c_1)$-parameter 
  $p$, $p_{\LEFT}$ and
  $p_{\RIGHT}$ are constant functions (with value $\diamond$).
  
  In order to construct a sum-of-box decomposition of $\Gf_p$, we
  first define the building blocks of this decomposition. 
  For this purpose, we define equivalence relations 
  $\wordsim{p\otimes o}{i}$ for each 
  $i\in\{\LEFT, \RIGHT, z_0, {z_0+1}, \dots, z_1\}$ on $\Lf_i$-words
  as follows.   
  For $\Lf_i$-words $w,w'$ set  $w \wordsim{p\otimes o}{i} w'$ if and only if
  \begin{enumerate}
  \item for all $q,q'\in Q$ \quad
    $q \run{w\otimes p_i\otimes o_i}{\Ac} q'  \Longleftrightarrow 
     q \run{w'\otimes p_i \otimes o_i}{\Ac} q'$ and
   \item for all $q,q'\in Q_E$ \quad
    $q \run{w\otimes w \otimes o_i}{\Ac_E} q'  \Longleftrightarrow 
     q \run{w'\otimes w' \otimes o_i}{\Ac_E} q'$.
  \end{enumerate}
  Note that for fixed $i,p,o$ there are at most $\exp({\lvert Q\times Q\rvert+
    \lvert Q_E\times Q_E \rvert})$ many $\wordsim{p\otimes o}{i}$
  equivalence classes.   
  As domains of the $\alpha_i$-oracle-automatic building blocks of our
  decomposition we use the sets
  $K(i,w,p,o):=\{ x\mid x \wordsim{p\otimes o}{i} w\}$ for each
  $\Lf_i$-word $w$. 
  We augment this notation by writing $K(i,v,p,o):=K(i,w,p,o)$ for $\Lf$-words $v$, where $w$ is the restriction of $v$ to $\Lf_i$. 
  Now for each $M\subseteq Q_E\times Q_E$ we define a structure
  $\Kf^M(i,w,p,o)=(K(i,w,p,o), E^M)$ where
  $(w_1,w_2)\in E^M$ if 
  $w_1,w_2\in K(i,w,p,o)$ and there is a  $(q,q')\in M$ such that
  $q \run{w_1\otimes w_2 \otimes o}{\Ac_E} q'$. 
  Recall that $p_{\LEFT}$ and $p_{\RIGHT}$ are independent
  of the concrete choice of the $(c_0,c_1)$-parameter $p$ whence (for
  fixed $o$) the sets
  \begin{align*}
    \Cc_{\LEFT}:=\left\{\Kf^M(\LEFT,w,p,o)\mid M \subseteq Q_E\times Q_E, p
     \text{ a }  (c_0,c_1)\text{-parameter}  \right\}\\
    \Cc_{\RIGHT}:=\left\{\Kf^M(\RIGHT,w,p,o)\mid M \subseteq Q_E\times Q_E, p
      \text{ a } (c_0,c_1)\text{-parameter}  \right\}
  \end{align*}
  have each at most $\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$ many
  elements (up to isomorphisms). 

  Our next goal is the definition of the function $\eta$ that
  witnesses the decomposition claimed in this theorem. 
  For this purpose, let $\wordsim{p\otimes o}{}$ denote the
  equivalence on 
  $\Lf$-words that is the product of the 
  $\wordsim{p\otimes o}{i}$.\footnote{
    Thus,  for $w=w_{\LEFT}w_{z_0}w_{z_0+1}\dots w_{z_1} w_{\RIGHT}$ and
    $v=v_{\LEFT}v_{z_0}v_{z_0+1}\dots v_{z_1} v_{\RIGHT}$ we have
    $w\wordsim{p\otimes o}{} v$ iff
    $w_i\wordsim{p\otimes o}{i} v_i$ for all 
    $i\in\{\LEFT,\RIGHT, z_0,  z_0+1, \dots, z_1\}$.
  }
  Let
  \begin{align*}
    \eta: &\bigsqcup_{[w]\in V_p /{\wordsim{p\otimes o}{}}}
    K(\LEFT, w,p,o) \times \left(\prod_{i=z_0}^{z_1} K(i,w,p,o)\right )
    \times K(\RIGHT, w,p,o)  \longrightarrow V_p\\
    &(x_{\LEFT}, x_{z_0}, x_{z_0+1}, \dots, x_{z_1}, x_{\RIGHT}) \mapsto 
    x:=x_{\LEFT}x_{z_0} x_{z_0+1}\dots x_{z_1}x_{\RIGHT}. 
  \end{align*}
  It follows from the definitions that $\eta$ is a well-defined
  bijection (using the fact that some $\Lf$-word $x$ belongs to
  $V_p$ iff there is a run 
  \begin{align*}
    q_I \run{x_{\LEFT}\otimes p_{\LEFT} \otimes
    o_{\LEFT}}{\Ac} q_{z_0}  \run{x_{z_0}\otimes p_{z_0} \otimes
    o_{z_0}}{\Ac} q_{z_0+1} \dots q_{z_1} \run{x_{\RIGHT} \otimes p_{\RIGHT}
      \otimes o_{\RIGHT}}{\Ac} q_F    
  \end{align*}
  for some initial state $q_I$ and a final state $q_F$). 
  
  In order to finish the proof, we show that  $\Gf_p$ is a
  tamely-colourable sum-of-box-augmentation of 
  $(\Cc_\LEFT, \Fc_{\Lf_{z_0}}, \Fc_{\Lf_{z_0+1}}, \dots, 
  \Fc_{\Lf_{z_1}}, \Cc_\RIGHT)$ via
  $\eta$. For any $w\in V_p$, let
  $\Ff_w$ be the restriction of $\Gf_p$ to 
  $\eta\left(    K(\LEFT, w,p,o) \times \left(\prod_{i=z_0}^{z_1}
      K(i,w,p,o)\right )  \times K(\RIGHT, w,p,o)\right)$. 
  It is clear that $\Gf_p$ is a sum augmentation of 
  $(\Ff_{w_1}, \Ff_{w_2}, \dots, \Ff_{w_k})$ for $w_i$ representatives of
  the $\wordsim{p\otimes o}{}$-classes. 
  From now on 
  let  $I_E (F_E)$ denote the initial (final) states of
  $\Ac_E$.
  \begin{enumerate}
  \item Fix \mbox{$w= w_{\LEFT} w_{z_0} w_{z_0+1} \dots w_{z_1} w_{\RIGHT}\in
      V_p$}. We show that $\Ff_w$ is a box-augmen\-tation of
    $(\Cc_\LEFT, \Fc_{\Lf_{z_0}}, \Fc_{\Lf_{z_0+1}}, \dots, 
    \Fc_{\Lf_{z_1}}, \Cc_\RIGHT)$. For this purpose, fix 
    $i\in \{\LEFT, \RIGHT, z_0, z_0+1, \dots, z_1\}$  and 
    let $\overset{\leftarrow}{w}:=  w_{\LEFT}\dots w_{i-1}$,
    $\overset{\leftarrow}{o} :=  o_{\LEFT}\dots o_{i-1}$,
    $\overset{\rightarrow}{w} :=  w_{i+1}\dots w_{\RIGHT}$, and 
    $\overset{\rightarrow}{o} :=  o_{i+1}\dots o_{\RIGHT}$. 
    Let $M_i$ be the set defined by 
    \begin{equation}
      \label{eq:boxelement}
%    \begin{aligned}
      (q_1,q_2)\in M_i \Longleftrightarrow \exists q_I\in I_E, q_F\in F_E
      \quad
      q_I \run
      {\overset{\leftarrow}{w} \otimes 
        \overset{\leftarrow}{w} \otimes 
        \overset{\leftarrow}{o}}{ \Ac_E} q_1 \text{ and }
      q_2 \run{
        \overset{\rightarrow}{w} \otimes 
        \overset{\rightarrow}{w} \otimes 
        \overset{\rightarrow}{o}}{ \Ac_E} q_F.
%    \end{aligned}
    \end{equation}
    The function
    \begin{align*}
      \eta^{w}_i: K(i,w,p,o) \to  V_p, \quad
      x_i \mapsto w_{\LEFT} w_{z_0} w_{z_0+1} \dots w_{i-1} x_i w_{i+1}
    \dots w_{z_1} w_{\RIGHT}
    \end{align*}
    embeds $\Kf^{M_i}(i,w,p,o)$ into $\Gf_p$
    because
    \begin{align*}
      &\forall x_i,y_i\in K(i,w,p,o)\quad (x_i,y_i)\in E^{M_i} \\
      \Leftrightarrow &\exists (q_1,q_2)\in M_i \quad  q_1 \run{x_i\otimes
        y_i \otimes o_i}{\Ac_E} q_2\\
      \overset{\eqref{eq:boxelement}}{\Leftrightarrow} 
      &\exists q_I\in I_E, q_F\in F_E \quad
      q_I \run{ \overset{\leftarrow}{w} \otimes 
        \overset{\leftarrow}{w} \otimes \overset{\leftarrow}{o}}{ \Ac_E} q_1
      \run{x_i\otimes  y_i \otimes o_i}{\Ac_E} q_2
      \run{\overset{\rightarrow}{w} \otimes 
        \overset{\rightarrow}{w} \otimes
        \overset{\rightarrow}{o}}{ \Ac_E} q_F \\
      \Leftrightarrow 
      &\left(\eta^w_i(x_i), \eta^w_i(y_i)\right) \in E.
    \end{align*}
  \item We show that the decomposition is tamely colourable. 
    For all $j\in \{\LEFT, \RIGHT, z_0, z_0+1, \dots, z_1\}$,
  %  all words $w,v\in V_p$, all $x_j\in K(j,w,p,o)$, and all $y_j\in
  %  K(j,v,p,o)$, 
    let
      $c_j: (\bigsqcup_{[w]\in V_p/\wordsim{p\otimes o}{}} K(j,w,p,o))^2 \to
      Q_E^2$ be the colouring function satisfying
      \mbox{$c_j(x_j,y_j) := \{ (q,q')\in A_E \mid 
      q\run{x_j\otimes y_j\otimes o_j}{\Ac_E} q'\}$.}
%    \begin{align*}
%      &c_j: \bigsqcup_{[w]\in V_p/\wordsim{p\otimes o}{}} K(j,w,p,o) \to
%      Q_E^2\\
%      &c_j(x_j,y_j) := \{ (q,q')\in A_E \mid 
%      q\run{x_j\otimes y_j\otimes o_j}{\Ac_E} q'\}.
%    \end{align*}
    The colour functions  $(c_j)_{j\in\{\LEFT, \RIGHT, z_0, z_0+1,
      \dots, z_1)}$ determine  $E$ because for
    $w = w_\LEFT w_{z_0} w_{z_0+1} \dots w_{z_1} w_\RIGHT$ and
    \mbox{$v = v_\LEFT v_{z_0} v_{z_0+1} \dots v_{z_1} v_\RIGHT$, }
    \begin{align*}
    &(w_\LEFT w_{z_0} w_{z_0+1} \dots w_{z_1} w_\RIGHT,
    v_\LEFT v_{z_0} v_{z_0+1} \dots v_{z_1} v_\RIGHT)\in E\\
    \Longleftrightarrow 
    &\exists q_0, \dots, q_k\in Q_E \ %\quad 
    \left(
    \begin{aligned}
      &q_0\in I_E, q_k\in F_E,
      \text{ and } \\     
      &q_0 \run{w_\LEFT\otimes v_\LEFT \otimes o_\LEFT}{\Ac_E} q_1 
      \run{w_{z_0}\otimes v_{z_0} \otimes o_{z_0}}{\Ac_E} q_2   
      \dots 
      % q_{k-2}
      %\run{w_{z_1}\otimes v_{z_1} \otimes o_{z_1}}{\Ac_E} 
      q_{k-1} 
      \run{w_{\RIGHT}\otimes v_{\RIGHT} \otimes o_{\RIGHT}}{\Ac_E} q_k
    \end{aligned} \right)
    \\
    \Longleftrightarrow
    &\exists q_0, \dots, q_k\in Q_E \ %\quad 
    \left(
      \begin{aligned}
        &q_0\in I_E, q_k\in F_E,   \text{ and }\\
        &(q_{i-1},q_{i})\in c_j(w_j,v_j)        
       \text{ with } j=
        \begin{cases}
          \LEFT &\text{if }i=1,\\
          \RIGHT &\text{if } i={k},\\
          z_0+m &\text{if } i=m  
        \end{cases}
      \end{aligned} \right) . %\qed 
    \end{align*}
  \end{enumerate} 
  %\fixme{add \qed's}
\end{proof}





\section{Bounds on 
  Scattered-Oracle-Automatic Structures} 
\label{sec:LinOrd}

\subsection{FC-Ranks of Linear-Orders}
\label{sec:fcrankbound}

In this section, we first study the question which scattered linear orders
are $\Lf$-oracle-automatic for a fixed order $\Lf$. We provide a sharp
bound on the $\FC$-rank. For the upper bound we lift Schlicht and
Stephan's result \cite{SchlichtS11} using our new sum- and box-decomposition
from the case where $\Lf$ is an ordinal (detailed proof in Appendix
\ref{sec:ProofOnScatteredOrders}):  

\begin{theorem} \label{thm:BoundsonScatteredOrders}
  Let $\Lf$ be a scattered order of $\FCstar$ rank
  $1+\alpha$ ($0$, respectively) for some ordinal $\alpha$. 
  Then every finite word $\Lf$-oracle-automatic scattered linear order
  $\Af$ satisfies 
  \mbox{$\FCstar(\Af) < \omega^{\alpha+1}$} ($\FCstar(\Af) <\omega^0=1$, respectively).
\end{theorem}

If $\Lf$ is an ordinal of the form $\omega^{1+\alpha}$,
Schlicht and Stephan \cite{SchlichtS11} showed that the
supremum of the 
$\Lf$-automatic ordinals is exactly 
$\omega^{\omega^{\alpha+1}}$ whence Theorem
\ref{thm:BoundsonScatteredOrders} is optimal.
From our theorem we can also derive the following characterisation of
finite $\FC$-rank presentable ordinals (cf.~Appendix 
\ref{sec:OrdinalsOverFiniteRankOrders}).

\begin{corollary}
  Let $\Lf$ be a scattered linear order with
  $\FC(\Lf)<\omega$. The finite word $\Lf$-oracle-automatic ordinals
  are exactly 
  those below $\omega^{\omega^{\FC(\Lf)+1}}$. 
\end{corollary}
Here, the oracle is crucial: $0$ and $1$ 
are the only  finite word $\Z^n$-automatic ordinals if $n\geq 1$
(any $\Z^n$-automatic linear order with $2$ elements contains a
copy of $\Z$). 



\subsection{Ranks of Well-Founded Automatic Order Forests}
\label{sec:Forests}

We next study scattered-oracle-automatic well-founded order forests. 
Kartzow et al.~\cite{KaLiLo12} proved compatibility of the ordinal height
with sum- and box-augmentations. Together with our decomposition
theorem this yields a bound on the height of an
$\Lf$-oracle-automatic well-founded order forest in terms of
$\FC(\Lf)$. Unfortunately, in important cases these bounds are not
optimal. For scattered orders $\Lf$ where the set of finite
$\Lf$-words allow an $\Lf$-oracle-automatic order which is scattered,
we can obtain better bounds. If $\Lf$ is an ordinal or has finite
$\FC$-rank, the set of
$\Lf$-words allows such a scattered ordering.
If the finite $\Lf$-words
admit an $\Lf$-automatic scattered order $\leq$, the
Kleene-Brouwer ordering of an $\Lf$-oracle-automatic well-founded
order forest with respect to $\leq$ is $\Lf$-oracle-automatic
again. Thus, its FC-rank is bounded 
by our previous result. Adapting a result of Kuske et
al.\cite{KuLiLo11} relating the $\FC$-rank of the Kleene-Brouwer
ordering with the height of the forest, we derive a bound on 
the height (cf.~Appendix \ref{app:RanksofForests}). Our main result on
forests is as follows. 

\begin{theorem}\label{thm:BoundsOnTreeRanks}
  \begin{itemize}
  \item Let $\Lf$ be an ordinal or a  scattered linear
    order with $\FC(\Lf)<\omega$.
    Each $\Lf$-oracle-automatic forest $\Ff=(F, \leq)$ 
    has rank strictly below $\omega^{\FC(\Lf)+1}$.
  \item Let $\Lf$ be some scattered linear order.
    Each $\Lf$-oracle-automatic forest $\Ff=(F, \leq)$ 
    has rank strictly below $\omega^{\omega\cdot (\FC(\Lf)+1)}$.
  \end{itemize}
\end{theorem}
\begin{remark}
  The bounds in the first part are optimal: for each ordinal $\Lf$ and
  each $c\in \N$, we can construct an $\Lf$-automatic tree of height
  $\omega^{\FC(\Lf)}\cdot c$ (cf.~Appendix \ref{sec:HighRanks}).
\end{remark}



\section{Separation of Tree- and Ordinal-Automatic Structures}
\label{sec:BooleanAlgebraNotAutomatic}

\begin{theorem}
  The countable atomless Boolean algebra is not finite word
  $\Lf$-automatic for any ordinal $\Lf$. 
\end{theorem}

This theorem is proved by first showing that, if the atomless Boolean
algebra is finite word $\Lf$-automatic for some ordinal $\Lf$, then it
already is $\omega^n$-automatic for some $n\in\N$. 
This follows because any finite word $\Lf$-automatic structure for $\Lf$ an ordinal above $\omega^{\omega}$ has a
sufficiently elementary substructure that has a $\omega^n$-automatic presentation for some $n\in\N$. 
In the case of the countable atomless Boolean algebra any $\Sigma_3$-elementary
substructure is isomorphic to the whole algebra. 
Extending Khoussainov et al.'s
monoid growth rate argument for automatic structures 
(cf.~\cite{DBLP:journals/lmcs/KhoussainovNRS07}) to the $\omega^n$-setting,
we can reject this assumption (cf. Appendix \ref{sec: Boolean algebra}). 
This answers a question of Frank Stephan. 


\bibliography{ordinal-automata}
\bibliographystyle{plain}


%\begin{comment}
  

\newpage
\appendix



\section{Basics on Scattered Linear Orders}

Recall the following basic (folklore) results. 

\begin{lemma} \label{lem:ClosedIntSmallerFCStar}
  Let $\Lf=(L, \leq)$ be a scattered linear order with
  $\FC(\Lf)=\alpha$.  For all $l,l'\in
  L$, there are some $n\in\N$ and scattered linear orders $\Lf_1,
  \Lf_2, \dots, \Lf_n$ of condensation rank strictly below $\alpha$ 
  such that $[l,l'] \cong  \Lf_1+ \Lf_2 + \dots + \Lf_n$. 
\end{lemma}
\begin{proof}
  $\Lf$ can be written as $\sum_{i\in\Z} \Lf_i$ for $\Lf_i$ scattered
  linear orders with $\FC(\Lf)<\alpha$. If $l$ comes from the $j$-th
  factor of this sum and $l'$ form the $j'$-th, then $[l,l']$ is
  isomorphic to $\Lf'_j + \sum_{i=j+1}^{j'-1} \Lf_i + \Lf'_{j'}$ where
  $\Lf'_j$ and $\Lf'_{j'}$ are  suborders of $\Lf_j$ and $\Lf_{j'}$
  whence they have rank below $\alpha$. 
\qed \end{proof}


\begin{lemma} \label{lem:FCstarSumsIncreaseRank}
  Let $\gamma\in\{\omega,\omega^*, \zeta\}$, 
  $\Lf_i$ be a scattered order of $\FCstar$ rank $\alpha$.
  The order $\Lf := \sum_{i\in\gamma} \Lf_i$ is of rank 
  $\FCstar(\Lf)=\alpha+1$. 
\end{lemma}
\begin{proof}
  Since $\FCstar(\Lf_i)=\alpha$, for all 
  $\beta<\alpha$ the $\beta$-th condensation of $\Lf_i$ contains
  infinitely many nodes. Thus, also the $\beta$-th condensation of
  $\Lf$ contains infinitely many equivalence classes containing
  elements in $\Lf_i$. 
  Thus, for each $i\in \gamma$ such that $i+2\in\gamma$ and
  for every $x_i\in\Lf_i$, $x_{i+2}\in\Lf_{i+2}$ 
  the $\beta$ condensation of $x_i$ and 
  the $\beta$-condensation of $x_{i+2}$ 
  are separated by infinitely many nodes (the $\beta$ condensations of
  $\Lf_{i+1}$). 
  Thus, the $\alpha$ condensation of $\Lf$ does not identify 
  nodes of $\Lf_i$ and $\Lf_{i+2}$. 
  Thus, it contains a suborder isomorphic to $\gamma$, whence 
  $\FCstar(\Lf)\geq \alpha+1$.
  On the other hand, since each $\Lf_i$ has rank $\alpha$ the
  $\alpha$-condensation of $\Lf$ is a $\gamma$-sum over finite linear
  orders. 
  Hence its $\alpha+1$-condensation is finite and
  $\FCstar(\Lf)\leq\alpha+1$. 
\qed \end{proof}


\begin{lemma}\label{lem:AllFCstarRankAsSubOrders}
  [Lemma 4.16 of \cite{Huschenbett12}]
  Let $\Lf$ be a linear order  and $\alpha<\FC(\Lf)$. 
  There is a closed interval $I$ of $\Lf$ such that
  $I$ is a scattered linear suborder of $\Lf$,
  $\FC(I) = \alpha+1$, and
  $\FCstar(I) = \alpha$. 
\end{lemma}


%\begin{lemma}\label{lem:FCStarandCFCompat}
%  Let $\Lf$ be a scattered linear order with
%  $\FCstar(\Lf)=\alpha$. Then $\Lf$ decomposes as a finite sum
%  $\Lf=\Lf_1+\dots+\Lf_n$ such that $\FC(\Lf_i)=\alpha$. 
%\end{lemma}
%\begin{proof}
%  Recall that by definition $\sim_\alpha$ has finitely
%  many equivalence classes $L_1, \dots, L_n$. 
%  
%\qed \end{proof}


\section{Correctness of the Automaton in Example \ref{exa:FiniteWordsRec}}
\label{sec:FiniteWordsRecognisable}

  States 
  $e_l$ and $e_r$
  report errors from left and from right, respectively, i.e., a cut is
  forced to be visited in state $e_l$ if 
  it is a right limit step such that left of this limit infinitely many
  positive positions appear.
  
  On input $w$, the successor transitions mark the support of $w$ by
  state $p$ and all other successor positions in $w$ by $n$. 
  Let $P(w)\subseteq \Cuts(w)$ be defined by
  $(C,D)\in P(w)$ if $\exists x\in \supp(w)$ such that
  $x=\max(C)$. If $w$ has finite support, then 
  $$r(c):=
  \begin{cases}
    p &\text{if }c\in P(w)\\
    n & \text{otherwise}
  \end{cases}
  $$ defines an accepting run on $w$. 

  We now prove that there is no accepting run if $w$ is not a finite
  word. Heading for a contradiction assume that $r$ is an accepting
  run of $\Ac$ on $w$ and $w$ has infinite support. Then 
  $r((\emptyset, L)) = n = r((L, \emptyset))$. 
  We want to show that there is a cut $c$ such that $r(c)=e_l$ or
  $r(c)=e_r$. 

  If we are able to show this, we arrive at a
  contradiction: if $r(c)=e_l$ then $c$ is not the maximal cut. But
  there is no successor transition and no left limit transition from
  state $e_l$. Thus, $r$ cannot assign states to the cuts to the right
  of $c$, which is a contradiction. If state $e_r$ occurs, the
  argument is the same using the cuts to the left of $c$. 
  
  We show that there is a cut that is assigned an error state $e_l$ or
  $e_r$. 
  Assume that there is an infinite ascending chain
  $l_1<l_2<l_3<\dots$ in $\Lf$  such that 
  $\{l_i\mid i\in\N\}\subseteq \supp(w)$.
  For $C:=\{ x\in L\mid \exists i\in\N \quad x\leq l_i\}$ and
  $D:=L\setminus C$ the cut $c:=(C, D)$ has no direct
  predecessor. Moreover,  
  $p\in \lim_{c^-} r$ because state $p$ occurs at each cut associated
  to one of the $l_i$. Thus, if there is a right limit transition
  applicable at $c$, it assigns state $e_l$ to $c$. 
  If there is no infinite ascending chain in $\supp(w)$, then there is
  an infinite descending chain. The analogous argument shows that then
  state $e_r$ occurs. 



\section{Proof of Theorem \ref{thm:BoundsonScatteredOrders}}
\label{sec:ProofOnScatteredOrders}


Huschenbett \cite{Huschenbett13} used the sum-of-box decomposition
technique in 
order to prove a strict bound on the finite condensation rank of
tree-automatic  scattered linear orders. His result relies on the fact
that the finite condensation rank behaves well with box-decompositions
in the following sense. Let $\alpha_0\oplus\dots\oplus\alpha_n$ denote
the natural sum (also known as commutative sum or Hessenberg sum) of
$\alpha_0,...,\alpha_n$.  

\begin{lemma}
  \label{lem:FCStarAndBox}
  [Proposition 4.11 in \cite{Huschenbett12}]
  For each  scattered linear order $\Af$ that is a tamely-colourable
  box-augmentation of 
  $\Bf_1, \dots, \Bf_n$, its rank is bounded by
  \begin{align*}
    \FCstar(\Af) \leq \FCstar(\Bf_1) \oplus \FCstar(\Bf_2) \oplus
    \dots \oplus \FCstar(\Bf_n).
      \end{align*}
\end{lemma}

Moreover, Khoussainov et al. have already shown that $\FCstar$ rank
behaves well with sum-augmentations.
\begin{lemma} 
  \label{lem:FCStarAndSum}
  [Proposition 4.4 in \cite{KhoussainovRS05}]
  For each  scattered linear order $\Af$ that is a sum-augmentation of
  $\Bf_1, \dots, \Bf_n$, its rank is determined by
  \begin{align*}
    \FCstar(\Af) = \max\{\FCstar(\Bf_1), \FCstar(\Bf_2),
    \dots, \FCstar(\Bf_n)\}.
  \end{align*}
\end{lemma}


\begin{proposition}
  Let $\alpha$ be a scattered order of $\FC$ rank
  $1+\gamma$ ($0$, respectively) for some ordinal $\gamma$. 
  Every $\alpha$-oracle-automatic scattered linear order has $\FCstar$
  rank strictly below $\omega^{\gamma+1}$ ($\omega^0=1$, respectively).
\end{proposition}
\begin{proof}
  In the case $\FC(\alpha)=0$ the domain of an $\alpha$-automatic structure
  has at most $\lvert \Sigma \rvert$ many elements. The theorem
  follows because every finite linear order has $\FCstar$ rank $0$. 

  Now let $\FC(\alpha)=1+\gamma$. As induction hypothesis assume that
  the theorem holds for all orders $\beta$ with $\FC(\beta)<1+\gamma$. 
  Heading for a contradiction assume that $\Lf=(L, \leq)$ is an
  $\alpha$-oracle-automatic scattered linear order such that
  $\FCstar(\Lf)\geq \omega^{\gamma+1}$. Let $\leq$ be recognised by
  some automaton with state set $Q_\leq$. 
  Due to  Lemma \ref{lem:AllFCstarRankAsSubOrders} the automaton $\Ac$
  corresponding to the 
  formula $\varphi(x,y_1,y_2) := y_1\leq x \leq y_2$ is a parameter
  automaton such that for each $n\in\N$ there is a parameter $p_n$
  such that $\Lf_{p_n}$ is a scattered linear order with
  $\FCstar(\Lf_{p_n}) = \omega^{\gamma}\cdot n$. Assume that $\Ac$ has
  state set $Q$.
  
  Now, fix some $n_0\in \N$ such that 
  $n_0 >  4^{2+2\cdot \exp(\lvert Q \rvert^2+2\lvert Q_\leq\rvert^2)}$.
  Due to Theorem \ref{thm:Decomposition}, there are sets
  $\Cc_0, \Cc_1$ of size $\exp(\lvert Q \rvert^2+2\lvert Q_\leq\rvert^2)$
  such that for each $n\leq n_0$, $\Lf_{p_n}$ is a tamely-colourable
  sum-of-box-augmentation of $\Cc_0, \Cc_1$ and 
  sets of $\beta_i$-oracle-automatic structures where
  $\FC(\beta_i)<\FC(\alpha)$ (cf. Lemma \ref{lem:ClosedIntSmallerFCStar}).
  By choice of $n_0$, there is some $1\leq m < \frac{n_0}{4}$ such that
  for all  structures  $\Af\in \Cc_0\cup \Cc_1$
  \begin{align}
    \label{eq:FCRankGaps}
    \begin{aligned}
      &\FCstar(\Af) \leq  \omega^{\gamma} \cdot m \text{ or}\\
      &\FCstar(\Af) > \omega^{\gamma} \cdot 4m.
    \end{aligned}
  \end{align}
  Now consider the decomposition of 
  $\Lf_{p_{4m}}$. Due to Lemma \ref{lem:FCStarAndSum} 
  there is a suborder $\Lf'$ of $\Lf_{p_{4m}}$  with
  $\FCstar(\Lf')=\omega^{\gamma} \cdot 4m$ that is tamely-colourable
  box-augmentation of structures
  $(\Cf_0, \Cf_1, \Bf_1, \dots, \Bf_k)$ where
  $\Cf_0\in \Cc_0, \Cf_1\in \Cc_1$, and $\Bf_i$ a
  $\beta_i$-oracle-automatic structure for each $1\leq i \leq k$. 
  Note that for each $1\leq i \leq k$, by induction hypothesis
  $\FCstar(\Bf_i) < \omega^{\gamma_i+1}$ for some $\gamma_i<\gamma$. 
  Thus,
  \begin{equation*}
    \FCstar(\Bf_1) \oplus
    \dots \oplus  \FCstar(\Bf_k) < \omega^{\max\{\gamma_i\mid 1\leq i
      \leq k\}+1}\leq \omega^{\gamma}.
  \end{equation*}
  Moreover, since $\Cf_0$ and $\Cf_1$ are substructures of $\Lf'$, 
  we have $\FCstar(\Cf_i)\leq \omega^\gamma \cdot 4m$ whence 
  \eqref{eq:FCRankGaps}
  implies that 
  $\FCstar(\Cf_i) \leq \omega^{\gamma}\cdot m$ for $i\in\{0,1\}$. 
  Due to the properties of $\oplus$ and Lemma \ref{lem:FCStarAndBox}
  we arrive at the contradiction 
  \begin{align*}
    \FCstar(\Lf')=\omega^{\gamma} \cdot 4m &\leq
    \FCstar(\Cf_0) \oplus \FCstar(\Cf_1) \oplus \FCstar(\Bf_1) \oplus
    \dots \oplus
    \FCstar(\Bf_k)\\  
    &\leq   \omega^\gamma\cdot m  \oplus \omega^\gamma \oplus
    \omega^\gamma \cdot m \\
    &<    \omega^{\gamma} \cdot 4m.
  \end{align*}
\qed \end{proof}


Theorem \ref{thm:BoundsonScatteredOrders} now follows as a corollary
of this Proposition.

\begin{corollary}
  Let $\alpha$ be a scattered order of $\FCstar$ rank
  $1+\gamma$ ($0$, respectively) for some ordinal $\gamma$. 
  Every finite word $\alpha$-oracle-automatic scattered linear order
  has $\FCstar$ 
  rank strictly below $\omega^{\gamma+1}$ ($\omega^0=1$, respectively).
\end{corollary}
\begin{proof}
  If $\alpha$ is a scattered linear order such that
  $\FCstar(\alpha)=1+\gamma$, then there are linear orders 
  $\alpha_i$  with 
  $\FC(\alpha_i)\leq 1+\gamma$
  for $1\leq i \leq k$ such that
  $\alpha=\sum_{i=1}^k \alpha_i$.
  
  Theorem \ref{thm:Decomposition} implies that each finite word
  $\alpha$-oracle-automatic scattered linear order $\Lf$ is a tamely
  colourable sum-of-box augmentations of 
  $(\Fc_{\alpha_1}, \dots, \Fc_{\alpha_k})$,  the classes of finite
  word $\alpha_i$-oracle-automatic structures. 
  Due to Lemmas \ref{lem:FCStarAndBox} and \ref{lem:FCStarAndSum}
  there are  $\alpha_i$-oracle-automatic scattered linear orders
  $\Lf_i$ (for $1\leq i \leq k$) such that
  $\FCstar(\Lf) \leq \FCstar(\Lf_1) \oplus \dots \oplus
  \FCstar(\Lf_k)$. Since $\FCstar(\Lf_i) < \omega^{\gamma+1}$ for each
  $1\leq i \leq k$, we immediately conclude that
  $\FCstar(\Lf) < \omega^{\gamma+1}$. 
\qed \end{proof}




\section{Ranks of Forests}
\label{app:RanksofForests}

We now introduce a variant of the height of a well-founded partial
order called \emph{infinity rank} and
denoted by $\infrank$.

\begin{definition}
  Let $\Pf=(P, \leq)$ be a well-founded partial order.
  We define the ordinal valued $\infrank$ of a node $p\in P$ inductively by
  \begin{align*}
    \infrank(p, \Pf)=\sup\{ \alpha+1\mid \exists^\infty p' ( p'<p \text{ and }
    \infrank(p', \Pf)\geq \alpha)\}.
  \end{align*}
  The $\infrank$ of $\Pf$ is then
  \begin{align*}
    \infrank(\Pf)=
    \sup\{\alpha+1\mid \exists^\infty p\in P\quad  
    \infrank(p, \Pf)\geq \alpha\}. 
  \end{align*}
\end{definition}



\begin{lemma}\label{lem:RankAndInfRank}
  \cite{KaLiLo12}
  For $\Pf$  a well-founded partial order,
  we have 
  \begin{equation*}
    \infrank(\Pf) \leq \rank(\Pf)< \omega\cdot (\infrank(\Pf) +1).    
  \end{equation*}
\end{lemma}








In this section, we prove the following bound on the ranks of
$\alpha$-automatic order forests.
\begin{theorem}\label{thm:BoundsOnTreeRanksDet}
  Let   $\alpha$ be some scattered linear order.
  \begin{enumerate}
  \item 
    Every $\alpha$-oracle-automatic order forest $\Ff=(F, \leq)$ such
    that
    \begin{itemize}
    \item $F$ is also the domain of some $\alpha$-oracle-automatic
      scattered linear order, and
    \item    $\FC(\alpha)= 1+\gamma$
    \end{itemize}
    has rank
    strictly below $\omega^{1+\gamma+1}$ and
    $\infrank$ strictly below $\omega^{\gamma+1}$.
  \item 
    \begin{itemize}
    \item 
    If $\FC(\alpha) <\omega$, then 
    every $\alpha$-oracle-automatic order forest has rank
    strictly below $\omega^{ \FC(\alpha)+1}$.    
  \item     
    If $\FC(\alpha) = \omega +c_0$ for some $c_0<\omega$, then 
    every $\alpha$-oracle-automatic order forest has rank
    strictly below $\omega^{\omega \cdot (c_0 + 1)}$.    
  \item 
    If $\FC(\alpha) = \omega \cdot c_1 +c_0$ for $c_0,c_1<\omega$ and
    $c_1\geq 2$, then  every $\alpha$-oracle-automatic order forest has rank
    strictly below $\omega^{\omega^2\cdot (c_1-1) + \omega  \cdot (c_0
      + 1)}$.    
  \item If $\FC(\alpha) \geq \omega^2$, 
    then every $\alpha$-oracle-automatic order forest has rank
    strictly below $\omega^{ \omega \cdot \FC(\alpha)+
      \omega}$.\footnote{
      In particular, 
      if $\FC(\alpha) = 
      \omega^n \cdot c_n +
      \omega^{n-1} \cdot c_{n-1} +
      \dots +
      \omega \cdot c_{1} +
      c_0$ such that $n\geq 2$, $c_1,c_2,\dots, c_n <\omega$, and
      $c_n\neq 0$,
      then every $\alpha$-oracle-automatic order forest has rank
      strictly below $\omega^{\omega^{n+1} \cdot c_n +
        \omega^{n-1+1} \cdot c_{n-1} \dots \omega^2\cdot c_1 + \omega
        \cdot( c_0+1) }$.
    }
  \end{itemize}
  \end{enumerate}  
\end{theorem}
\begin{remark}
  If $\alpha$ is an ordinal or $\FC(\alpha)<\omega$, 
  we show in the next section that  every  $\alpha$-oracle-automatic  
  set $F$ of finite $\alpha$-words allows a scattered linear order.
  Thus, if $\alpha$ satisfies one of these conditions, then the better
  bounds hold.
\end{remark}




\subsection{A Scattered Order of Scattered Words}
\label{sec:OrderingWords}

We first show that scattered orders $\alpha$ of finite rank allow a
scattered order of all finite $\alpha$-words that is
$\alpha$-automatic. Afterwards, 
we show that the analogous result holds in case that $\alpha$ is an
ordinal. 
Our first claim is proved by induction on the $\FC$-rank and the
$\FCstar$-rank of $\alpha$. We prepare our result by defining an
automaton that determines at every cut the left and the right rank of
this cut. Given a cut $c=(C,D)$ without direct predecessor, the left rank is
the minimal rank of the induced suborders of nonempty upwards closed
subsets of $C$. Analogously, the right rank is the minimal rank of the
induced suborders of nonempty downwards closed subsets of $D$. 



\begin{definition} \label{def:AutLimitStages}
  For $\Sigma$ arbitrary, 
  let $\Cc_n=(Q_n, \Sigma, I_n,F_n,\Delta_n)$ be an automaton with state set 
  $Q_n:=\{0, 1, \dots, n\} \times \{0, 1, \dots, n\}$, 
  initial states $I_n=\{0\}\times \{0, 1, \dots, n\}$ and
  final state $F_n=\{0, 1, \dots, n\} \times \{0\}$.
  In order to define its transition relation, we use the following
  notation for $i\leq n$, let
  $\Pc_i$ be defined by
  \begin{align*}    
    \{ S\in 2^{Q_n}\mid 
    \forall j> i\ \forall k\quad (j,k),(k,j) \notin S \text{ and }
    \exists k\leq i\quad
    (i,k)\in S \text{ or } (k,i)\in S\}.
  \end{align*}
  The transition relation of $\Cc_n$ is
  \begin{align*}
    \Delta_n =& \left\{( (i,0),\sigma,(0,j))\mid \sigma\in\Sigma\text{
        and }i,j\in\{0,
      1, \dots, n\} \right\}\\
    &\cup \{( (i,j), X)\mid X\in \Pc_j\}\\
    &\cup \{( X, (i,j))\mid X\in \Pc_i\}
  \end{align*}
\end{definition}

\begin{lemma}
  Let $\alpha$ be some scattered linear order and $w$ an arbitrary
  $\alpha$-word. 
  Interpreting $\Cc_n$ as an $\alpha$-automaton, there is an accepting
  run $r$ of $\Cc_n$ on $w$ if and only if $\FCstar(\alpha)\leq n$.
  In this case, $r$ is the unique accepting run and for every cut 
  $c=(C,D)$ the state at $c$ is
  \begin{itemize}
  \item in $\{0\}\times\{0, 1, \dots, n\}$ if $c$ has a direct predecessor,
  \item in $\{0, 1, \dots, n\}\times \{0\} $ if $c$ has a direct successor,
  \item in $\{k\} \times \{0, 1, \dots, n\}$ (with $k\geq 1$) if
    $c$ has no direct predecessor, and for each cut $c'<c$ there is a cut
    $c''$ such that $c'<c''<c$  and
    $\FC(\alpha{\restriction}_{(c'',c)})=k$, and
  \item in $\{0, 1, \dots, n\}\times \{k\}$ (with $k\geq 1$) if
    $c$ has no direct successor, and for each cut $c'>c$ there is a cut
    $c''$ such that $c'>c''>c$  and
    $\FC(\alpha{\restriction}_{(c,c'')})=k$. 
  \end{itemize}
\end{lemma}
\begin{proof}
  First, let $n \geq \FCstar(\alpha)$. This implies, that for all cuts
  $c''$ and $c$, the suborder induced by $(c'',c)$ has $\FC$-rank at
  most $\FCstar(\alpha)\leq n$. 
  Moreover, if $c$ is a cut without direct predecessor, and if
  $c_1<c_2<c_3<\dots    <c$ is an infinite chain of cuts whose limit is $c$,
  then  $\FC(\alpha{\restriction}_{(c_i,c)})$ stabilises at some
  $i_0$. Thus, the following function $r$ is well-defined. It is a function
  $r: \Cuts(\alpha)\to Q_n$ where for each cut $c=(C,D)$ we have
  $r(C,D)= (i,j)$ such that
  \begin{enumerate}
  \item $i=0$ if $c$ has a direct predecessor or $C=\emptyset$, 
  \item  otherwise, $i= \min\{ \FC( (c',c))\mid c'<c\}$,
  \item $j=0$ if $c$ has a direct successor or $D=\emptyset$, 
  \item  otherwise, $j= \min\{ \FC( (c,c'))\mid c'>c\}$.
  \end{enumerate}
  A straightforward induction on the left and right rank of each cut
  in $\alpha$ shows that $r$ is consistent with the transition
  relation, i.e.,  $r$ is an accepting run of $\Cc_n$ on each
  $\alpha$-word.  
  
  We next show that $r$ is the unique run  of $\Cc_n$ on
  $\alpha$-words.
  Heading for a contradiction assume that $r'$ is another accepting
  run on some $\alpha$-word and that $c=(C,D)$ satisfies
  $r(c) = (i,j) \neq r'(c)=(i',j')$. Without loss of generality (the
  other case is symmetric), we
  may assume that $i\neq i'$ and  $c$ has been chosen such that $i$ is
  minimal with this property. 
  We distinguish the following cases:
  \begin{itemize}
  \item Assume that $i=0$. Since $r'$ is accepting, $c$ cannot be the minimal
    cut. Thus, $c$ has a direct predecessor $c'$. But independent of
    the
    successor transition used between $c'$ and $c$, $r'(c)\in
    \{0\}\times\{0, 1, \dots, n\}$ whence $i=i'=0$ contradicting the
    assumption $i\neq i'$.
  \item Assume that $i\geq 1$. The right limit transition applied by
    $r$ at $c$ 
    shows that there is a cut $c'<c$ such that for all
    $c''\in (c',c)$, $r(c'')\in \{0, 1, \dots, i-1\}^2$. 
    By minimality of $i$, $r$ and $r'$ agree on this interval. 
    But then again the applicable right limit transitions always
    imply that $i'=i$ contradicting $i'\neq i$. 
  \end{itemize}
  
  Finally, we have to show that there are no accepting runs of $\Cc_n$
  on $\alpha$-words if $\FCstar(\alpha)>n$. 
  Assume that $\FCstar(\alpha)>n$. Due to Lemma
  \ref{lem:AllFCstarRankAsSubOrders}, $\alpha$ contains an interval
  $\alpha'$ with $\FCstar(\alpha')=n+1$. We show that there is no
  function $r:\alpha'\to Q_n$ which is consistent with the transition
  relation $\Delta_n$. 
  Up to symmetry, $\alpha'$ contains an upwards closed interval of the
  form  $\sum_\omega \beta_i$  with $\FC(\beta_i)=n$. 
  As shown in the first part, there is an accepting run $r'$ of
  $\Cc_{n+1}$ on this sum. For the maximal cut $c_{\max}$ of $\alpha'$,
  we have $r'(c_{\max})= (n+1,0)$. In fact, one easily sees that the
  previous arguments apply to any (possibly non-accepting run) on
  $\alpha'$ in the sense that any run on $\alpha'$ satisfies
  $r'(c_{\max})\in \{n+1\}\times \{0, 1, \dots, n+1\}$. 
  Since $\Delta_n\subsetneq \Delta_{n+1}$, any run of $\Cc_n$ on
  $\alpha$ is also a run of $\Cc_{n+1}$ that does not use states from
  $\{n+1\}\times\{0, 1, \dots, n+1\}$. But we have seen that any run
  of $\Cc_{n+1}$ on $\alpha'$ would label $c_{\max}$ with such a
  state. Thus, there is no run of $\Cc_n$ on $\alpha'$ whence there
  can neither be a run of $\Cc_n$ on $\alpha$. 
\qed \end{proof}

The automaton $\Cc_n$ will be useful to decompose an order $\alpha$
with $\FCstar(\alpha)=n$ into finitely many pieces
$\alpha=\alpha_1+\alpha_2+\dots+ \alpha_k$ of $\FC$-rank at most $n$. 

\begin{lemma}
  Let $\alpha$ be an order with $\FCstar(\alpha)=n$ and $r$ the
  accepting run of $\Cc_n$ on $\alpha$-words. Let
  $c,d$ be consecutive cuts of maximal rank in the sense that 
  \begin{itemize}
  \item $c$ is minimal or $r(c)=(i,j)$ with
    $\max(i,j)=n$,
  \item $d$ is maximal or $r(d)=(k,l)$ with $\max(k,l)=n$, and
  \item for all $e\in (c,d)$, $r(e)=(x,y)$ we have $\max(x,y)<n$.
  \end{itemize}
  Then the interval $(c,d)$ of $\alpha$ has $\FC$-rank at most $n$. 
\end{lemma}
\begin{remark}
  In particular, this lemma implies that in an order $\alpha$ with
  $\FCstar(\alpha)=n$ there are only finitely many
  cuts of left or right rank $n$.
\end{remark}
\begin{proof}
  By induction on $i$, we  prove that
  for arbitrary cuts $c \leq d$ the following holds.
  If for all cuts $e$ strictly between $c$
  and $d$ we have  $r(e)\in \{0, 1, \dots, i-1\}^2$ then
  $\FC( (c,d))\leq i$. 
  
  For $i=0$, the condition implies that $c=d$ whence
  $\FC( (c,d) )=\FC(\emptyset) = 0$. 
  Now assume that this claim holds for $i-1$ and that
  for all cuts $e\in (c,d)$ we have
  $r(e)\in \{0, 1, \dots, i-1\}^2$. 
  By definition of the limit transitions, we know that
  $r(c)\in \{0, 1, \dots, n\}\times \{0, 1, \dots, i\}$ and that
  $r(d)\in \{0, 1, \dots, i\}\times \{0, 1, \dots, n\}$. 
  From our construction of the accepting run $r$ (compare the previous
  proof), we conclude that there are cuts
  $c<c_1\leq d_1< d$ such that
  $\FC((c,c_1)) \leq i-1$ and
  $\FC((d_1,d))\leq i-1$. 
  Next, we claim that there are only finitely many cuts $c_1 < e <
  d_1$ such that $r(e)\in  M_{i-1}:=
  (\{i-1\}\times \{0, 1, \dots, \{i-1\}) \cup
  (\{0, 1, \dots, \{i-1\}) \times \{i-1\})$.
  Otherwise there would be an infinite ascending or descending chain
  of cuts in $M_{i-1}$ whose limit $e$ would satisfy $c_1\leq e \leq
  d_1$ and $r(e)\notin \{0, 1, \dots, i-1\}^2$ contradicting our
  assumptions on the interval $(c,d)$. 
  Thus, let $c_1=e_1 < e_2 < \dots < e_{n-1} < e_n=d_1$ be a finite
  sequence of cuts such that for all $c_1\leq e \leq d_1$ we have
  $r(e)\in M_{i-1}$ only if there is a $1\leq j \leq n$ with $e=e_j$.
  Thus, $(c,d) = (c,c_1) + \sum_{i=1}^{n-1} (e_i,e_{i+1}) + (d_1,d)$
  is a finite sum of intervals that (by induction hypothesis) have
  $\FC$-rank at most $i-1$. Thus, $\FC((c,d))\leq i$ as desired.
\qed \end{proof}

Let us collect one more fact about $\Cc_{n+1}$. 
Assume that $\alpha$ is an order with
$\FC(\alpha)=\FCstar(\alpha)=n+1$. 
This implies that $\alpha = \sum_{\gamma\in\Gamma} \alpha_\gamma$
where
$\Gamma\in\{\omega, \omega^*, \Z\}$ and $\FC(\alpha_\gamma)\leq n$
where for infinitely many $\gamma\in\Gamma$ we have
$\FC(\alpha_\gamma)=n$. Thus,  $\Cc_n$ has an accepting run on each
$\alpha_\gamma$ that agrees with the run of $\Cc_{n+1}$ on $\alpha$ on
the interval $\alpha_\gamma$. Hence, the run of $\Cc_{n+1}$ assumes
only finitely many often a state from $M_n:=\{n\}\times\{1, 2, \dots,
n\} \cup \{1, 2, \dots, n\} \times n\}$ on each $\alpha_\gamma$. 
The next lemma follows immediately.

\begin{lemma}\label{lem:MaxRankCutsEmbedinZ}
  Let $\alpha$ be an order with
  $\FC(\alpha)=n+1$. Let $r$ be the accepting run of
  $\Cc_{n+1}$ on some $\alpha$-word. 
  The suborder induced by the cuts
  $\{c\mid r(c)\in M_n\}$ form a suborder of $\Z$. 
\end{lemma}

Thus, there is an accepting run of
$\Cc_{n+1}$ on every $\alpha$-word but no run of
$\Cc_n$ on some $\alpha$-word. 



\begin{lemma} \label{lem:alpha-autmatic-words-are-scattered-ordered}
  Suppose that $\alpha$ is a scattered linear order with
  $\FC(\alpha)<\omega$. Then there is an $\alpha$-oracle-automatic
  scattered linear order on the 
  set of finite $\alpha$-words.   
\end{lemma} 

\begin{proof} 
  We define automata $\Ac_n$ (and $\Bc_n$, respectively) for each
  $n<\omega$ which 
  uniformly define 
  $\alpha$-automatic scattered linear orders on the finite
  $\alpha$-words over a fixed alphabet $\Sigma$ for all 
  scattered linear orders $\alpha$ with $\FC(\alpha)\leq n$ (and
  $\FCstar(\alpha)\leq n$,
  respectively).  
  Note that for $\alpha$ with $\FC(\alpha)=0$ there is a finite number
  of $\alpha$-words over 
  $\Sigma$ whence the construction of $\Ac_0$ is trivial.
  
  Suppose that we have constructed $\Ac_n$. We define $\Bc_n$ as follows. If
  $\FCstar(\alpha)\leq n$, 
  the run of the automaton $\Cc_n$ partitions $\alpha$ uniquely into a
  finite sum of intervals $\alpha=\alpha_1+\alpha_2+\dots+ \alpha_m$
  of $\FC$-rank $\leq n$ by taking the states from $\{n\}\times\{0, 1,
  \dots, n\} \cup \{0, 1, \dots, n\} \times\{n\}$ as splitting
  points. 
  Then 
  $\Bc_n$ orders $\alpha$-words lexicographically by comparing the restrictions
  to the intervals $\alpha_i$ via $\Ac_n$. 
  If $\Ac_n$ orders $\alpha_i$-words as some order $L_i$, then 
  $\Bc_n$ orders $\alpha$-words as the scattered sum 
  $\sum_{a_1\in L_1} \sum_{a_2\in L_2} \dots \sum_{a_m\in L_m} 1$ of
  one element orders which clearly is scattered again. 
  
  Suppose that $\FC(\alpha)\leq n+1$. Let $r$ be the accepting run of
  $\Cc_{n+1}$ on every 
  $\alpha$-word. 
  Recall that from Lemma \ref{lem:MaxRankCutsEmbedinZ}, we
  conclude that the cuts of rank $n$ embed into $\Z$, Thus, the cuts
  \begin{align*}
    C:=\{c \mid c \text{ minimal or maximal or } r(c)\in M_n\}
  \end{align*}
  are a suborder of $1+\Z+1$. 
  Given an $\alpha$-word $w$ we define $c(w)$ to be maximal element
  $c\in C$ such that $c<\supp(w)$ and define $d(w)$ to be the minimal
  element $c\in C$ such that $\supp(w)<c$. 
  We define $\Ac_{n+1}$ as
  follows.
  Given finite $\alpha$-words
  $v,w$, let $v\leq w$ if
  \begin{enumerate}
  \item $c(v) < c(w)$ , or
  \item $c(v) = c(w)$ and $d(v) < d(w)$, or
  \item $c(v) = c(w)$, $d(v)=d(w)$ and
    $\Bc_n$ applied to the interval between $c(v)$ and $d(v)$ reports 
    $v<w$. Note that $\FCstar((c(v),d(v))\leq n$ because the accepting
    run of $\Cc_{n+1}$ on $\alpha$ assumes only finitely many states
    of rank $n$ on this subinterval. Thus, also $\Cc_n$ accepts
    $(c(v),d(v))$-words. 
  \end{enumerate}
  This defines an $\alpha$-automatic linear order $(W_\alpha,\preceq)$
  on the set of finite $\alpha$-words $W_\alpha$. Since $\preceq$
  embeds into a $(1+\Z+1)^2$-sum  of scattered linear orders
  (induced by $\Bc_n$), where $(1+\Z+1)^2$ is ordered
  lexicographically, $(W_\alpha,\preceq)$   is scattered.  
\qed \end{proof} 

\begin{lemma}
  Let $\alpha$ be some ordinal. Then there is an $\alpha$-automatic
  well-order of all finite $\alpha$-words over an alphabet $\Sigma$.
\end{lemma}
\begin{proof}
  Fix a linear order $\leq_\Sigma$ on $\Sigma$.
  Let $w,v$ be $\alpha$-words. We set
  $w<v$ if either $\max(\supp(w))<\max(\supp(v))$ or
  $\max(\supp(w)) = \max(\supp(v))$ and
  there is a $\beta<\max(\supp(w))$ such that 
  $w(\beta) <_\Sigma v(\beta)$ and for all $\alpha>\beta'>\beta$,
  $w(\beta')=v(\beta')$. 
  Apparently this order is $\alpha$-automatic. 
  Note that for $\alpha=\omega$ this is a the
  length-backward-lexicographic order (we first compare words with
  respect to size and words of the same size are compared
  lexicographically from the last letter to the first one). 
  In order to show that this defines a well-order, first note that it
  is reflexive, transitive and antisymmetric, i.e., a linear order.
  Heading for a contradiction, assume that there is some ordinal
  $\alpha$ such that the order on $\alpha$-words contains an infinite
  descending chain $w_1 > w_2 > w_3 > \dots$.
  The chain $\alpha_i:=\max(\supp(w_i))$ is a monotone
  decreasing sequence in $\alpha$. Since $\alpha$ is an ordinal, it
  stabilises at some $k\in\N$. We conclude that
  the sequence $v_j:=w_{k+j}$ satisfies
  $\max(\supp(v_{j}))= \alpha_k$ for all $j\in\N$.

  We now iterate the following argument: let $\alpha'<\alpha_k$ be
  maximal such that there are $v_j, v_k$ such that $v_j(\alpha') \neq
  v_k(\alpha')$. Since $\Sigma$ is finite, there is an infinite
  subsequence $v_{i_1} > v_{i_2} > \dots$ such that
  $v_{i_k}$ and $v_{i_j}$ agree at $\alpha'$, i.e.,
  $v_{i_k}(\alpha')=v_{i_j}(\alpha')$. Replace the sequence $v_{k}$ by
  the sequence $v_{i_k}$. Since this is an decreasing chain and above
  $\alpha'$ all $v_{i_k}$ agree, we can repeat this argument with some
  smaller $\alpha''<\alpha'$ which is maximal such that some $v_{i_k}$
  do not agree on $\alpha''$. 
  Since $\alpha$ is an ordinal and since
  $\alpha'>\alpha''>\alpha'''>\dots$, this sequence must be finite. 
  But this process terminates if and only if $v_{i_k} = v_{i_j}$ for
  all $j,k\in\N$. This contradicts the assumption that the $v_{i_j}$
  form a strictly decreasing infinite chain.
\qed \end{proof}





\subsection{Kleene-Brouwer Orders of Trees}
\label{sec:KleeneBrouwer}

Let $\Tf=(T, \sqsubseteq)$ be a tree and let $\Lf=(T, \preceq)$ be a
linear order. Then we can define
the  \emph{Kleene-Brouwer order} (also called Lusin-Sierpi\'nski
order)  $\KB(\Tf, \Lf):=(T, \lessdot)$ given by
$t \lessdot t'$ if either 
$t \sqsubseteq t'$ or there are $t\sqsubseteq s, t'\sqsubseteq s'$
such that  
$\{r\in T\mid s\sqsubset r\} = \{r\in T\mid s'\sqsubset r\}$ and 
$s\prec s'$. This
generalises the order induced by postorder traversal to 
infinitely branching trees where the children of each node are ordered
corresponding to the linear order $\preceq$. 
Since $\alpha$-oracle-automatic structures are closed under
first-order definitions, the following observation is immediate.
\begin{proposition}
  If $\Tf$ is an tree and $\Lf$ a linear order such that both are
  $\alpha$-oracle-automatic, then $\KB(\Tf, \Lf)$ is
  $\alpha$-oracle-automatic. 
\end{proposition}

For the following section, it is important that
$(T, \lessdot)$ is scattered if
$(T, \preceq)$ is a scattered linear order. 

\begin{lemma}
  Let $\Tf=(T, \sqsubseteq)$ be a tree and $\Lf=(T, \preceq)$ a
  scattered linear order, then $\KB(\Tf, \Lf)=(T, \lessdot)$ is
  scattered.
\end{lemma}
\begin{proof}
  The proof is by induction on the rank of $\Tf$. If $\Tf$ has rank
  $1$, it consists only of the root whence $\KB(\Tf, \Lf)$ is the linear
  order of $1$ element which is scattered. 
  Otherwise, let $T_0$ be the set of children of the root and let
  $t_0$ be the root of $\Tf$. 
  $T_0$ induces a scattered suborder $(T_0, \preceq)$ of $\Lf$. 
  Now (abusing notation slightly) 
  $\KB(\Tf, \Lf) = \left(\sum_{t\in (T_0, \preceq)} \KB(\Tf(t), \Lf)\right) +
  t_0$ which is a scattered sum of 
  scattered orders. Proposition 2.17 in \cite{rosenstein82} shows that
  $\KB(\Tf, \Lf)$ is scattered. 
\qed \end{proof}

\subsection{Bounds for Forests on Scattered Orders of Finite Rank}
\label{sec:Treeboundsmall}

In this section, we prove the main theorem in the case that
$\FC(\alpha)$ is finite, $\alpha$ is an ordinal, or in general, the
set of finite $\alpha$-words allows a scattered linear order. In the next
Section we then prove the other cases.

\begin{lemma}\label{lem:rankAndKB}
  Let $\Tf=$ be a nonempty $\alpha$-oracle-automatic order tree with domain
  $T$ and $\Lf$ a scattered $\alpha$-oracle-automatic order with
  domain $T$. 
  If $\FCstar(\KB(\Tf, \Lf)) < \beta$,
  then $\infrank(\Tf)<\beta$. 
\end{lemma}
\begin{proof}
  The proof is by contraposition and induction on $\beta$. 
  \begin{itemize}
  \item If $\beta=0$, there is nothing to show.
  \item Assume that $\infrank(\Tf)=\beta=\beta'+1$ and for each tree
    $\Tf'$ with $\infrank(\Tf')=\beta'$ we have
    $\FCstar(\KB(\Tf', \Lf)) \geq \beta'$. 
    By definition of $\infrank(\Tf)$ there is an infinite antichain
    $d_1, d_2, d_3,\dots$ in $\Tf$ such that the subtree
    $\Tf(d_i)$ rooted at $d_i$ satisfies
    $\infrank(\Tf(d_i))=\beta'$. By induction hypothesis, 
    $\FCstar( \KB(\Tf(d_i), \Lf))\geq \beta'$. 
    Moreover, $\Lf$ orders $\{d_i\mid i\in\N\}$ as order type 
    $\gamma\in\{\omega, \omega^*, \zeta\}$
    Thus, $\KB(\Tf, \Lf)$ contains a suborder of the form
    $\sum_{x\in \gamma} \KB(\Tf(d_x), \Lf))$ with
    $\FCstar(\KB(\Tf(d_x), \Lf))=\beta'$. 
    Due to Lemma \ref{lem:FCstarSumsIncreaseRank}, 
    we conclude that
    \begin{align*}
      \FCstar(\KB(\Tf, \Lf)) \geq 
      \FCstar(\sum_{x\in \gamma} \KB(\Tf(d_x), \Lf))       
      = \beta'+1 = \beta.      
    \end{align*}
  \item Assume that $\infrank(\Tf)=\beta$ is a limit ordinal. 
    By definition for each $\beta'<\beta$ there is $d\in \Tf$ such
    that
    $\infrank(\Tf(d)) \geq \beta'$ whence
    $\FCstar(\KB(\Tf(d), \Lf )) \geq \beta'$ by induction. 
    Thus, $\FCstar(\KB(\Tf, \Lf)) \geq \sup\{\beta' \mid \beta'<\beta\} =
    \beta$. 
  \end{itemize}
\qed \end{proof}

\begin{corollary}
  \label{cor:rankAndKB}
  Let $\Tf$ be a nonempty $\alpha$-automatic order tree. 
  If $\FC(\KB(\Tf, \Lf)) < \beta$,
  then $\infrank(\Tf)<\beta+1$.   
\end{corollary}

Combining this result with our bound on the $\FC$ ranks of
$\alpha$-oracle-automatic we can now prove the first part of 
Theorem \ref{thm:BoundsOnTreeRanksDet}.

\begin{proof}[Proof of Theorem \ref{thm:BoundsOnTreeRanksDet} part (1)] 
  Assume that  $\Tf=(T,\leq)$ is an
  $\alpha$-oracle-automatic 
  order tree  such that
  $\Lf$ is an $\alpha$-oracle-automatic scattered order with domain $T$. 
  Since $\KB(\Tf, \Lf)$ is an 
  $\alpha$-oracle-automatic scattered linear order,
  $\FC(\KB(\Tf, \Lf)) <\omega^{\gamma+1}$ due to Theorem 
  \ref{thm:BoundsonScatteredOrders}. 
  Due to Corollary \ref{cor:rankAndKB}, $\infrank(\Tf)<
  \omega^{\gamma+1}$.  
  By application of Lemma \ref{lem:RankAndInfRank} we finally obtain
  $\rank(\Tf)<\omega^{1+\gamma+1}$. 

  Note that this result easily extends to forests because for each
  $\alpha$-oracle-automatic forest, we can turn it into a
  $\alpha$-oracle-automatic tree by
  adding a new root. This tree has the same $\infrank$ as the forest
  we started with. 
\qed \end{proof}



\subsection{Bounds for Forests on Scattered Orders 
  of Infinite Rank} 
\label{sec:Treeboundlarge}

Since we do not know whether there is an $\alpha$-automatic scattered
linear ordering of all finite $\alpha$-words for all linear orders
$\alpha$  with $\FC(\alpha)\geq \omega$, we have to do a direct analysis of
the sum-of-box decompositions of $\alpha$-automatic forests. 
Fortunately, we can rely on the analogous analysis in the case of
tree-automatic structures from \cite{KaLiLo12}.
The essence of this analysis can be rewritten as the following result.
\begin{theorem} \label{thm:treerank-indecomposable}
  \cite{KaLiLo12}
  If $\Ff$ is a forest that is tamely-colourable
  sum-of-box-augmentation of classes $\Cc_1, \dots, \Cc_k$ such that
  for all 
  structures $\Ff'\in \bigcup_{i=1}^k \Cc_1$ we have  
  $\infrank(\Ff')\neq \omega^\alpha$, 
  then $\infrank(\Ff) \neq \omega^\alpha$. 
\end{theorem}

Using this decomposition result, the second part of
Theorem \ref{thm:BoundsOnTreeRanksDet} is obtained by induction. 


\begin{proof}[Proof of Theorem \ref{thm:BoundsOnTreeRanksDet} part (2)] 
  Because of the first part of this theorem and Lemma 
  \ref{lem:alpha-autmatic-words-are-scattered-ordered}, the claim for
  orders $\alpha$ with $\FC(\alpha)<\omega$ has already been proved. 
  
  We now establish the following claim.
  Assume that $\alpha$ is a scattered linear order of rank
  $\FC(\alpha)=\gamma \geq \omega$.   
  Let $\delta \geq \omega $ be an ordinal such that for all $\alpha'$ with
  $\FC(\alpha')< \gamma$ and all 
  $\alpha'$-oracle-automatic forests $\Ff'$, 
  $\infrank(\Ff')<\omega^\delta$. 
  Then every $\alpha$-oracle-automatic forest $\Ff$ satisfies
  $\infrank(\Ff) < \omega^{\delta + \omega}$.
    
  Heading for a contradiction assume that $\Ff$ is an
  $\alpha$-oracle-automatic forest with 
  \mbox{$\infrank(\Ff)\geq \omega^{\delta + \omega}$.}
  Then there is a parameter automaton $\Ac$ (corresponding to the
  formula $x<y$ and parameters $p_n$ for $n\in\N$ such that
  $\infrank(\Ff_{p_n}) = \omega^{\delta + n}$. 
  Assume that $\Ac$ has $q$ many states and the order automaton of
  $\Ff$ has $q_<$ many states. 
  Now fix $n_0 > 2 \exp(q^2+2q_<^2)$. 
  Due to Theorem \ref{thm:Decomposition}, 
  there are sets
  $\Cc_0, \Cc_1$ of size $\exp(q^2+2q_<^2)$
  such that for each $n\leq n_0$, $\Ff_{p_n}$ is a tamely-colourable
  sum-of-box augmentation of $\Cc_0, \Cc_1$ and 
  some sets  of $\alpha_i$-oracle-automatic structures where
  $\FC(\alpha_i)< \gamma$ for each $i$.
  By choice of $n_0$, there is some $1 \leq m \leq n_0$ such that
  \begin{equation*}
     \infrank(\Af) \neq \omega^{\delta + m}
  \end{equation*}
  for all  structures  $\Af\in \Cc_0\cup \Cc_1$.
  Moreover, by definition of $\delta$ every $\alpha_i$-oracle-automatic
  forest has  $\infrank$ strictly below $\omega^\delta$. 
  Thus, $\Ff_{p_{m}}$ is a tamely-colourable sum-of-box augmentation 
  of classes of structures such that none of these
  structures has $\infrank$  $\omega^{\delta + m}$.
  But this contradicts directly  Theorem
  \ref{thm:treerank-indecomposable} because
  $\infrank(\Ff_{p_{m}} ) = \omega^{\delta+m}$.

  Using Lemma \ref{lem:RankAndInfRank} this claim carries 
  over from $\infrank$ to rank because 
  for
  $\gamma\geq \omega$ some forest has 
  rank strictly below $\omega^\gamma$ if and only if
  it has $\infrank$ strictly below $\omega^\gamma$ (note that
  $\omega\cdot \omega^\gamma = \omega^\gamma$).
  
  The proof of the theorem now follows by a straightforward induction
  on $\FC(\alpha)$ using the claim proved above. 
\qed \end{proof}


\subsection{Optimality of the Bounds on Forests}
\label{sec:HighRanks}


The upper bounds on the ranks of trees stated in the first part of
Theorem \ref{thm:BoundsOnTreeRanksDet} are optimal in the sense that we
can reach all lower ranks as stated in the following theorem. 

\begin{theorem}\label{thm:TreesLowerBounds}
  \begin{enumerate}
  \item For all  $i,c\in\N$ there is an $\omega^i$-automatic tree
    $\Tf_{i,c}$ with $\rank(\Tf_{i,c})=\omega^{i}\cdot c$.
  \item 
    For all ordinals $\gamma\geq\omega$ and all $c\in\N$, 
    there is an
    $\omega^{1+\gamma}$-automatic tree $\Tf_{\gamma,c}$ with
    $\rank(\Tf_{\gamma,c})= \omega^\gamma \cdot c$. 
  \end{enumerate}
\end{theorem}




In order to prove the first part of Theorem
\ref{thm:TreesLowerBounds},  we
want to  construct  for all $i\in\N$ and $c\in\N$ an
$\omega^i$-automatic tree of $\infrank$  $\omega^{i-1}\cdot c$ and
rank $\omega^{i}\cdot c$. 

We define a finite word
$\omega$-automatic tree as follows. Let $T=(\{\varepsilon\} \cup
\{ (n,m) \mid n\leq m \}$ and $\Tf_0=(T, \leq)$ where
\begin{align*}
  &\varepsilon \leq t \text{ for all }t\in T, \\
  &(n,m) \leq (n',m') \text{ if } m=m' \text{ and } n\leq n'.
\end{align*}
$\Tf_0$ is clearly well-founded, finite word $\omega$-automatic, and
satisfies $\infrank(\Tf_0)=1$ and $\rank(\Tf_0)=\omega$. 

Next, we show that for any $i,c\in\N$ and any given $\omega^i$-automatic
tree $\Tf$ there is also an $\omega^i$-automatic tree $\Tf'$ such that
$\infrank(\Tf')=\infrank(\Tf)\cdot c$ and $\rank(\Tf)=\rank(\Tf)\cdot c$. 

\begin{lemma}\label{lem:TreeRankFactorcViaConvolution}
  Let $c\in\N$ and $\Tf$ an  $\alpha$-automatic tree. 
  Then there is
  an $\alpha$-automatic tree $\Tf_c$ such that
  $\infrank(\Tf_c)=\infrank(\Tf)\cdot c$ and $\rank(\Tf)=\rank(\Tf)\cdot c$. 
\end{lemma}
\begin{proof}
  Let $\Tf = (T, \leq)$ and $L\subseteq T$ be the set of leaves of
  $\Tf$ ($L$ is $\alpha$-automatic because it is first-order definable
  if $\Tf$). 
  Set $T_c = \bigcup_{i=0}^{c-1} L^{\otimes i} \otimes T$ where
  $L^{\otimes 1} = L$ and $L^{\otimes {i+1}} = L^{\otimes i} \otimes
  L$. 
  The order of $\Tf_c$ is given by
  \begin{equation*}
    l_1 \otimes l_2 \otimes \dots \otimes l_i \otimes t \leq_c 
    l'_1 \otimes l'_2 \otimes \dots \otimes l'_j \otimes t'    
  \end{equation*}
  iff
  either $i=j, l_1=l'_1, \dots, l_i=l'_i$, and $t\leq t'$ or
  $i<j$ and $t\leq l'_{i+1}$. 
  
  Note that $\Tf_1=\Tf$ and $\Tf_{c+1}$ is obtained from $\Tf_c$ by
  attaching a copy of $\Tf$ to each leaf of $\Tf_c$. Thus, an easy
  induction on $c$ proves the claim. 
\qed \end{proof}

In the case $\alpha=\omega^i$ By replacing the convolution by
composition of $\omega^i$-words, we 
construct a finite word $\omega^{i+1}$-automatic
representation of the forest $\bigsqcup_{c\in\N} \Tf_c$ for any
$\omega^i$-automatic tree $\Tf$. 

\begin{lemma}
  For $\Tf$ a finite word $\omega^i$-automatic tree, the forest
  $\Ff:=\bigsqcup_{c\in\N} \Tf_c$ is finite word $\omega^{i+1}$-automatic.
\end{lemma}
\begin{proof}
  Let $\bot$ be a fresh symbol not occurring in the alphabet $\Sigma$ of 
  the representation of $\Tf$. 
  Let $W_c$ be the set of finite $\omega^{i+1}$-words whose letters
  all occur before position $\omega^{i}\cdot c$ and that have $\bot$
  exactly at position $\omega^{i}\cdot c$. We write $\bot_c$ for the
  word of $W_c$ whose only letter is $\bot$. 
  We identify an element of $\Tf_c$ with a word in $W_c$ as follows.
  Assume that $t_c\in \Tf_c$ has the form 
  $t_c= l_1\otimes \dots \otimes l_k \otimes t$ where each $l_i$ is a
  $\omega^i$-word denoting a
  leaf of $\Tf$ and $t$ is an $\omega^i$-word denoting an arbitrary
  element of $\Tf$.  
  Now let $t_c'$ be the word $l_1 + l_2 + \dots + l_k + t +
  \bot_{c-k-1}$ where $+$ denotes the concatenation of
  $\alpha$-words. Note that $t_c'\in W_c$.
  Since the order of two elements of $\Tf_c$ is defined by
  componentwise comparisons on the convolutions, this results in an
  $\omega^{i+1}$-automatic  presentation of $\Tf_c$ whose domain is a
  subset of $W_c$. 
  It is easy to see that the union of all these representations is
  an $\omega^{i+1}$-automatic forest. 
\qed \end{proof}

Of course, we can add a new  root to $\Ff$ and obtain an
$\omega^{i+1}$-automatic tree $\Tf'$ with 
$\infrank(\Tf')=\sup\{\infrank(\Tf)\cdot c \mid c\in \N\}$ and 
$\rank(\Tf')=\sup\{\rank(\Tf)\cdot c\mid c\in\N\}$. 


Iterated application of this lemma to the tree $\Tf_1$ shows that for
each $i\in\N$ there is an $\omega^i$-automatic tree of rank
$\omega^{i+1}$ (and $\infrank$ $\omega^i$). Application of Lemma
\ref{lem:TreeRankFactorcViaConvolution} then proves the first part
of Theorem \ref{thm:TreesLowerBounds}. 




We now use a variant of the previous construction in order to prove
the second part 
of Theorem \ref{thm:TreesLowerBounds}, i.e., we construct
$\alpha$-automatic trees of high ranks for ordinals $\alpha\geq
\omega^\omega$.  

\begin{definition}
  Let $\alpha$ be an ordinal. Let $D_\alpha$ be the set of finite
  $\alpha$-words $w$ over $\{\diamond,1\}$ such that for all limit
ordinals $\beta<\alpha$ 
  and all $c\in \omega$ the implication
  \begin{align*}
    w(\beta + c)=1 \Rightarrow w(\beta) = w(\beta+1) = 
    \dots = w(\beta+c) = 1
  \end{align*}
  holds. 
  We define a partial order on $D_\alpha$ via the suffix relation: for
  $w_1,w_2\in D_\alpha$ let
  $w_1 \suffix{\alpha} w_2$ if and only if
  for $\beta\leq \alpha$ maximal such that for all $0\leq \gamma <
  \beta \quad w_2(\gamma)=\diamond$ we have that
  $\forall \beta \leq \delta <\alpha \quad w_1(\delta)=w_2(\delta)$,
  i.e., the domain of $w_2$ is an upwards closed  subset of the domain
  of $w_1$ and  both agree on the domain of $w_2$. 
\end{definition}

Note that $\Tc_\alpha:=(D_\alpha, \suffix{\alpha})$ is
$\alpha$-automatic. 

\begin{lemma}
  $\Tc_\alpha:=(D_\alpha, \suffix{\alpha})$ is a tree. 
\end{lemma}
\begin{proof}
  Since $D_\alpha$ contains finite $\alpha$-words $w$ there are only
  finitely many positions $\beta<\gamma$ with $w(\beta)=1$. Thus,
  there are also only finitely many 
  suffixes of $w$ that are undefined up to some position in $\supp(w)$. 
  This implies that all
  ascending chains are finite. 
  Moreover, the suffix relation is a linear order when restricted to
  the suffixes of a fixed word $w$. 
\qed \end{proof}


The following lemma combined with 
Lemma \ref{lem:TreeRankFactorcViaConvolution} proves the second part
of Theorem \ref{thm:TreesLowerBounds}. 

\begin{lemma}
  For all ordinals $\alpha, \alpha'$ such that $\alpha=\omega\cdot
  \alpha' \geq \omega$,
  $\rank(\Tc_\alpha) =\alpha'$. 
\end{lemma}
\begin{proof}
  The proof is by induction on $\alpha'$. 
  For $\alpha=\omega \cdot 1 = \omega$ note that $D_\alpha$ consists
  of all words $1^m\diamond^\omega$, $m\in\N$ where the word
  $\diamond^\omega$ is suffix 
  of all other elements. Moreover, these others are pairwise
  incomparable. Thus, $\Tc_\omega$ is the infinite tree of depth $1$
  which has rank $1$ as desired. 
  We now proceed by induction. 
  \begin{enumerate}
  \item Assume that $\alpha'$ is a successor ordinal, i.e., there is
    some $\beta'$ such that $\alpha=\omega\cdot \alpha' = \omega \cdot
    \beta' + \omega$.
    Note that the words directly below $\diamond^\alpha$ are those of the
    form $w=\diamond^\gamma1^m\diamond^\delta$ such that
    $\gamma+\delta=\alpha$ and 
    $\gamma$ is some limit ordinal and $m < \omega$. 
    Fix such a word and note that 
    $D_\alpha\cap \{w'\mid w'\suffix{\alpha} w\}$ induces a suborder
    isomorphic to $(D_\gamma, \suffix{\gamma})$ which by induction
    hypothesis has rank $\gamma'$ for $\gamma'$ such that
    $\gamma=\omega\cdot \gamma'$. 
    Thus, the suborders of maximal rank $\beta'$ are induced by the
    elements $w_m= \diamond^{\omega\cdot \beta'}1^m\diamond^\omega$ for each
    $m < \omega$. Since these are infinitely many nodes of $\infrank$
    $\beta'$, the rank of $\Tc_\alpha$ is $\beta'+1=\alpha'$.
  \item 
    Assume that $\alpha'$ is a limit ordinal and
    $(\beta_i)_{i\in\omega}$ converges to $\alpha'$ and
    $\beta_i<\alpha$ for each $i\in\omega$. 
    Then each $w^m_i:=\diamond^{\beta_i}1^m\diamond^\alpha$ for $m,i\in\omega$ is
    directly below $\diamond^\alpha$ 
    and induces a suborder isomorphic to
    $(D_{\beta_i}, \suffix{\beta_i})$ of $\infrank$ $\beta_i$. 
    Thus, $\infrank(\Tc_\alpha)\geq \alpha'$. 
    But as in the previous case we see that all proper suborders have
    $\infrank<\alpha$ whence $\infrank(\Tc_\alpha)\leq \alpha'$. 
    Thus, its $\infrank$ is exactly $\alpha'$. 
  \end{enumerate}
\qed \end{proof}





\section{ Finite-Rank-Scattered-Automatic Ordinals }
\label{sec:OrdinalsOverFiniteRankOrders}

In this section we prove that for every scattered linear $\Lf$
order such that $\FC(\Lf)=\FCstar(\Lf)= n<\omega$, the
$\Lf$-oracle-automatic ordinals 
are exactly those below $\omega^{\omega^{n+1}}$. 
For this purpose, it suffices to show that
$\omega^{\omega^{n}}$ is $\Lf$-oracle-automatic. Since
$\Lf$-oracle-automatic structures are closed under finite
(lexicographically ordered) products, it
follows that for each $k$ the ordinal
$(\omega^{\omega^{n}})^k = \omega^{\omega^{n} \cdot k}$ is
$\Lf$-oracle-automatic. Since the $\Lf$-oracle-automatic ordinals are
closed under definable substructures we conclude that all ordinals below
$\omega^{\omega^{n+1}}$ are $\Lf$-oracle-automatic.

\begin{theorem}
  Let $\Lf$ be a scattered linear order with
  $\FC(\Lf)=\FCstar(\Lf)=1+n<\omega$.  
  The ordinal $\omega^{\omega^{n}}$ is finite word $\Lf$-oracle-automatic.
\end{theorem}
\begin{proof}
  We inductively prove the following claim:
  For each $n$ there is are finite automata $\Ac_n$ and $\Bc_n$ 
  such that for
  every scattered linear order $\Lf$ with
  $\FC(\Lf)=\FCstar(\Lf)=1+n$ there is an $\Lf$-oracle $o_\Lf$ 
  such that $\omega^{\omega^{n}}$ is $\Lf$-$o_\Lf$-automatic 
  where $\Ac_n$ recognises the domain and $\Bc_n$ the order $<$ in
  this representation. Moreover the empty $\Lf$-word represents $0$).
  
  In the base $n=0$, we distinguish two cases:
  \begin{enumerate}
  \item $\Lf=\omega$ or $\Lf=\Z$: Let $o_\Lf:\Lf\to\{\diamond,1\}$ be
    an oracle such that $\supp(o_\Lf)$ is isomorphic to $\omega$. 
    Let $\Ac_0$ accept all $\Lf$-words $w$ such that
    $\supp(w)\subseteq \supp(o_\Lf)$ and $\lvert \supp(w)\rvert = 1$. 
    The order is given by $w<v$ iff $\supp(w)$ is to the left of
    $\supp(v)$.
  \item $\Lf=\omega^*$: Let $o_\Lf:\omega^*\to \{\diamond,1\}$ be the
    constant $1$ oracle. 
    Again, the domain recognised by $\Ac_0$ consists of all
    $\Lf$-words $w$ such that 
    $\supp(w)\subseteq \supp(o_\Lf)$ and $\lvert \supp(w)\rvert = 1$. 
    The order is given by $w<v$ iff $\supp(w)$ is to the right of
    $\supp(v)$.
  \end{enumerate}
  There is an  automaton $\Bc_1$ recognising the order independent of
  the shape of $\Lf$. If $\Bc_1$ applies a right limit transition it
  guesses whether $\supp(o_\Lf)$ is defined arbitrarily close to the
  minimal cut. This guess can be checked at the successor
  transitions. Depending on its guess, it recognises the correct order
  according to the case distinction. Since both orders are automatic,
  this combined order is also automatic. 

  For the induction step assume that the claim was proved for all $n'<n$. 
  Let $\Lf$ be some scattered linear order with
  $\FC(\Lf)=\FCstar(\Lf)=1+n$. 
  Recall the automaton $\Cc_{n+1}$ from definition
  \ref{def:AutLimitStages} which determines the left and right order
  of each cut of $\Lf$. 
  Using those cuts where $\Cc_n$ is in a state from 
  $M_{n}=\{n\}\times \{0,1, \dots, n\} \cup 
  \{0, 1, \dots, n\} \times \{n\}$, we obtain a 
  decomposition 
  $\Lf=\sum_{i\in\Z} \Lf_i$ such that $\FC(\Lf_i)=n$ and
  there is an infinite ascending (or descending) sequence
  \begin{align}\label{align:seqOrdinalOrders}
    i_0 < i_1 < i_2 < \dots\text{ such that }\FC(\Lf_i)=n \text{
      and } \forall j\geq 1\quad i_j-{i_{j-1}}\geq 2.
  \end{align}  
  By this we mean that $\Cc_n$ upon reading any $\Lf$-word is not in a
  state from $M_{n}$ on any cut strictly in $\Lf_i$ but it is in one of the
  states from $M_{n}$ at the last cut before and the first cut after
  $\Lf_i$. 
  
  We now describe the case of an ascending chain, but the descending case
  is analogous. 
  Let $o_\Lf$ be the oracle defined by 
  $o_\Lf(x)=(1,o_{\Lf_{i_j}}(x))$ if $x\in \Lf_{i_j}$ 
  and $o(x)=\diamond$ if for all $j\in\N$ we have 
  $x\notin \Lf_{i_j}$.
  The domain of our presentation of $\omega^{\omega^n}$ consists of
  those finite $\Lf$-words $w$ such that 
  $\supp(w)\subseteq \bigcup_{j\in\N} \Lf_{i_j}$ and for each $j$ 
  $\Ac_{n-1}$ accepts $w$ restricted to $\Lf_{i_j}$. 
  This set is recognised by an $\Lf$-$o_\Lf$-automaton $\Ac_n$ as
  follows. $\Ac_n$ simulates $\Cc_n$. At the initial state and
  whenever $\Cc_n$ is in a state from $M_{n}$, it guesses whether
  the next part of $\Lf$ is one of the $\Lf_{i_j}$ where $o_\Lf$ is
  defined. In this case, it starts a simulation of $\Ac_{n-1}$. This
  simulation is stopped when $\Cc_n$ is again in a state from
  $M_{n}$. If it starts a simulation of $\Ac_{n-1}$ and $o_\Lf$
  turns out to be undefined on this part, then the run is
  aborted. Analogously, the run is aborted if we did not start a
  simulation of $\Ac_{n-1}$ and reach a position in $\supp(o_{\Lf})$. 
  
  We identify each word $w$ accepted by $\Ac$ with a sequence
  $(\alpha_j)_{j\in \omega}$ of ordinals in $\omega^{\omega^{n-1}}$ such that
  all but finitely many $\alpha_j$ are $0$ and 
  $\alpha_j$ is the ordinal represented by the restriction of $w$ to
  the $\Lf_{i_j}$ (with respect to the order induced by the order
  automaton $\Bc_{n-1}$). Of course there is an automaton $\Bc'_n$ that
  orders the 
  sequences $(\alpha_j)_{j\in \omega}$ backwards lexicographically, i.e., 
  $(\alpha_j)_{j\in \omega} < (\beta_j)_{j\in\omega}$ if and only if there is
  $j_0\in \N$ such that $\alpha_j=\beta_j$ for all $j> j_0$ and
  $\alpha_{j_0} < \beta_{j_0}$. This order is $\Lf$-$o_\Lf$-automatic
  (just apply order automaton $\Bc_{n-1}$ on the part corresponding to
  $\Lf_{i_j}$ indicated by the oracle and remember the last outcome
  different from '{$=$}'). 
  This gives a presentation of 
  $\sum_{i\in\omega} (\omega^{\omega^{n-1}})^i = 
  \sum_{i\in\omega} (\omega^{\omega^{n-1} \cdot i})  =
  \omega^{\omega^n}$.
  Note that the definition of the oracle $o_\Lf$ depends on $\Lf$ but
  the automata do not depend on $\Lf$. We only need a a slightly different
  order in the case of a descending sequence instead of the
  ascending sequence in  \eqref{align:seqOrdinalOrders}. In the case
  of a descending sequence the order automaton uses lexicographic
  ordering instead of backwards lexicographic order because the domain
  of   the presentation can be identified with
  $(\alpha_j)_{j\in\omega^*}$. 
  Of course, we can define an automaton $\Bc_n$ that guesses (and
  verifies) whether
  $\supp(o_\Lf)$ is cofinal and depending on this guess, simulates
  $\Bc'_n$ or the variant $\Bc''_n$ performing lexicographic
  ordering (since $o_\Lf$ is either coinitial or cofinal, 
  the correctness of this guess can be checked immediately in the
  transitions leaving the initial states).
\qed \end{proof}

\begin{problem}
  Can one lift the previous theorem to orders of transfinite rank?
\end{problem}








\section{The countable atomless Boolean algebra is not ordinal automatic}\label{sec: Boolean algebra}




If $\eta$ is an ordinal, there is an apparent bijection between
$\Cuts(\eta)$ and the ordinal $\eta+1=\{\alpha\mid \alpha\leq
\eta\}$ which we will use to identify cuts. 
Let $\Cuts^-(\eta)=\Cuts(\eta)\setminus \{(\eta,\emptyset)\}$. 
We call $w:\eta \to \{\diamond\}$ the \emph{empty input}. 
If $r\colon \Cuts^-(\eta)\rightarrow \mathcal{S}$ is a run of $\mathcal{A}$
with $\gamma\leq\eta$ and $\gamma<\eta$ is a limit ordinal, let as above
$\lim_{\gamma^-} r$ 
denote the set of states appearing unboundedly
often before $\gamma$. 

\begin{lemma}\label{lemma: pumping for ordinal automata} (Pumping)
  Let
  $\mathcal{A}$ be a non-deterministic ordinal automaton with state
  set $S$, $m\in\N$, and $\gamma$ some ordinal
  with $\gamma\neq 0$. 
  Suppose $S_{\lim}\subseteq S^+\subseteq S$ and $s\in S^+$ with 
  $|S_{lim}|\leq m$. 

  If there is a run 
  \begin{align*}
    r\colon \Cuts(\omega^{m})\rightarrow S^+    
  \end{align*}
  on empty input with
  $r(0)=s$, 
  $\lim_{\omega^{m-}} r= S_{\mathsf{lim}}$, and
  $r(\Cuts(\omega^{m}))=S^+$, 
  then 
  there is a run 
  \begin{align*}
    \bar r\colon \Cuts(\omega^{m}\gamma)\rightarrow
    S^+    
  \end{align*}
  on empty input with
  $\bar r(0)=s$, 
  $\lim_{\omega^{m}\gamma^-} \bar r= S_{\mathsf{lim}}$, and
  $\bar r(\Cuts(\omega^{m}\gamma))=S^+$. 
\end{lemma} 

\begin{proof} 
  The proof is by induction on $m$ and $\lvert S_{lim}\rvert$. 
  \begin{itemize}
  \item First 
    suppose that $S_{lim}=S^+$. Then
    $r(\omega^{m})=r(\alpha_0)$ for 
    some $\alpha_0<\omega^{m}$. Let
    $\bar{r}(\alpha)=r(\alpha)$ and 
    $\bar{r}(\omega^m\beta+\alpha)=r(\alpha_0+\alpha)$ for
    $\alpha<\omega^m$ and $1\leq \beta<\gamma$. Let
    $\bar{r}(\omega^m\gamma)=r(\omega^m)$. 
  \item 
    Now suppose that 
    $S_{lim}\subsetneq S^+$. 
    Choose
    $n_0$ with
    $r([\omega^{m-1}n_0,
    \omega^{m}))\subseteq S_{lim}$.   
    \begin{itemize} 
    \item If there is $n\geq n_0$ with
      $r([\omega^{m-1}n,\omega^{m-1}(n+1)))=S_{lim}$,  
    choose $\beta_0\in [\omega^{m-1}n,\omega^{m-1}(n+1)$ with
    $r(\beta_0)=r(\omega^{m-1}(n+1))$.  
    Let $\bar{r}(\alpha)=r(\alpha)$ for $\alpha\leq\omega^{m-1}(n+1)$, 
    let $\bar{r}(\omega^{m-1}\beta+\alpha)=r(\beta_0+\alpha)$ for
    $\alpha<\omega^{m-1}$ and $\omega \beta<\gamma$, and let
    $\bar{r}(\omega^m\gamma)=r(\omega^m)$.  
    \item If there is no such $n$, find $n_0=\beta_0<\beta_1<...$ with
      $\sup_{i\in\omega}\omega^{m-1}\beta_i=\omega^m\gamma$.  
    Let $\bar{r}(\alpha)=r(\alpha)$ for $\alpha\leq\omega^{m-1} n_0$. 
    We can pump $r\upharpoonright [\omega^{m-1}
    n,\omega^{m-1}(n+1)]$ to a run  
    $\bar{r}\colon [\omega^{m-1}\beta_n, \omega^{m-1}\beta_{n+1}]
    \rightarrow S^+$ for $n\geq n_0$ by the induction hypothesis for
    smaller $S_{lim}$.   
    \end{itemize} 
    \end{itemize}
\qed \end{proof} 





\begin{lemma}\label{lemma: Shrinking for ordinal automata} (Shrinking)
  Let
  $\mathcal{A}$ be a non-deterministic ordinal automaton with state
  set $S$, $m\in\N$, and $\gamma$ some ordinal
  with $\gamma\neq 0$. 
  Suppose $S_{\lim}\subseteq S^-\subseteq S$ and $s\in S^-$ with
  $|S^-|\leq m$.  
  If there is a run 
  \begin{align*}
    r\colon \Cuts^-(\omega^{m}\gamma)\rightarrow  S^-    
  \end{align*}
  on empty input with
  $r(0)=s$, 
  $\lim_{\omega^{m}\gamma^-} r= S_{\mathsf{lim}}$, and 
  $r(\Cuts^-(\omega^{m}\gamma))=S^-$, 
  then 
  there is a run 
  \begin{align*}
    \bar r \colon \Cuts^-(\omega^{m})\rightarrow S^-     
  \end{align*}
  on empty input with
  $\bar r(0)=s$, 
  $\lim_{(\omega^{m})^-} \bar r= S_{\mathsf{lim}}$, and 
  $\bar r(\Cuts^-(\omega^{m}))=S^-$. 
\end{lemma} 

\begin{proof} 
  The proof is by induction on $m$, $\gamma$, and the size of $S^-$. 
  The claim is obvious for $m= 1$ or $\gamma=1$. Thus, we assume that
  $\gamma\geq 2$ and $m \geq 2$. 
  
  \begin{itemize}
  \item First suppose that $S_{\mathsf{lim}}=S^-$  and that there
    is some $\beta<\gamma$ with $\lim_{(\omega^m\beta)^-} r = S^-$. 
    Then we can shrink the run $r\upharpoonright \omega^m\beta$ to a
    run $\bar{r}\colon \omega^m\rightarrow S^-$ by the induction
    hypothesis for $\beta$.  
  \item 
    Next suppose that $S_{\mathsf{lim}}=S^-$ and that for
      each $\beta<\gamma$, there is an $s\in S^-$ such that 
      $s\notin \lim_{(\omega^m\beta)^-} r$.
      There are the following subcases:
      \begin{itemize}
      \item First suppose that $\gamma=\bar{\gamma}+1$. Choose $\beta_0\in [\omega^m\bar{\gamma}, \omega^m \gamma))$ with $r(\beta_0)=r(0)$. 
      Let $\bar{r}(\alpha)=r(\beta_0+\alpha)$ for $\alpha<\omega^m$. 
      \item Suppose that  $\gamma=\omega$.
        By assumption, for each $i$, there is some $\alpha_i$ with
        $\omega^m i \leq \alpha_i < \omega^m (i+1)$ and a state
        $s_i\in S^-$ such  that  $s_i\neq r(\beta)$ for all
        $\alpha_i \leq \beta < \omega^m(i+1)$. Thus, we can apply the
        induction  hypothesis for smaller $S^-$ to each
        $r{\restriction}[\alpha_i, \omega^m(i+1))$ 
        and shrink it to a run of size $\omega^{m-1}$. 
        Note that the length of $r{\restriction}[\omega^m i,
        \alpha_i]$ is also bounded by some $\omega^{m-1}\cdot k_i$. 
        Thus, composition of these runs yields the desired run of
        length $\omega^m$. 
      \item Finally, suppose that $\gamma>\omega$ is a limit ordinal
        and that 
        $\gamma_1<\gamma_2<\dots <\gamma$ are ordinals such that 
        $\lim \gamma_i=\gamma$.   
        By induction hypothesis for smaller $\gamma$, we can 
        shrink each run 
        $r{\restriction}[\omega^m\gamma_i, \omega^m\gamma_{i+1})$ to a
        run of length $\omega^m$ such that 
        each state of $S^-$ appears in one of these runs. 
        Composition of the resulting runs reduces this case to the
        previous case. 
      \end{itemize}
      
    \item Finally,
      suppose that $S_{\mathsf{lim}}\subsetneq S^-$. Let 
      $\alpha_0$ denote the least $\alpha<\omega^m\gamma$ such that
      only states $s\in S_{\mathsf{lim}}$ appear in
      $[\alpha,\omega^m\gamma)$. 
      There are two subcases:
      \begin{itemize}
      \item First suppose that $\alpha_0<\omega^m\beta$ for some
        $\beta<\gamma$. 
        Note that $[\alpha_0,\omega^m\beta)$ and
        $[\alpha_0,\omega^m\gamma)$ are of the form 
        $\omega^{m}\cdot \delta$ with $\delta\leq\gamma$. 
        Since the image of 
        $r\upharpoonright [\alpha_0,\omega^m\gamma)$ is contained in
        $S_{\mathsf{lim}}\subsetneq S^-$, 
        we can shrink 
        $r\upharpoonright [\alpha_0,\omega^m\gamma)$ to a run
        $\bar{r}\upharpoonright 
        [\alpha_0,\omega^{m}\beta)$ by the induction
        hypothesis for smaller $S^-$. 
        Since $\beta<\gamma$ we conclude by  application of the
        induction hypothesis to this shorter run. 
      \item 
        Second suppose that  $\alpha_0 \geq \omega^m\beta$ for all
        $\beta<\gamma$. We conclude immediately that 
        $\gamma$ is a successor, i.e., $\gamma=\bar{\gamma}+1$ and 
        $\alpha_0\geq  \omega^m \bar{\gamma}$. 
        Now we distinguish the following cases.
        \begin{enumerate}
        \item Assume that $\bar \gamma=1$ and  that 
          $r(\omega^m) \in \lim_{(\omega^m)^-} r$. Then there is a
          $\beta <\omega^m$ such that $r(\beta)=r(\omega^m)$ and for
          each state $s\in S^-$ such that $s$ occurs in $r$ strictly before
          $\omega^m$  also occurs before $\beta$. 
          Then the composition of $r{\restriction}[0, \beta)$ with
          $r{\restriction}[\omega^m, \omega^m\gamma]$ yields the
          desired run. 
        \item Assume that $\bar\gamma=1$ and that
          $r(\omega^m) \notin \lim_{(\omega^m)^-} r$. Thus, there is
          some $\beta<\omega^m$ such that 
          $r([\beta, \omega^m))\subseteq 
          S^- \setminus \{r(\omega^m)\}$.
          Thus, we can apply the induction hypothesis for smaller $m$
          and $S^-$ shrinking $r{\restriction}[\beta, \omega^m)$ 
          to a run $\hat r$ on domain $[\beta, \beta+\omega^{m-1})$ with 
          $\hat r([\beta, \beta+\omega^{m-1})) = r([\beta, \omega^m))$
          and
          $\lim_{(\beta+\omega^{m-1})^-} \hat r = \lim_{(\omega^m)^-}
          r$.
          Since $\beta<\omega^{m-1}\cdot k$ for some $k\in\N$, 
          Composition of $r{\restriction}[0, \beta)$ with $\hat r$ and
          $r{\restriction}[\omega^m, \omega^m\gamma)$ yields the
          desired run $\bar r$ of length $\omega^m$.
        \item 
          If $\bar\gamma>1$, we  apply the induction hypothesis (for
          smaller $\gamma$) to 
          $r{\restriction}[0, \omega^m\bar \gamma)$ and shrink this
          run to a run $\bar r$ of length $\omega^m$. The composition of
          $\bar r$ and  $r{\restriction}[\omega^m\bar \gamma,
          \omega^m\gamma)$ is a run of length $\omega^m\cdot 2$ and we
          can apply the induction hypothesis for smaller $\gamma$.
        \end{enumerate} 
      \end{itemize}
    \end{itemize}
\qed \end{proof} 



We directly obtain the following corollary.
\begin{corollary} 
  Let $\gamma\geq 1$ be an ordinal and let
  $\Ac_\gamma=\Ac_1=(S, \Sigma, I,   F, \Delta)$ be an
  automaton (where we interpret $\Ac_i$ as  $\omega^mi$-automaton). 
  For all $s_0,s_1\in S$, 
  \begin{align*}
    s_0 \run{\diamond^{\omega^m}}{\Ac_1} s_1 \Longleftrightarrow 
    s_0 \run{\diamond^{\omega^m\gamma}}{\Ac_\gamma} s_1       
  \end{align*}
  where $\diamond^\alpha$ denotes the empty input of length $\alpha$. 
\end{corollary} 


A formula is $\Sigma_0$ if it is quantifier-free. A formula is $\Pi_i$
if it is logically equivalent to the negation of a $\Sigma_i$-formula.
Formulas of the form $\exists x_0...\exists
x_n\varphi(x_0,...,x_n,y_0,...,y_k)$ for some $\Pi_i$-formula
$\varphi$ are $\Sigma_{i+1}$.

\begin{lemma}\label{lemma: elementary substructure} 
Let $L_0, L_1, \dots, L_k$ be linear orders and let
$\delta_1, \delta_2, \dots, \delta_k, \eta_1, \eta_2, \dots, \eta_k$
be ordinals all strictly greater than $0$. 
Let $\Ac, \Ac_{R_1}, \dots, \Ac_{R_n}$ be
automata such that $m\in\N$ is a bound on the number of states of any
of these. Let $n_0\in\N$ be some number. 
Setting $K^j_i:=\omega^{m+n_0}\cdot j_i$ for $j\in\{\delta,\eta\}$
define the maps 
\begin{align*}
  f_\delta: \prod_{i=0}^k L_i &\to \delta:= 
  L_0+\sum_{i=1}^k (K^\delta_i+ L_i),\\
  (w_1, \dots, w_k) &\mapsto w_1 + \diamond^{\omega^{m+i}\cdot \delta_1}
  + w_2 + \dots + \diamond^{\omega^{m+i}\cdot \delta_k} + w_k, \text{ and}\\
  f_\eta: \prod_{i=0}^k L_i &\to \eta:=
  L_0+\sum_{i=1}^k (K^\eta_i+ L_i), \\
  (w_1, \dots, w_k) &\mapsto w_1 + \diamond^{\omega^{m+i}\cdot \eta_1}
  + w_2 + \dots + \diamond^{\omega^{m+i}\cdot \eta_k} + w_k.  
\end{align*}
Let $M_i$ be the finite word $i$-automatic structure induced by 
$\Ac, \Ac_1, \dots, \Ac_n$  for $i\in\{\delta, \eta\}$. 
For every $\Sigma_i\cup\Pi_{n_0}$-formula $\varphi(\vec{x})$ and all
$\vec{w}=(\vec{w_0}, \dots, \vec{w_k})\in (\prod_{i=0}^k
W_i)^{<\omega}$ (where $W_i$ denotes the set of finite $L_i$-words), 
$M_\delta\models \varphi(f_\delta(\vec{w}))$ if and only if
$M_\eta \models \varphi(f_\eta(\vec{w}))$. 
\end{lemma}

\begin{proof} 
  The claim for $n_0=0$ follows from the Pumping and Shrinking
  Lemmas because we can translate any run on $\diamond^{\omega^m\cdot
    \gamma}$ into a run on $\diamond^{\omega^m\cdot \gamma'}$ with
  same initial and final state for all ordinals $\gamma, \gamma'\geq
  1$. 
  
  For the inductive step, assume that the claim holds for all
  $n'<n_0\in\N$. 
  
  Due to symmetry of the claim and since every $\Pi_{n_0}$-formula is
  the negation of a $\Sigma_{n_0}$-formula it suffices to prove that
  $M_\eta \models \varphi(f_\eta(\vec{w}))$ if
  $M_\delta\models \varphi(f_\delta(\vec{w}))$ for a $\Sigma_{n_0}$
  formula $\varphi$. 


  Let  $\varphi$ be some $\Pi_{{n_0}-1}$-formula and 
  $\vec{v}=f^\delta(\vec{w})$ for some $\vec{w}_i
  \in  (\prod_{i=0}^k L_i)^{<\omega}$ such that 
  $N\vDash \exists \vec{x} \ 
  \varphi(\vec{x}, \vec{v})$. Choose  
  $\vec{t}\in {M_\delta}^{<\omega}$ with $M_\delta \vDash \varphi(t,\vec{v})$.
  
  Since $\vec{t}$ has finite support, for each $1\leq i \leq k$, 
  $\supp(\vec{t})\cap K^\delta_i$ induces a decomposition
  $K^\delta_i= L^i_0+ \sum_{j=1}^m (\bar K^\delta_j+ L^i_j)$ such that
  \begin{itemize}
  \item $\bar K^\delta_j = \omega^{n_0-1}\cdot \kappa$ for some ordinal
    $\kappa\geq 1$,
  \item $L^i_j = \omega^{n_0-1}$, and
  \item   $\supp(\vec{t})\cap  K^\delta_i \subseteq \bigcup_{j=1}^m L^i_j$, 
  \end{itemize}
  Fix ordinals $\bar K^\eta_j$ such that
  $K^\eta_i= L^i_0+ \sum_{j=1}^m (\bar K^\eta_j+ L^i_j)$ (these exist
  because $K^\eta_i = \omega^{m+{n_0}-1} \cdot (\omega\cdot \kappa)$
  for some ordinal $\kappa\geq 1$).
  
  Application of the inductive hypothesis to
  $\varphi$ and the functions
  \begin{align*}
  &g^\delta: L_0\times \prod_{i=1}^k (\prod_{j=1}^m L^i_j \times L_i) \to \delta,
  \text{ and }\\
  &g^\eta: L_0\times \prod_{i=1}^k (\prod_{j=1}^m L^i_j \times L_i) \to \eta
  \end{align*}
  defined in the apparent way
  shows
  that 
  there are words $\vec{w_1}, \vec{w_2}$ such that
  $g^\delta(\vec{w_1})= \vec{v}, 
  g^\delta(\vec{w_2})= \vec{t}$, and
  \begin{align*}
    M_\delta\models \varphi( g^\delta(\vec{w_1}), g^\delta(\vec{w_2}))
    \text{  if and only if }
    M_\eta\models \varphi( g^\eta(\vec{w_1}), g^\eta(\vec{w_2})).
  \end{align*}
  By definition, one easily sees that
  $g^\eta(\vec{w_1}) = f^\eta(\vec{w}) =
  \vec{v}$. Thus, 
  \begin{align*}
    M_\eta \models \exists \vec{x} \ 
    \varphi(\vec{x}, f^\eta(\vec{w})).
  \end{align*}
\qed 
\end{proof}



%Note that any $\delta$-automatic structure has an $\omega^m\gamma$-automatic presentation for the least $\gamma$ with $\delta\leq\omega^m\gamma$. 


\begin{definition} 
  For any ordinal $\alpha$, let $\bar{\alpha}$ be the  ordinal of the
  form
  $\bar{\alpha}=\omega^{m+1}\beta$ for some ordinal $\beta$ such
  that $\alpha=\bar{\alpha}+\omega^m n_m+\omega^{m-1} n_{m-1}+...+n_0$ and
\begin{enumerate} 
\item 
\begin{enumerate}[a.] 
\item Let $U_m(\alpha)$ denote the set of ordinals $\gamma=\bar{\alpha}+\omega^m l_m+\omega^{m-1} l_{m-1}+...+l_0$ such that either 
\begin{itemize}
\item $\gamma=\alpha$ or 
\item $l_k\leq n_k+m$ and  $l_i\leq m$ for all $i<k$, 
\end{itemize} 
where $k$ is maximal with $l_k\neq n_k$. 
\item Let $U_m(X)=\bigcup_{\gamma\in X\cup\{0\}}U_m(\gamma)$. 
\item Let $U_m(X,\delta)=U_m(X\cup\{\delta\})\cap \delta$.  
\end{enumerate} 
\item 
\begin{enumerate}[a.] 
\item Let $c_m(\alpha)=\max_{i\leq m} n_i$. 
\item Let $c_m(X)=\max_{\gamma\in X}c_m(\gamma)$. 
\end{enumerate} 
\item Let $d_m(X)=|\{\bar{\gamma}\mid \gamma\in X\cup\{0\}\}|$. 
\end{enumerate} 
\end{definition} 

Let $U_m^1(X)=U_m(X)$ and $U_m^{i+1}(X)=U_m(U_m^i(X))$ for $i\in\N$, 
and similarly let $U_m^1(X,\delta)=U_m(X,\delta)$ and $U_m^{i+1}(X,\delta)=U_m(U_m^i(X,\delta),\delta)$ for $i\in\N$. 
A rough upper bound for the sizes of these sets is given in the following lemma.

\begin{lemma} Suppose that $X$ is a finite set of ordinals and $i\geq
  1$. Then
  \begin{align*}
    &|U_m^i(X)|\leq (c_m(X)+im)^{m+1} d_m(X), \text{ and also}\\
    &\lvert U_m^i(X,\delta)|\leq (c_m(X\cup\{\delta\})+im)^{m+1}
    d_m(X\cup\{\delta\}).    
  \end{align*}
\end{lemma} 

\begin{proof} The coefficient of $\omega^j$ of an element of $U_m^i(\gamma)$ can take at most $(c_m(w)+im)^{m+1}$ many different values for any fixed $j\leq m$. 
Hence $|U_m^i(\alpha)|\leq (c_m(w)+im)^{m+1}$ for all ordinals $\alpha$ and all $i\geq 1$. Moreover $d_m(U_m^i(X))=d_m(X)$ for all $i\geq 1$. 
\qed \end{proof} 

It follows that there are at most
$|\Sigma_{\diamond}|^{(c_m(X)+im)^{m+1} d_m(X)}$ many finite words $w$
over alphabet $\Sigma_\diamond$ with $\mathsf{supp}(w)\subseteq U_m^i(X)$ for $i\geq 1$, where $\Sigma_{\diamond}$ is an alphabet with $\diamond\in\Sigma$. 

A relation $R\subseteq X\times Y$ is called \emph{locally finite} if for every $x\in X$, there are at most finitely many $y\in Y$ with $(x,y)\in R$. 

\begin{lemma}(Growth lemma) Suppose $\eta$ is an ordinal and $R\subseteq (\Sigma^*)^k\times(\Sigma^*)^l$ is a locally finite relation of finite $\eta$-words. Suppose $R$ is recognised by an $\eta$-automaton $\mathcal{A}$ with at most $m$ states. Then $\mathsf{supp}(w)\subseteq U_{m+1}(\mathsf{supp}(v),\eta)$ for all $(v,w)\in R$. 
\end{lemma} 

\begin{proof} Suppose $\alpha\in \mathsf{supp}(w)\setminus U_{m+1}(\mathsf{supp}(v),\eta)$ is minimal. Let $k\in \N$ be least such that there are $\beta\in \mathsf{supp}(w)\cup\{0,\eta\}$ and $\delta$ with $\omega^{k+1}\delta\leq \alpha,\beta<\omega^{k+1}(\delta+1)$. It follows from the Pumping Lemma that $k\leq m$. Choose the maximal such $\beta$ for this $k$. If $\beta\neq\delta$ then $\mathsf{supp}(w)\cap (\beta,\omega^{k+1}(\delta+1))=\emptyset$. At most $m$ different states can appear at the ordinals $\beta+\omega^{k}l$ for $l\in\N$. Since $R$ is locally finite, none of the states appears twice between $\beta$ and $\alpha$ if $\beta\neq\delta$, since otherwise it is possible to shrink the run, and hence $\omega^{k+1}\delta \leq \alpha<\beta+\omega^k m$. 
If $\beta=\delta$ then $\omega^{k+1}\delta\leq\alpha<\beta$. 
Let $\alpha_j$ denote the coefficient of $\omega^j$ in the Cantor normal form of $\alpha$ for $j\in\N$. Since there are at most $m$ states and $R$ is locally finite, $\alpha_j<m$ for all $j<k$ and hence $\alpha\in U_{m+1}(\beta)$. 
\qed \end{proof} 

Let $\lceil x \rceil$ denote the least $n\in\omega$ with $x\leq n$, and $\log$ the logarithm with base $2$. 

\begin{lemma} (Growth lemma for monoids) Suppose the multiplication of the monoid $(M,\cdot)$ is recognised by an automaton with $\leq m$ states. Suppose $s_1,...,s_{n}\in M$ and $\mathsf{supp}(s_i)\subseteq X$ for $1\leq i\leq n$ where $n\geq 2$. Then $\mathsf{supp}(s_1\cdot...\cdot s_n)\subseteq U_{m+1}^{\lceil \log n\rceil}(X)$. 
\end{lemma} 

\begin{proof} We follow the proof of \cite[Lemma
  3.2]{DBLP:journals/lmcs/KhoussainovNRS07}. The statement follows
  from the Growth Lemma for $n\geq 2$. For $n>2$ let $k=\lceil
  \frac{n}{2}\rceil$ and $l=n-k$. Then $\lceil \log k\rceil, \lceil
  \log l\rceil< \lceil \log n\rceil$. Let $t=s_1\cdot...\cdot s_k$ and
  $u=s_{k+1}\cdot...\cdot s_n$. Then $\mathsf{supp}(t)\cup
  \mathsf{supp}(u)\subseteq U_{m+1}^{\lceil \log n\rceil-1}(X)$ by the
  induction hypothesis for $\lceil\frac{n}{2}\rceil$. Thus, 
  $\supp(t\cdot u) \subseteq U_{m+1}^{\lceil
    \log n\rceil}(X)$ by the Growth Lemma applied to $t$ and $u$.  
\qed \end{proof} 




We  prove that the countable atomless Boolean algebra is not
$\delta$ automatic for any ordinal $\delta$. 
We first conclude by Lemma
\ref{lemma: elementary substructure} that it suffices to consider
ordinals of the form 
$\delta=\omega^k$ with $k\in\N$.

\begin{corollary}
  Let $\eta, \kappa, \delta$ be ordinals such that
  $\eta\geq 1$, $\kappa<\omega^\omega$, and
  $\delta=\omega^{\omega}\cdot \eta + \kappa$. If the countable
  Boolean algebra is finite word $\delta$-automatic then 
  it is finite word $\omega^k$-automatic for some $k\in\N$. 
\end{corollary}
\begin{proof}
  Let $\bar\Ac=(\Ac, \Ac_\cup, \Ac_\cap, \Ac_0, \Ac_1)$ be $\delta$-automata
  representing  the countable atomless Boolean algebra 
  $\mathfrak{M}=(M, \cup,\cap, \bf{0}, \bf{1})$.
  Let $n\in\N$ be a bound on the number of states of any of these automata.
  $\delta$ can be written as a sum
  $\omega^{n+2} + \omega^\omega \cdot \eta + \kappa$. 
  Let $m'$ be a finite $\delta$-word such that $m'\in M$. 
  Due to the Shrinking Lemma 
  \ref{lemma: Shrinking for ordinal automata}, 
  there is an $m\in M$ with $\supp(m)\subseteq \omega^{n+2} \cup
  \kappa$, i.e., a word whose support has a $\omega^\omega \eta$ gap
  at $\omega^{n+2}$. 
  Now let $\Ac_{\varphi}$ be the automaton that corresponds in
  $\mathfrak{M}$ to the $\Pi_2$ formula $\varphi(x)$ saying
  $x\in M \land $ $M$ \emph{forms a Boolean algebra without
  atoms}.\footnote{Note that associativity, commutativity, identity,
    distributivity are $\Pi_1$-statements, existence of complements is
    $\Pi_2$ and absence of atoms is a $\Pi_2$-statement.}
  Due to Lemma \ref{lemma: elementary substructure} and since 
  $m$
  satisfies $\varphi$ in $\mathfrak{M}$, 
  in the structure 
  $\mathfrak{M}'=(M', \cup',\cap,\bf{o}',\bf{1}')$ induced by
  $\bar\Ac$ seen as  $(\omega^{m+2} + \omega^{m+2} + \kappa)$-automata,
  there is a word $m'\in M'$  satisfying $\varphi$. 
  Thus, $\mathfrak{M}'$ forms a countable Boolean algebra
  without atoms. 
  By definition of $\kappa$,
  there is a  $k'\in \N$ such that $\kappa<\omega^{k'}$ 
  Set $k:=\max(k'+1,m+3)$. 
  Since there is an $\omega^{k}$-automaton marking position
  $\omega^{m+2} 2 + \kappa$ by a unique state, the countable atomless
  Boolean algebra 
  $\mathfrak{M}'$ also has an $\omega^k$-automatic presentation.
\qed \end{proof}


We finally show that the countable atomless Boolean algebra has no
$\omega^k$-automatic presentation.

\begin{theorem} The countable atomless Boolean algebra is not $\delta$-automatic for any ordinal $\delta$. 
\end{theorem} 

\begin{proof} 
  Assume that the countable
  atomless Boolean algebra has an $\omega^k$-automatic presentation
  $\mathfrak{M}=(M,\cup,\cap,\bf{0},\bf{1})$. Suppose the automata
  have at most $m$ states.  

  We follow the proof of \cite[Lemma
  3.4]{DBLP:journals/lmcs/KhoussainovNRS07}. We construct trees $T_n$
  with nodes $a_{\sigma}$ for all $\sigma\in 2^{\leq n}$ such that
  $T_n$ has exactly $2^n$ leaves and $u\cap v=\bf{0}$ for
  any any two leaves $u\neq v$ of $T_n$.\footnote{In this construction
    we replace Khoussainov et al.'s use of the length-lexicographic
    order by the use of an $\omega^k$-automatic well-order of the
    finite $\omega^k$-words.}
  The partial functions which
  determine the successor nodes $a_{\sigma0},a_{\sigma1}$ from
  $a_{\sigma}$ are definable in
  $\mathfrak{M}$ by first-order formulas with the quantifier
  $\exists^{\infty}$ and hence recognisable by automata by the closure
  of $\omega^k$-automatic relations under first-order definable
  relations\footnote{as usual in automatic structures 
    $\exists^{\infty}$ can be replaced by a
    first-order statement over some automatic expansion.} (see
  \cite{BedonBesCartonRispal2010}). Suppose each of these automata has
  at most $l\geq m$ states.  
  Then $\mathsf{supp}(a_{\sigma})\subseteq
  U_{l+1}^n(\mathsf{supp}(a_{\emptyset}))$ for all $\sigma \in
  \{0,1\}^{\leq n}$. %for which $a_{\sigma}$ is defined. 
  If $s=s_1\cup ...\cup s_j$ with pairwise
  different leaves
  $s_1,...,s_j\in T_n$, then $j\leq2^n$ and
  $\mathsf{supp}(s)\subseteq  U_{l+1}^{n 
    \lceil \log(2^n)\rceil}(\mathsf{supp}(a_{\emptyset}),\omega^l)$
  by the growth lemma for monoids. There are at most
  $|\Sigma_{\diamond}|^{(c_l(\mathsf{supp}(a_{\emptyset})\cup\{\omega^l\})+
    n\lceil\log(2^n)\rceil 
    l)^{l+1}}$ many such $s$. However, since the leaves of $T_n$ are
  pairwise incompatible, there are $2^{(2^n)}$ many $s$.
  This is a contradiction for large $n$.  
\qed \end{proof} 

Note that the growth argument in the previous proof can also be applied directly to the $\delta$-automatic presentation. 

\begin{lemma} Suppose $\Lf$ is of the form $\mathbb{Z}\cdot
\mathfrak{M}$ for some linear order $\mathfrak{M}$. Then the countable
atomless Boolean algebra is not $\Lf$-automatic.
\end{lemma}

\begin{proof} Suppose that $R$ is a locally finite $\Lf$-automatic
relation on an $\Lf$-automatic structure $M$ such that $R$ and the domain and relations of $M$ are recognised by automata
with $\leq m$ states. Then for any $(x,y)\in R$ and any $t\in
\mathsf{supp}(y)$, there are $u\leq v \in \mathsf{supp}(x)$ with
finite distance such that $\bar{u}\leq t\leq \bar{v}$ for the $n^{th}$
predecessor $\bar{u}$ of $u$ and the $m^{th}$ successor $\bar{v}$ of
$v$. The same growth rate argument as for finite automata (see \cite[Theorem 3.4]{DBLP:journals/lmcs/KhoussainovNRS07}) shows that
every infinite $\Lf$-automatic Boolean algebra is a finite product of
the Boolean algebra of finite and co-finite subsets of $\N$ with inclusion. 
\qed \end{proof}

\begin{question} Is the countable atomless Boolean algebra
  $\Lf$-$o$-automatic for any linear order $\Lf$ and any oracle $o$? 
\end{question} 





\begin{comment}

\end{comment}

\end{document}

  

\section{Old Stuff}

\begin{comment}

\begin{lemma}\label{lem:ordinals1}\fixme{I'm not sure if this is used in the current version of the next lemma.}
  Let $\alpha_0 < \omega^m \cdot \beta$. Then  there is some ordinal
  $\beta_0$ such that 
  $\alpha_0 + \omega^{m-1} =  \omega^{m-1} \cdot  \beta' <\omega^m
  \cdot \beta$.

  Moreover, $[\alpha_0, \omega^{m}\cdot \beta)$ is isomorphic to
  $\omega^{m-1}\cdot \eta$ for some ordinal $\eta\geq 1$.
  
\end{lemma}

\begin{proof}
  By left division with remainder, 
  $\alpha_0= \omega^m \cdot \gamma + \delta$ for some ordinal $\gamma$
  and some ordinal $\delta < \omega^m$.
  Thus $\omega^m\cdot \gamma < \omega^m  \cdot \beta$ whence
  $\gamma < \beta$. 
  We conclude that $\alpha_0+\omega^{m-1} = 
  \omega^{m-1} \cdot (\omega \gamma) + \delta + \omega^{m-1} = 
  \omega^{m-1} \cdot (\omega \gamma + 1) \leq \omega^{m-1} (\omega
  \beta)$. Since $\omega \cdot \beta$ is  a limit ordinal and
  $\beta':=\omega \gamma +1$ is not, the claim follows. 

  Since $\alpha_0=\omega^m\cdot \gamma +
  \delta < \omega^m \cdot \beta$  and $\gamma<\beta$ there is a unique 
  $\eta$ such that $\gamma+\eta = \beta$. 
  Now $\alpha_0+ \omega^m\cdot \eta = \omega^m \cdot (\gamma+\eta)
  = \omega^m \cdot \beta$. Thus, 
  $[\alpha_0, \omega^{m}\cdot \beta)$ is isomorphic to
  $\omega^{m-1}\cdot \eta$.
\qed \end{proof}

\end{comment} 




\begin{comment}

\begin{lemma}\label{lemma: elementary substructure} Suppose $M$ is a
$\delta$-automatic structure recognised by an automaton $\mathcal{A}$
with $\leq m$ states and $i\geq 1$. Suppose $(N,\eta)$ is obtained
from $(M,\delta)$ by replacing finitely many disjoint intervals $I_j$
above $\omega^{m+i}$ with lengths $\omega^{m+i}\gamma_j$ for some
$\gamma_j\geq 1$ by intervals $K_j$ of length $\omega^{m+i}$. This
induces a map $f$ on tuples of words in $N$ with supports disjoint
from all $I_j$. Suppose $\vec{w}\in N^{<\omega}$ with
$\mathsf{supp}(w)\cap I_j=\emptyset$ for all $j$ and $\varphi$ is a
$\Sigma_i$-formula. Then $N\vDash \varphi(\vec{w})$ if and only if
$M\vDash \varphi(f(\vec{w}))$.
\end{lemma}

\begin{proof} The claim for $i=0$ follows from the Pumping Lemma. For
the induction step, suppose $\varphi$ is a $\Pi_i$-formula and
$N\vDash \exists x\varphi(x,\vec{v})$. Choose $t\in N$ with $N \vDash
\varphi(t,\vec{v})$.
An \emph{interval word} is a function $w\colon
[\alpha,\beta)\rightarrow S$. Consider the finitely many maximal
interval words of the form $\diamond^{\omega^{m+i}\zeta_l}$ with
support disjoint from $\mathsf{supp}(t)\cup\mathsf{supp}(\vec{v})$.
We replace each such word by $\diamond^{\omega^{m+i}\xi_l}$ for some
$\xi_l\geq\zeta_l$ so that this is compatible with the original
pumping from $N$ to $M$.
%so that every interval word of the form
$\diamond^{\omega^{m+i+1}\theta}$ with support disjoint from
$\mathsf{supp}(t)\cup\mathsf{supp}(\vec{v})$ is replaced by
$\diamond^{\omega^{m+i+1}\sigma}$ for the same ordinal
$\sigma\geq\theta$ as in the original replacement.
We thus obtain a map $g$ mapping tuples of words in $N$ with supports
disjoint from these intervals into tuples of words in $M$ such that
$f(\vec{w})=g(\vec{w})$ for each tuple $\vec{w}$ of words with
supports disjoint from $K_j$ for all $j$. Then $f(\vec{v})=g(\vec{v})$
and $M\vDash \varphi(u,g(\vec{v}))$ by the induction hypothesis for
$\varphi$.
\qed \end{proof}

  
\end{comment}





\section{Preliminaries}
\label{sec:preliminaries}

Let $\alpha$ be some ordinal.
In this paper, we fix $\Sigma=\{0,1\}$ 
A \emph{finite $\alpha$-word} is a map $w:\alpha \to \Sigma$ such that
$w^{-1}(1)$, i.e., such that the preimage of $1$ is finite. 




\begin{lemma}
  Any finite word $\alpha$-automatic set admits an $\alpha$-automatic
  well-ordering. 
\end{lemma}
\begin{proof}
  For simplification we assume that $\alpha$ is a limit
  ordinal. Hence, 
  $\alpha=\omega \cdot \alpha_0$ for some ordinal $\alpha_0$, i.e.,
  $\alpha$ consists of $\alpha_0$ many copies of
  $\omega$. Interpreting each $\omega$-copy as a number in binary
  encoding (least significant bit first) any finite $\alpha$-word over
  $\Sigma=\{0,1\}$ is a sequence of length $\alpha_0$ where all but
  finitely many elements are $0$. It is easy to design an
  $\alpha$-automaton that compares these sequences lexicographically
  and the resulting order is a well-order.
\qed \end{proof}

Some easy facts about ordinals
\begin{lemma}
  For all $n<\omega$, we have 
  \begin{align*}
    \omega \cdot \omega^n =  \omega^{1+n}=\omega^{n+1}    
  \end{align*}
  and for all 
  $\alpha\geq \omega$, we have
  \begin{align*}
    \omega \cdot \omega^\alpha = \omega^{1+\alpha} = \omega^{\alpha}.
  \end{align*}
\end{lemma}
\begin{proof}
  The first claim is trivial. The second one is proven by induction. 
  Assume that the lemma is true for all $\beta<\alpha$. 
  If $\alpha=\omega$, then
  $\omega\cdot \omega^\alpha = \sup\{\omega\cdot \omega^i\mid
  i<\omega\} = \sup\{\omega^{i+1} \mid i< \omega\} = \omega^\omega$. 
  If $\alpha>\omega$ then 
  $\omega\cdot \omega^\gamma = \sup\{ \omega\cdot \omega^\beta \mid
  \omega\leq \beta < \gamma\} \overset{I.H.}{=}
  \sup\{ \omega^\beta\mid \omega\leq \beta < \gamma\} =
  \omega^\gamma$. 
\qed \end{proof}






\section{Comparing Finite Type Products and Sum-Augmentations of
  Tamely Colourable Box-Augmentations}

This section aims at the following two results. Firstly, any
$2$-dimensional tamely colourable box-augmentation can be considered as
a faithful finite type product. Secondly, a
faithful finite type product induces a sum-augmentation of tamely
colourable $2$-dimensional box-augmentations. Let us first recall
definitions: 

\begin{definition}
  A structure $\Af$ is \emph{sum-augmentation} of structures $\Af_1, \dots,
  \Af_n$ if the domain of $\Af$ can be partitioned into $n$ parts such
  that the substructure induced by the $i$-th part is isomorphic to
  $\Af_i$. 

  A structure $\Af=(A, \leq^A)$ is \emph{$2$-dimensional box-augmentation} of
  $\Bf=(B, \leq^B)$ and
  $\Cf=(C, \leq^C)$ if there is a bijection
  $f: B\times C \to A$ such that 
  \begin{enumerate}
  \item   $\Af{\restriction}_{f(\{b\}\times C)}$ is isomorphic to $\Cf$ for
    all $b\in B$ and
  \item   $\Af{\restriction}_{f(B \times \{c\})}$ is isomorphic to $\Bf$ for
    all $c\in C$. 
  \end{enumerate}
  Such a $2$-dimensional box-augmentation is \emph{tamely colourable}
  if there are finite range functions
  $\varphi_{\Bf}:B\times B \to M$ and $\varphi_{\Cf}: C\times C \to M$ 
  and a set $M_<\subseteq M\times M$ such that
  $f(b_1,c_1) <^A f(b_2,c_2)$ iff
  $\left(\varphi_{\Bf}(b_1,b_2), \varphi_{\Cf}(c_1,c_2)\right)\in
  M_<$. 
\end{definition}


Let us now define faithful finite type products. We use the following
auxiliary definition. Let $\Af$ be a structure over some signature
$\tau$ with domain $A$ and
$f,g: B \to A$ be partial functions. Let $\tau^{f,g}$ be 
$\tau \cup \{ c_b: b\in \domain(f)\} \cup \{d_b:b\in \domain(g)\}$
where the $c_b$ and $d_b$ are fresh constant symbols. 
We write $\mathsf{type}(f,g)$ for the structure that is the expansion
of $\Af{\restriction}_{\image(f)\cup\image(g)}$ to a $\tau^{f,g}$
structure by interpreting 
a constant $c_b$ as $f(b)$ for all $b\in \domain(f)$ and 
a constant $d_b$ as $g(b)$ for all $b\in \domain(g)$. 


\begin{definition}
  Let $\Ef_1, \Ef_2, \dots, \Ef_n$ and $\Ff_1, \dots, \Ff_n$ be
  structures where $\Ef_i$ has domain $E_i$ and $\Ff_i$ has domain
  $F_i$. A structure $\Af$ with domain $A$ is a 
  \emph{faithful finite type product} of $(\Ef_1, \dots, \Ef_n)$ and 
  $(\Ff_1, \dots, \Ff_n)$ if there is a bijection
  $\varphi: \bigsqcup_{i=1}^n E_i\times F_i \to A$ such that
  \begin{enumerate}
  \item for all $1\leq i \leq n$ and $e\in E_i$ the restriction 
    $\varphi_e := \varphi{\restriction}_{\{e\}\times F_i}$ is an
    isomorphism between  
    $\Ff_i$ and the substructure of $\Af$ induced by the image of
    $\varphi_e$,
  \item for all $1\leq i \leq n$ and $f\in F_i$ the restriction 
    $\varphi^f:\varphi{\restriction}_{E_i \times \{f\}}$ is an
    isomorphism between  
    $\Ef_i$ and the substructure of $\Af$ induced by the image of
    $\varphi^f$,
  \item The sets 
    \begin{align*}
      &\mathsf{T_1}(\varphi) = \{\mathsf{type}(\varphi_e,
      \varphi_{e'}): e,e'\in \bigsqcup_{i=1}^n E_i\} \text{ and}\\
      &\mathsf{T_2}(\varphi) = \{\mathsf{type}(\varphi^f,
      \varphi^{f'}): f,f'\in \bigsqcup_{i=1}^n F_i\}
    \end{align*}
    are finite (up to isomorphisms).
  \end{enumerate}
\end{definition}

\begin{lemma}
  If $\Af$ is a faithful finite type product of 
  $(\Ef_1, \dots, \Ef_n)$ and $(\Ff_1, \dots, \Ff_n)$ via the function
  $\varphi$ then $\Af$ is 
  a sum-augmentation of structures $\Af_1, \dots, \Af_n$ where $\Af_i$
  is a tamely colourable box-augmentation of $\Ef_i$ and $\Ff_i$. 
\end{lemma}
\begin{proof}
  For simplicity we assume that $\Af$ is a graph with edge relation
  $<$. For arbitrary signatures $\tau$ the proof works analogously.
  
  Define a colouring $\psi_{\Ef_i}: E_i\times E_i \to \mathsf{T_1}(\varphi)$ via
  $\psi_{\Ef_i}(e,e') = \mathsf{type}(\varphi_e,\varphi_{e'})$. 
  For the colouring of $\Ff_i$ we fix an enumeration 
  $(e_1,e_1'), (e_2, e_2'), \dots, (e_m, e_m') \in E_i\times E_i$ such that 
  for all $e,e'$ there is a unique $1\leq j \leq m$ such that
  $\mathsf{type}(\varphi_{e}, \varphi_{e'}) = 
  \mathsf{type}(\varphi_{e_i}, \varphi_{e'_i})$. 
  Now define the colouring
  $\psi_{\Ff_i}: F_i\times F_i \to \{0,1\}^m$  via
  $\psi_{\Ff_i}(f,f') = (x_1, \dots, x_m)$ where $x_j=1$ iff
  in $\mathsf{type}(\varphi_{e_i}, \varphi_{e'_i})$
  $c_f < d_{f'}$ holds.\footnote{Recall that in 
  $\mathsf{type}(\varphi_{e_i}, \varphi_{e'_i})$ the constant $c_f$ 
  is interpreted as $\varphi(e_i,f)$  and $d_{f'}$ is interpreted as
  $\varphi(e'_i, f')$.}
  
  Note that for arbitrary $e,e'\in E_i$ and $f,f'\in F_i$ we have
  $\varphi(e,f) < \varphi(e',f')$ iff
  the $j$-th bit of
  $\psi_{\Ff_i}(f,f')$ is $1$ where $j$ is the unique number such that
  $\mathsf{type}(\varphi_{e_j}, \varphi_{e'_j}) =
  \psi_{\Ef_i}(e,e')$. 
  
  It is now easy to see that $\Af$ is the sum-augmentation of the
  substructures induced by $\varphi(E_i\times F_i)$ and the
  substructures induced by $E_i \times F_i$ are tamely colourable
  box-augmentations of $\Ef_i$ and $\Ff_i$. 
\qed \end{proof}


\begin{lemma}
  Let $\Af$ be a $2$-dimensional tamely colourable box-augmentation of 
  $\Ef$ and $\Ff$ via the map $\varphi:E\times F \to A$.
  Then $\Af$ is a faithful finite type product of $\Ef$ and $\Ff$ via
  $\varphi$. 
\end{lemma}
\begin{proof}
  For $e,e'\in E$ note that $\mathsf{type}(\varphi_{e},\varphi_{e'})$ is
  determined by the colour of $(e,e')$, of $(e',e)$, of $(e,e)$ and of
  $(e',e')$. 
\qed \end{proof}



\section{Multidimensional Finite Type Products and Tree-Automatic Structures}
\label{sec:TreeProducts}


In this section, we propose to lift the notion of faithful finite type
products to more than $2$ dimensions.
We then prove that the substructures of a given tree-automatic
structure are multidimensional finite type products of a finite set of
tree-automatic structures. 

For our definition we use the following two notations. 

Firstly, let 
$\varphi: \bigsqcup_{i=1}^n  \prod_{j=1}^m B_i^j  \to A$ be some
function, $1\leq i_0 \leq n$ some number, 
\mbox{$P\subseteq \{1, 2, \dots,m\}$} be a subset and $\bar P= \{1, 2,
\dots, m\}\setminus P$ its 
complement, and  
\begin{equation*}
  \bar b= (b_{k_1}, b_{k_2}, \dots, b_{k_l}) \in \prod_{p\in P}
  B_{i_0}^j  
\end{equation*}
some tuple. 
Then we define
\begin{align*}
  &\varphi^P_{\bar b}: \prod_{\bar p\in \bar P} B_{i_0}^{\bar p} \to A
  \text{ by}\\
  &\varphi^P_{\bar b}( b_{k_{l+1}}, b_{k_{l+2}}, \dots, b_{k_{m}}):= 
  \varphi(b_1, b_2, \dots, b_m),
\end{align*}
i.e., $\varphi^P_{\bar b}$ is the
function $\varphi$ restricted to those elements where the coordinates
specified by $P$ are fixed to the corresponding elements of $\bar b$. 
In the case that $P=\{1, \dots, m\} \setminus\{p\}$, we also write
$\varphi^p_{\bar b}$ for $\varphi^P_{\bar b}$.

Secondly, let $\Af$ be a structure over some signature
$\tau$ with domain $A$ and
$f,g: B \to A$ be partial functions. Let $\tau^{f,g}$ be 
$\tau \cup \{ c_b: b\in \domain(f)\} \cup \{d_b:b\in \domain(g)\}$
where the $c_b$ and $d_b$ are fresh constant symbols. 
We write $\mathsf{type}(f,g)$ for the structure that is the expansion
of $\Af{\restriction}_{\image(f)\cup\image(g)}$ to a $\tau^{f,g}$
structure by interpreting 
the constant $c_b$ as $f(b)$ for all $b\in \domain(f)$ and 
the constant $d_b$ as $g(b)$ for all $b\in \domain(g)$. 


  



\begin{definition}
  For $1\leq i \leq m$ and $1\leq j \leq n$, Let $\Bf_i^j$ be
  structures over some signature $\tau$ where $\Bf_i^j$ has domain
  $B_i^j$. A structure $\Af$ with domain $A$ is a  
  \emph{faithful finite type product} of 
  $(\Bf_1^1, \dots, \Bf_m^1), 
  (\Bf_1^2, \dots, \Bf_m^2), \dots, 
  (\Bf_1^n, \dots, \Bf_m^n)$
  if there is a bijection
  $\varphi: \bigsqcup_{i=1}^n  \prod_{j=1}^m B_i^j  \to A$ such that
  \begin{enumerate}
  \item for all $1\leq i \leq m$, all $1\leq j \leq n$ and 
    all $\bar b= b_1^j, \dots, b_{i-1}^j,b_{i+1}^j, \dots, b_m^j \in 
    \prod_{1\leq k \leq m, k\neq i}  B_k^j$
    the function 
    $\varphi^i_{\bar b}$
    is an  isomorphism between  
    $\Bf_i^j$ and the substructure of $\Af$ induced by 
    $\image( \varphi^i_{\bar b} )$,
  \item for all $P\subseteq \{1, 2, \dots, m\}$ the set
    $\mathsf{T}_P(\varphi) = 
      \{ \mathsf{type} (\varphi_{\bar b}, \varphi_{\bar b'}): \bar b,
      \bar b' \in \bigsqcup_{i=1}^n  \prod_{p\in P} B_i^p \}
    $
    is finite up to isomorphisms.
  \end{enumerate}
\end{definition}


For a tree $t$, let the \emph{frontier} of $t$, denoted by $\fr(t)$,
be the set of minimal elements of $\{0,1\}^*\setminus\domain(t)$. 

In the following we consider deterministic bottom-up tree-automata
$\Ac=(\Sigma, Q, q_i, F, \Delta)$ where $\Sigma$ is a finite alphabet,
$Q$ a finite set of states $q_i\in Q$ the initial state, $F\subseteq Q$
the set of final states, and 
$\Delta: Q\times Q \times \Sigma \to Q\setminus\{q_i\}$ is the
transition function.

For a map $\rho:\{0,1\}^* \to Q$, a set $D\subseteq \{0,1\}^*$ and a
(binary) tree $t$ we say
$\rho$ is \emph{compatible} on $D$ with $t$ and $\Ac$ 
if 
\begin{enumerate}
\item the equation $\rho(w) = \rho(w0) = \rho(w1) = q_i$ is
  satisfied for all
  $w\in D\setminus \domain(t)$ and 
\item 
  $\Delta( \rho(w0), \rho(w1), t(w)) = \rho(w)$ is satisfied
  for all $w\in D\cap \domain(t)$. 
\end{enumerate}

Note that for a tree $t$, a set $A\subseteq \{0,1\}^*$  
and $\varphi:A\to Q$ some map, there is at most one extension
$\rho_{\Ac,t}^{\varphi} :\{0,1\}^* \to Q$ of $\varphi$ that is
compatible on $\{0,1\}^*\setminus A$ with $t$. If it exists, we can
explicitly define it by induction on the depth of $t$ setting
\begin{align*}
  \rho_{\Ac,t}^{\varphi}(w) =
  \begin{cases}
    q_i &\text{if }w\in \{0,1\}^*\setminus (A\cup \domain(t))\\
    \varphi(w) &\text{if }w\in A\\
    \Delta(\rho_{\Ac,t}^{\varphi}(w0) ,\rho_{\Ac,t}^{\varphi}(1), t(w))
    &\text{ otherwise.}
  \end{cases}
\end{align*}
This extension does not exist if and only if there is some $a\in A$
such that $\varphi(a)\neq q_i$ and the predecessor of $a$ does not
belong to $A\cup \domain(t)$. 

In case that $A=\emptyset$, we write $\rho_{\Ac,t}$ for
$\rho_{\Ac,t}^{\varphi}$ and call it the \emph{run} of $\Ac$ on $t$. 
Given a tree $t$, a set $A\subseteq\{0,1\}^*$ and a function
$\varphi:A\to Q$ 
we let $\Ac(t, \varphi)=
\begin{cases}
\rho_{\Ac,t}^{\varphi}(\varepsilon)&\text{if
  $\rho_{\Ac,t}^{\varphi}$ is defined}\\   
\nil &\text{otherwise},
\end{cases}$
where $\nil$ is a special symbol representing undefined
elements. Especially, we never consider automata where $\nil$ appears
as a state.

We omit $\varphi$ if
$A=\emptyset$. Thus, $\Ac(t)$ denotes the state of the run of $\Ac$ on
$t$ at the root. We say $\Ac$ accepts a tree $t$ if 
$\Ac(t)\in F$. The language of $\Ac$ is the set of all trees accepted
by $\Ac$. 
For $p$ some tree, we write $\Ac( \cdot\otimes p)$ for the set 
\begin{align*}
  \{t \mid \Ac(t\otimes p)\in F\}  
\end{align*}
of trees \emph{accepted by $\Ac$ with parameter $p$} (where $\otimes$
denotes as usual the convolution of trees). 


We will now show that for any tree-automatic structure $\Af$ and any
tree-automaton $\Ac$ 
the induced substructures 
$\Af\cap \Ac(\cdot \otimes p)$ for all trees $p$ are all faithful
finite type products of  
a fixed finite set of automatic structures. 
For simplicity of the presentation, we restrict our attention to
graphs, i.e., to tree-automatic structures over the signature $\{R\}$
where $R$ is a binary relation symbol. 
Fix a tree-automatic graph $\Gf=(V, R^\Gf)$ whose edge relation
$R^\Gf$ is accepted by an automaton 
$\Ac_R$ with states $Q_R$ and final states $F_R$  and fix an automaton
$\Ac$ with states $Q$, 
initial state $q_i$ and final states $F\subseteq Q$ whose language is 
a subset of $V\otimes \Tc$. 
In the following, we prove a decomposition result for the
substructures
$\Gf_p:=\Gf{\restriction}_{\Ac(\cdot\otimes p)}$ for all parameters $p$. 
In order to do this, we first introduce the building blocks which we
will use. Let
\begin{align*}
  \Gamma =  Q_R \times Q  \times 2^{Q_R}.
\end{align*}
For each
$\gamma=(q_R,q,P)\in\Gamma$
we define a structure $\Bf_\gamma$ with domain
\begin{align*}
	B_\gamma = \{ t\in \Tc \mid
		\Ac_R(t\otimes t)=q_R\text{ and }
		\Ac(t \otimes \emptyset)=q\}
\end{align*}
and relation $R$ interpreted by
\begin{align*}
	\{ (t, t') \in B_\gamma^2 \mid
		\Ac_R(t \otimes t')\in P \}.
\end{align*}
Clearly, $\Bf_\gamma$ is tree-automatic.
The main result of this section is that each $\Gf_p$ is a finite type
product of copies of some of the structures $\Bf_\gamma$. 

Now we fix a parameter tree $p$ and investigate 
\begin{align*}
  \Gf_p=\Gf{\restriction}_{\Ac(\cdot\otimes p)}.  
\end{align*}
We also fix  an enumeration 
$u_1, u_2, \dots, u_{\lvert \fr(p)\rvert}$
of the frontier $\fr(p)$ of $p$. 
For $t, t_1, t_2, \dots, t_{\lvert \fr(p)\rvert}$ trees we later use
the notation $t[\fr(p)/(t_1, t_2, \dots, t_{\lvert \fr(p)\rvert})]$
for the tree that results
from $t$ by replacing the subtree rooted at $u_i$ by $t_i$. 

For $\varphi:\fr(p) \to Q$, $\varphi_R:\fr(p) \to Q_R$ and a tree $t$
 we call
$(t, \varphi, \varphi_R)$ good (w.r.t. $\Ac$ and $p$) if
\begin{enumerate}
\item $\domain(t)\subseteq \domain(p)$,
\item $\Ac(t\otimes p, \varphi)\in F$ and
\item for each $q\in\image(\varphi)$
  there is a tree $t_q$ such that $\Ac(t_q\otimes \emptyset)=q$. 
\end{enumerate}
Let $G$ be the set of good triples. 
For each good triple $(t, \varphi, \varphi_R)$ and each $1\leq i \leq
\lvert \fr(p) \rvert$ we define a set of trees
\begin{align*}
  T(p, t, \varphi, \varphi_R, u_i) :=
  \{ 
  t'\in \Tc \mid \Ac(t'\otimes \emptyset) = \varphi(u_i)\text{ and }
  \Ac_R(t'\otimes t') = \varphi_R(u_i)\}.  
\end{align*}
We make $T(p, t, \varphi, \varphi_R, u_i)$ the domain of a 
structure
\begin{align*}
  \Tf(p, t, \varphi, \varphi_R, u_i) =\left(T(p, t, \varphi, \varphi_R,
    u_i), E^{\Tf(p, t, \varphi, \varphi_R, u_i)}\right)  
\end{align*}
by setting
\begin{align*}
  (t_1,t_2)\in E^{\Tf(p, t, \varphi, \varphi_R, u_i)}
  \text{ if and only if }
  \Ac_R(t\otimes t, \varphi_R[u_i\mapsto \Ac_R(t_1\otimes t_2)])\in
  F_R.  
\end{align*}
Especially, $(t_1,t_2)\in E^{\Tf(p,t,\varphi,\varphi_R, u_i)}$
requires that 
$\Ac_R(t\otimes t, \varphi_R[u_i\mapsto \Ac_R(t_1\otimes t_2)])$ is
defined. 
Note that $\Tf(p, t, \varphi, \varphi_R, u_i)$ is isomorphic to 
$\Bf_\gamma$ for $\gamma=(\varphi_R(u_i), \varphi(u_i), P)$ where
\begin{align*}
P=\{ 
  q\in Q\mid 
  \Ac_R(t\otimes t, \varphi_R[u_i\mapsto q])\in F_R
\}.  
\end{align*}
Now we want to define a map $f: \Pgood \to \Gf_p$ where
\begin{align*}
  \Pgood:=\bigsqcup_{(t,\varphi, \varphi_R)\in G} \prod_{u_i\in
    \fr(p)}  T(p,t,\varphi,\varphi_R, u_i).
\end{align*}
Note that $\Pgood$ may contain several
copies of a tuple $(t_1, \dots, t_{\lvert\fr(p)\rvert})$ of trees
that occur in 
$\prod_{u_i\in \fr(p)}  T(p,t,\varphi,\varphi_R, u_i)$ for different
good triples $(t,\varphi,\varphi_R)$. 
In the following we write that the triple
$(t, \varphi, \varphi_R)$ \emph{witnesses} that
$(t_1, \dots, t_{\lvert\fr(p)\rvert})\in\Pgood$ if 
\begin{align*}
  (t_1, \dots, t_{\lvert \fr(p)\rvert})\in 
  \prod_{u_i\in \fr(p)}  T(p,t,\varphi,\varphi_R, u_i)
\end{align*}
if we want to address this specific copy of 
$(t_1, \dots, t_{\lvert\fr(p)\rvert})$ in $\Pgood$. 

Now, let $(t, \varphi, \varphi_R)$ be a triple witnessing
$\bar t=(t_1, t_2, \dots, t_{\lvert \fr(p)\rvert})\in \Pgood$.
We set 
$f(t_1, t_2, \dots, t_{\lvert \fr(p)\rvert}) = 
t[\fr(p)/(t_1, t_2, \dots, t_{\lvert \fr(p)\rvert})]$ 

Note that for all $\bar t=(t_1, \dots, t_{\lvert \fr(p) \rvert}) \in
\Pgood$, $f(\bar t)$ is indeed a tree in the domain of $\Gf_p$, i.e., 
$\Ac$ accepts $f(\bar t)\otimes p$:
Let $(t,\varphi, \varphi_R)$ be the triple witnessing that 
$\bar t \in \Pgood$. Thus, by definition of
$T(p, t, \varphi, \varphi_R, u_i)$, 
$\Ac(t_i\otimes \emptyset)= \varphi(u_i)$ 
for $1\leq i \leq \lvert \fr(p)\rvert$.
Moreover, $\Ac(t\otimes p, \varphi)\in F$ because 
$(t, \varphi, \varphi_R)$ is a good triple. But since 
$\domain(t)\subseteq \domain(p)$, 
\begin{align*}
\Ac(f(\bar t)\otimes p)= \Ac(t\otimes p, [u_i \mapsto \Ac(t_i \otimes
\emptyset)]) = \Ac(t\otimes p, \varphi)\in F.  
\end{align*}
 
Let us now show that $f$ is indeed a finite type product:
\begin{lemma}
  $f$ is a bijection between $\Pgood$ and the domain of $\Gf_p$
\end{lemma}
\begin{proof}
  We first show that $f$ is surjective. 
  Let $v\in \Gf_p$. Thus, there is an accepting run of
  $\Ac$ on $v\otimes p$. 
  Set $t := v{\restriction}_{\domain(p)}$ and set
  $t_i:=v(u_i)$ where $u_i$ is still the $i$-th node of $\fr(p)$. 
  Let $\rho$ be the run of $\Ac$ on $v\otimes p$ and $\rho_R$ the run
  of $\Ac_R$ on $v\otimes v$. 
  Let $\varphi:\fr(p)\to Q$ be defined by
  $\varphi(u_i)=\rho(u_i) =  \Ac(t_i\otimes \emptyset)$
  Analogously, let $\varphi_R:\fr(p)\to Q_R$ be defined by
  $\varphi_R(u_i)=\rho_R(u_i) =  \Ac_R(t_i\otimes t_i)$. 
  Since $v\in \Gf_p$, the triple $(p, \varphi, \varphi_R)$ is good. 
  Moreover, it is easy to see that 
  $t_i\in T(p, t, \varphi, \varphi_R, u_i)$. 
  Thus, $\bar t := (t_1, t_2, \dots, t_{\lvert \fr(p)\rvert})$ is in the
  domain   of $f$ and $f(\bar t)=v$. 
  
  Let us now show injectivity. Let 
  $\bar t= (t_1, \dots, t_{\lvert \fr(p) \rvert})$ be a tuple and $(t,\varphi,
  \varphi_R)$ be a good triple witnessing that $\bar t\in \Pgood$. 
  Analogously, let
  $\bar t'= (t'_1, \dots, t'_{\lvert \fr(p) \rvert})$ be a tuple and
  $(t',\varphi',  \varphi'_R)$ be a good triple witnessing that 
  $\bar t'\in \Pgood$.  
  Assume that $f(\bar t')= f(\bar t)$. We have to show that
  $\bar t = \bar t'$ and $(t,\varphi, \varphi_R)=(t', \varphi',
  \varphi'_R)$.
  Note $f(\bar t') = f(\bar t)$ immediately implies that $\bar t'=\bar
  t$ and $t=t'$. Moreover, $t_i$ ($t_i'$, respectively) completely determines 
  $\varphi(u_i)$ and $\varphi_R(u_i)$ 
  ($\varphi'(u_i)$ and $\varphi'_R(u_i)$, respectively). Since we
  already know that 
  $t_i=t'_i$ we obtain $\varphi=\varphi'$ and $\varphi_R=\varphi'_R$. 
\qed \end{proof}
\begin{remark}
  Note that the previous proof shows that for a tuple $\bar t$ of
  trees and a fixed tree $t$ there is at most one good triple  
  $(t, \varphi, \varphi_R)$ witnessing that $\bar t\in \Pgood$. 
\end{remark}

For all $\bar t = (t_1, t_2, \dots, t_{\lvert \fr(p)\rvert})\in
\Pgood$ and  all $1\leq i \leq \lvert \fr(p) \rvert$ we write
$\bar t^i$ for the 
$(\lvert \fr(p)\rvert-1)$-tuple that results from $\bar t$
by omission of the $i$-th component. 
Fix such a pair $\bar t$, $i$  and 
the good triple $(t, \varphi, \varphi_R)$ witnessing $\bar t\in
\Pgood$.  
Recall the function $f^i_{\bar t^i}:T(p,t,\varphi,\varphi_R,u_i)\to
\Gf$ that results from $f$ by fixing all but one argument to the values
specified by $\bar t^i$. 
\begin{lemma}
  For all $i$ and all $\bar t\in \Pgood$, 
  the functions $f^i_{\bar t^i}$ is a partial isomorphism between
  $\Tf(p,t,\varphi,\varphi_R, u_i)$ and its image in $\Gf_p$. 
\end{lemma}
\begin{proof}
  Given two elements $t',t''\in T(p,t,\varphi,\varphi_R,u_i)$ such
  that $(t',t'')\in E^{\Tf(p,t,\varphi,\varphi_R,u_i)}$. By definition
  this is equivalent to 
  \begin{align} \label{isoembedding}
    \Ac_R(t\otimes t, \varphi_R[u_i\mapsto \Ac_R(t'\otimes t'')])\in
    F_R.     
  \end{align}
  Note that (writing $\bar t = (t_1, \dots, t_{\lvert \fr(p) \rvert})$)
  \begin{align*}
    &f^i_{\bar t^i}(t')= t[\fr(p)/(t_1, \dots, t_{i-1}, t',
    t_{i+1}, \dots, t_{\lvert \fr(p)\rvert})]\text{ and}\\ 
    &f^i_{\bar t^i}(t'')= t[\fr(p)/(t_1, \dots, t_{i-1}, t'',
    t_{i+1}, \dots, t_{\lvert \fr(p)\rvert})].  
  \end{align*}
  Thus, $f^i_{\bar t^i}(t') \otimes f^i_{\bar t^i}(t')$ is the tree
  \begin{align*}
    (t\otimes t)[\fr(p)/(t_1\otimes t_1, \dots, t_{i-1}\otimes
    t_{i-1}, t'\otimes t'',
    t_{i+1}\otimes t_{i+1}, \dots, t_{\lvert \fr(p)\rvert}\otimes
    t_{\lvert \fr(p)\rvert})] 
  \end{align*}
  By definition of $\bar t$, we have $\Ac_R(t_j\otimes
  t_j)=\varphi_R(u_j)$ for all $1\leq j \leq \lvert \fr(p)\rvert$.
  Hence \eqref{isoembedding} holds if and only if $\Ac_R$ accepts 
  $f^i_{\bar t^i}(t') \otimes f^i_{\bar t^i}(t')$.
\qed \end{proof}

Finally we have to prove the finite type property of the function $f$.
\begin{lemma}
  For all $P\subseteq \{1, 2, \dots, \lvert \fr(p)\rvert\}$ the set
  \begin{align*}
    \mathsf{T_P(f)} = 
    \{ \mathsf{type}(f_{\bar b}, f_{\bar b'}): \bar b,
    \bar b' \in \bigsqcup_{(t,\varphi, \varphi_R)\in G}  \prod_{p\in P}
    T(p,t,\varphi,\varphi_R,u_p) \}
  \end{align*}
  is finite.
\end{lemma}
\begin{proof}
  The proof is an easy decomposition of runs similar to the previous 
  proof. 
  Let $\bar t, \bar t'$ be $\lvert P \rvert$-tuples of trees
  and let $(t,\varphi, \varphi_R), (t', \varphi', \varphi_R')\in G$ be
  good triples that witness that extensions of $\bar t$ and $\bar t'$,
  respectively, are contained in $\Pgood$.
  Then, $\mathsf{type}(f_{\bar t}, f_{\bar t'})$ is determined by
  $t, \varphi, \varphi_R, t', \varphi', \varphi_R', 
  (\Ac_R(t_p\otimes t_{p'}))_p\in P, \{\psi:\fr(p)\to Q_R \mid
  \Ac_R(t\otimes t', \psi)\in F_R\}$. Since there are only finitely
  many different such tuples, there are only finitely many types. 
\qed \end{proof}



\section{Ordinal Automatic Trees of High Rank}


\section{Questions}
\label{sec:questions}

\begin{enumerate}
\item What about deciding Ramsey-quantifier?
\item what about infinite alpha-words?
\item Can we bound the rank of well-founded partial orders 
that are $\alpha$-automatic? Our argument on tree-automatic structures
for upwards linear partial orders should carry over in some version to
be determined exactly (basically the rank bounds for scattered linear
orders should carry over. 
\item What happens to the arguments if we proceed to finite words over
scattered linear orders $\alpha$. The decomposition argument should yield a
$3$-dimensional box  with 2 components (prefix and suffix  not
containing part of the parameter) among a fixed set of structures and
a middle part of $\alpha'$ structures where $\alpha'$ is a proper
interval of $\alpha$ so it should have smaller FC-rank (?).
By induction on FC-rank we would get bounds on these trees. 
Jedes abgeschlossene Intevall eines FC-rank Alpha Ordnung ist endliche
Summe von Intervalen kleiner Ordnung.
\item From Philipp's slides: 
- the restriction of $\omega^\gamma$-structure to
  $\omega^\omega$ is an elementary substructure. 
  {\bf todo WHY?}
\item - the $\exists^\infty$ theory of an $\alpha$-structure is decidable.
  {\bf todo WHY?}
\end{enumerate}





Using the decomposition result of shuffles of scattered orders, we
obtain a similar result. 

\begin{theorem} \label{thm:Shuffle-BoundsonScatteredOrders}
  Let $\alpha=\shuffle(\alpha_1, \dots, \alpha_n)$ be a shuffle of 
  scattered orders whose $\FC$ rank is at most
  $1+\gamma$ ($0$, respectively) for some ordinal $\gamma$. 
  Every $\alpha$-automatic scattered linear order has $\FCstar$
  rank strictly below $\omega^{\gamma+\omega}$ ($\omega^\omega$, respectively).
\end{theorem}
\begin{problem}
  What about $\alpha$-oracle-automatic structures?
\end{problem}
\begin{proof}
  Heading for a contradiction, assume that  $\Lf$ is an
  $\alpha$-automatic scattered linear order with
  $\FCstar(\Lf)\geq\omega^{\gamma+\omega}$. 
  Then there is a parameter automaton and parameters $p_i$ such that
  $\FCstar(\Lf_{p_i}) = \omega^{\gamma+i}$. 
  Due to Theorem \ref{thm:ShuffleDecomposition}, each $\Lf_{p_i}$
  decomposes as a sum of boxes of $(\Cc, \Dc, \Cc, \Dc, \dots, \Cc)$
  where $\Dc$ contains only $\beta$-oracle-automatic structures for
  scattered linear orders $\beta$ of with $\FC(\beta)\leq 1+\gamma$
  and $\Cc$ is finite. Thus, there is some $k\geq 1$ such that
  there is no $\Lf'\in \Cc\cup \Dc$ with 
  $\FCstar(\Lf') = \omega^{\gamma+k+1}$. 
  But now there are substructures $\Lf'_1, \dots, \Lf'_m \in
  \Cc\cup\Dc$ of $\Lf_{p_{k+1}}$ such that there is a box
  of $\Lf'_1, \dots, \Lf'_m$ of $\FC$ rank $\omega^{\gamma+k+1}$
  Due to Lemma \ref{lem:FCStarAndBox}, 
  this requires 
  \begin{equation*}
    \omega^{\gamma+k+1} \leq
    \FCstar(\Lf'_1)\oplus  \FCstar(\Lf'_2)\oplus \dots\oplus
    \FCstar(\Lf'_n)    
  \end{equation*}
  which requires $\FCstar(\Lf'_j)\geq \omega^{\gamma+k+1}$ for some
  $1\leq j \leq m$. Since $\Lf'_j$ is a substructure of
  $\Lf_{p_{k+1}}$ this contradicts $\FCstar(\Lf'_j)\neq
  \omega^{\gamma+k+1}$. 
\qed \end{proof}
\begin{remark}
  The previous result has no extension to arbitrary dense sums of
  scattered orders. In order to see this, choose some order
  $\Lf\subseteq (\Q, \leq)$  with $\FCstar(\Lf)=\beta$ an arbitrary
  countable ordinal. $\Lf$ has an $\alpha$-automatic presentation
  where $\alpha$ 
  is a $\Q$-sum of orders of $\FC$ rank $0$. 
  For this purpose, for each $q\in \Q$ let  $\alpha_q:=
  \begin{cases}
    \emptyset &\text{if }q\notin \Lf,\\
    1        &\text{if } q\in\Lf,
  \end{cases}$.
  Setting $\alpha:=\sum_{q\in\Q} \alpha_q$, it is straightforward to
  see that the $\alpha$-words with support of size $1$ are in
  bijection with $\Lf$ and the order of $\Lf$ is isomorphic to the
  order of the supports (with respect to their position in $\Q$).
  Thus, $\Lf$ is a $\Q$-sum of the $\alpha_q$ which all have
  $\FC(\alpha_q)=0$. 
\end{remark}









\section{Old Stuff}
\label{sec:OLD}






\begin{comment}
  $\omega^\omega$-automatic:
  Direct analysis of  $\infrank$ (or even rank)  under finite type products 
  does not give a better bound.
  
  Complementation of Rational Sets of Countable Scattered Linear
  Orderings, Rispal +Carton : 
  Regularity / Rationality is preserved by complementation for  words
  indexed by Scattered linear orderings.
  darin steht:
  Buechi Decision Methods in the Theory of Ordinals
    did it for transfinite words
  Bedon+Carton An Eilenberg Theorem for Words on Countable Ordinals:
    is an algebraic proof for closure under complement under
    transfinite words   

\end{comment}




\begin{lemma} Suppose $\mathcal{A}$ is a non-deterministic
  $\eta$-automaton with state set $\mathcal{S}$, $|\mathcal{S}|<m$,
  and $\gamma\geq 1$. Let $r\colon \eta\rightarrow \mathcal{S}$ vary
  over runs of $\mathcal{A}$. If $r$ is a run of $\mathcal{A}$ and
  $\gamma<\eta$ is a limit ordinal, let $r(<\gamma)$ denote the set of
  states appearing unboundedly often before $\gamma$.  
Suppose $\mathcal{S}_0\subseteq\mathcal{S}$ and $s_0\in\mathcal{S}$. 
\begin{enumerate} 
\item There is a run $r$ on empty input with $r(<\omega^m)=\mathcal{S}_0$ if and only if there is a run $r$ on empty input with $r(<\omega^m\cdot \gamma)=\mathcal{S}_0$. 
\item There is a run $r$ on empty input with $r(\omega^m)=s_0$ if and only if there is a run $r$ on empty input with $r(\omega^m\cdot \gamma)=s_0$. 
\end{enumerate} 
\end{lemma} 

\begin{proof} Notice that (1) implies (2). We prove (1) by induction on $m$, $\gamma$, $|\mathcal{S}_0|$. 
If $|\mathcal{S}_0|< m-1$, the claim follows from the inductive hypothesis. Suppose $\mathcal{S}_0=\mathcal{S}$. 

Suppose $r(<\omega^m)=\mathcal{S}$. Choose $\alpha<\omega^m$ with $r(\alpha)=r(\omega^m)$. Define a run $t\colon \omega^m\cdot\gamma\rightarrow \mathcal{S}$, $t(\beta)=r(\beta)$ for $\beta<\omega^m$, $t(\omega^m\cdot \gamma+\beta)=r(\alpha+\beta)$ for $\beta<\omega^m$. Then $r(<\omega^m\cdot \beta)=\mathcal{S}$. 

Suppose $r(<\omega^m\cdot \gamma)=\mathcal{S}$. 
If there is $\beta<\gamma$ with $\beta\geq 1$ and $\mathcal{S}$ unbounded below $\omega^m\cdot\beta$, the claim follows from the inductive hypothesis. Suppose there is no such $\beta$. 
Let $\gamma_0$ denote the least $\omega^m\cdot\beta$ such that all states appear below $\omega^m\cdot \beta$. Let $\gamma_{n+1}$ denote the least $\omega^m\cdot\beta$ such that all states appear in $[\gamma_n,\omega^m\cdot\beta)$. Then not all states appear unboundedly often below $\gamma_n$. By the inductive hypothesis for the number of states applied to the intervals $[0,\gamma_0)$ and $[\gamma_n,\gamma_{n+1})$ for $n\in\omega$, there is a run $t\colon \omega^m\rightarrow \mathcal{S}$ with $t(<\omega^{m-1}\cdot n)=r(<\gamma_n)$ for all $n$. Then $t(<\omega^m)=r(<\omega^m\cdot \gamma)$. 
\qed \end{proof} 

\begin{corollary} Suppose $\mathcal{A}$ is a deterministic $\eta$-automaton with $<m$ states. Suppose $r$ is a run of $\mathcal{A}$ on empty input. Then $r(\omega^m)= r(\omega^m\cdot \beta)$ for all $\beta\geq 1$ with $\omega^m\cdot \beta<\eta$. 
\end{corollary} 

Let us consider $\mathbb{Z}^n$-automata. Here, $\mathbb{Z}^n$ is always linearly ordered by the right-lexicographical ordering, i.e. comparing the digits beginning from the rightmost one. We assume that $\mathbb{Z}^m\subseteq \mathbb{Z}^n$ for $m\leq n$ by identifying $(z_0,...,z_m)$ with $(z_0,...,z_m,0,...,0)\in\mathbb{Z}^n$. 

If $c=(X,Y)$ is a cut in a linear order $L$, let us write $c_{\mathrm{left}}=X$, $c_{\mathrm{right}}=Y$. 

\begin{lemma} Suppose $\mathcal{A}$ is a non-deterministic $\mathbb{Z}^n$-automaton with $\leq k$ states. Suppose $r\colon \mathbb{Z}^n\rightarrow \mathcal{S}$ is a run of $\mathcal{A}$ on empty input. 
\begin{enumerate} 
\item There is a strictly increasing sequence $(c_i)_{i\in\omega}$ of cuts in $\mathbb{Z}^{k+1}$ and a cut $c$ with $\sup_{i\in\omega} c_i=c$ and $r(c_i)=r(c)$ for all $i\in\omega$. 
\item For every cut $e$ with $type(c,e)$ a multiple of $type(c_0,c)$, there is a run $t\supseteq r\upharpoonright c_{\mathrm{left}}$ with $t(e)=r(c)$. 

\item There is an isomorphism from $(c_0,c)$ to $(c,e)$ mapping $r\upharpoonright (c_0,c)$ to $t\upharpoonright (c,e)$. 
\end{enumerate} 
\end{lemma} 




\subsection{Decomposition of 
  Shuffle-Automatic Structures}

Let $\alpha_1, \dots, \alpha_n$  {(\bf todo : what about countably many
$(\alpha_n)_{n\in\N}$?)}
be scattered linear orders with $\FC(\alpha_i)=\beta_i$, we denote by 
$\shuffle(\alpha_1, \dots, \alpha_n)$ the (countable) \emph{shuffle} of
$\alpha_1, \dots , \alpha_n$ which is 
$\sum_{q\in \Q} \alpha_{i_q}$ where for all $p<q\in \Q$ and all 
$1\leq j \leq n$ there is a $p<r<q$ such that $\alpha_{i_r} =
\alpha_j$ (The order type of the result is unique! {\bf todo find cite
  for this claim})

If $\alpha=\shuffle(\alpha_1, \dots, \alpha_n)$ for scattered
orders $\alpha_1, \dots, \alpha_n$ we call any
\mbox{$\alpha$-(oracle-)automatic} structure a 
\emph{shuffle-(oracle-)automatic structure}.
We study shuffles of scattered linear orders because they decompose
nicely as sums of scattered orders and open intervals which are
isomorphic to the whole shuffle. 
This property allows to prove a decomposition similar to that for
scattered-oracle-automatic structures. 

\begin{theorem} \label{thm:ShuffleDecomposition}
  Let $\alpha=\shuffle(\alpha_1, \dots, \alpha_n)$
  Let  $\Gf$ be 
  some finite-word-$\alpha$-automatic graph $(V,E)$
  where $E$ is recognised by some automaton $\Ac_E$ with state set
  $Q_E$ and 
  let $\Ac$ be a parameter automaton with state set $Q$. 
  There is
  \begin{itemize}%\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$
  \item a set $\Cc$ of $\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$
    many $\alpha$-automatic graphs
  \end{itemize}
  such that for each parameter $p$  the subgraph
  $\Gf_p$ is a tamely-colourable sum-augmentation of box-augmentations   
  of $(\Cc, \Dc_1, \Cc, \Dc_2, \dots, \Cc, \Dc_m, \Cc)$ where $m \leq
  \lvert \supp(p) \rvert$ and  
  $\Dc_1=\Dc_2=\dots=\Dc_m$ is the union  of  the
  $\alpha_i$-oracle-automatic graphs for all $1\leq i \leq n$. 
\end{theorem}
\begin{proof}
  Let $\alpha=\sum_{q\in Q} \alpha_{i_q}$ 
  Let $q_1<\dots<q_{m}\in \Q$ such that $\supp(p)$ is contained in the
  scattered orders associated with $q_1, \dots, q_m$ in the sense that
  or each $x\in \supp(p)$ there is a $1\leq i \leq m$ such that
  $x$ is between the cuts $\sum_{q<q_i} \alpha_{i_q}$ and
  $\sum_{q\leq q_i} \alpha_{i_q}$. 
  By definition, $\alpha$ is isomorphic to
  \begin{align*}
    \alpha + \alpha_{i_{q_1}} + \alpha + \alpha_{i_{q_2}} + \dots +
    \alpha + \alpha_{i_{q_m}} + \alpha.   
  \end{align*}
  For notational simplicity, we define
  \begin{align*}
    &\alpha_{p_0} = \alpha_{p_1} = \dots =\alpha_{p_m} = \alpha \text{
      and}\\
    &\alpha_{q_j}:=\alpha_{i_{q_j}}.  
  \end{align*}
  Induced by the decomposition of $\alpha$ there is a decomposition of 
  any $\alpha$-word $w$ as 
  \begin{align*}
    w = w_{p_0} w_{q_1} w_{p_1} \dots w_{q_m} w_{p_m}
  \end{align*}
  such that $w_{q_j}$ is an $\alpha_{i_{q_j}}$-word and
  $w_{p_j}$ is an $\alpha_{p_j}$-word. In particular, our parameter
  decomposes as
  \begin{align*}
    p = p_{p_0} p_{q_1} p_{p_1} \dots p_{q_m} p_{p_m}.
  \end{align*}
  Note that $p_{p_i}$ are empty $\alpha$-words for all $0\leq j \leq
  m$ whence they are
  independent of the concrete choice of the parameter $p$.
  
  In order to construct a sum and box decomposition of $\Gf_p$, we
  first define the building blocks. 
  For this purpose, we define equivalence relations 
  $\wordsim{p}{i}$ for each $i\in\{p_0, \dots, p_m, q_1, \dots,
  q_m\}$ on $\alpha_i$-words as follows.  
  For $\alpha_i$-words $w,w'$ set  $w \wordsim{p}{i} w'$ if and only if
  \begin{enumerate}
  \item for all $q,q'\in Q$ 
    $q \run{w\otimes p_i}{\Ac} q'  \Longleftrightarrow 
     q \run{w'\otimes p_i}{\Ac} q'$ and
   \item for all $q,q'\in Q_E$ 
    $q \run{w\otimes w}{\Ac_E} q'  \Longleftrightarrow 
     q \run{w'\otimes w'}{\Ac_E} q'$.
  \end{enumerate}
  Note that for fixed $i$ and $p$ there are at most 
  $2^{\lvert Q\times  Q\rvert+ 
    \lvert Q_E\times Q_E \rvert}$ many 
  $\wordsim{p}{i}$
  equivalence classes.   
  As domains of the building blocks of our
  decomposition we use   for each
  $\alpha_i$-word $w$ the sets
  \begin{equation*}
    K(i,w,p):=\{ x\mid x \wordsim{p}{i} w\}.
  \end{equation*}
  For each $M\subseteq Q_E\times Q_E$ we define a structure
  $\Kf^M(i,w,p)=(K(i,w,p), E^M)$ where
  $(w_1,w_2)\in E^M$ if 
  $w_1,w_2\in K(i,w,p)$ and there is a  $(q,q')\in M$ such that
  $q \run{w_1\otimes w_2}{\Ac_E} q'$.
  Note that $\Kf^M(q_j,w,p)$ is $\alpha_{q_j}$-oracle automatic with
  oracle $p_{q_j}$ for each $1\leq j \leq m$. Moreover, for all $0\leq
  j \leq m$ the structures $\Kf^M(p_j,w,p)$ are independent of $j$ and
  $p$, whence there are only finitely many. 
  Thus, 
  \begin{align*}
    \Cc:=\left\{\Kf^M(p_j,w,p)\mid M \subseteq Q_E\times Q_E, p
     \text{ a parameter}, 1\leq j \leq m  \right\}\\
  \end{align*}
  has each at most $\exp(\lvert Q \rvert^2+2\lvert Q_E\rvert^2)$ many
  elements (up to isomorphisms). 

  From now on, we proceed exactly as in the case of
  scattered-oracle-automatic structures. 
  
  Our next goal is the definition of the function $\eta$ that
  witnesses the decomposition claimed in this theorem. 
  For this purpose, let $\wordsim{p}{}$ denote the
  equivalence on 
  $\alpha$-words that is the product of the 
  $\wordsim{p}{i}$.\footnote{
    Thus,  for 
    $w=w_{p_0}w_{q_1}w_{p_1}\dots w_{q_m} w_{p_m}$ and
    $v=v_{p_0}v_{q_1}v_{p_1}\dots v_{q_m} v_{p_m}$ we have
    $w\wordsim{p}{} v$ iff
    $w_i\wordsim{p}{i} v_i$ for all 
    $i\in\{p_0, \dots, p_m, q_1, \dots, q_m\}$.
  }
  Now let
  \begin{align*}
    \eta: &\bigsqcup_{w\in V_p /{ \wordsim{p}{}}}
    K(p_0, w,p) \times \prod_{i=1}^{m} \big( K(q_i,w,p) \times
      K(p_i,w,p) \big)
    \longrightarrow V_p\\
    &(x_{p_0}, x_{q_1}, x_{p_1}, \dots, x_{q_m}, x_{p_m}) \mapsto 
    x := x_{p_0}x_{q_0} x_{p_1}\dots x_{p_m}x_{q_m}. 
  \end{align*}
  It follows from the definitions that $\eta$ is a well-defined
  bijection (using the fact that some $\alpha$-word $x$ belongs to
  $V_p$ iff there is a run 
  \begin{align*}
    q_I 
    \run{x_{p_0}\otimes p_{p_0}}{\Ac} q_1 
    \run{x_{q_1}\otimes p_{q_1}}{\Ac} q_2 \dots 
    q_{k-1} 
    \run{x_{q_m} \otimes p_{q_m}}{\Ac} q_k
    \run{x_{p_m} \otimes p_{p_m}}{\Ac} q_F    
  \end{align*}
  for some initial state $q_I$ and a final state $q_F$). 
  
  We finally prove that $\eta$ witnesses that $\Gf_p$ is a
  tamely-colourable sum-of-box augmentation of 
  $(\Cc, \Dc_1, \Cc, \Dc_2,  \dots, \Cc,  \Dc_m, \Cc)$.
  \begin{enumerate}
  \item Note that for each 
    $i\in \{p_0, \dots, p_m, q_1, \dots, q_m\}$ and for all
    $w= w_{p_0} w_{q_1} w_{p_1} \dots w_{q_m} w_{p_m}\in
    V_p$ the function
    \begin{align*}
    &\eta^{w}_i: K(i,w,p) \to  V_p\\
    & x_i \mapsto w_{p_0} w_{q_0} w_{p_1} \dots w_{r_i} x_i w_{r_{i+1}}
    \dots w_{q_m} w_{p_m}
    \end{align*}
    for $r_i=
    \begin{cases}
      q_j& \text{if } x_i=p_j,\\
      p_{j-1}& \text{if } x_i=q_j,
    \end{cases}$
    embeds $\Kf^M(i,w,p)$ into $\Gf_p$ where $M$ is defined by 
    \begin{equation}
      \label{eq:Shuffleboxelement}
    \begin{aligned}
      (q_1,q_2)\in M \Longleftrightarrow &\exists q_I\in I_E, q_F\in F_E
      \text{ such that}\\ 
      &q_I \run{ (w_{p_0}\dots w_{r_i}) \otimes
        (w_{p_0}\dots w_{r_i})}{ \Ac_E} q_1 \text{ and }
      q_2 \run{ (w_{r_{i+1}}\dots w_{p_m}) \otimes
        (w_{r_{i+1}}\dots w_{p_m})}{ \Ac_E} q_F.
    \end{aligned}
    \end{equation}
    This is true because
    \begin{align*}
      &\forall x_i,y_i\in K(i,w,p)\quad (x_i,y_i)\in E^M \\
      \Leftrightarrow &\exists (q_1,q_2)\in M \quad  q_1 \run{x_i\otimes
        y_i}{\Ac_E} q_2\\
      \overset{\eqref{eq:Shuffleboxelement}}{\Leftrightarrow} 
      &\exists q_I\in I_E, q_F\in F_E \quad
      q_I \run{ (w_{p_0}\dots w_{r_i}) \otimes
        (w_{p_0}\dots w_{r_i})}{ \Ac_E} q_1
      \run{x_i\otimes  y_i}{\Ac_E} q_2
      \run{ (w_{r_{i+1}}\dots w_{p_m}) \otimes
        (w_{r_{i+1}}\dots w_{p_m})}{ \Ac_E} q_F \\
      \Leftrightarrow 
      &\left(\eta^w_i(x_i), \eta^w_i(y_i)\right) \in E
    \end{align*}
  \item For all $i\in \{p_0, \dots, p_m, q_1, \dots, q_m\}$,
    all words $w,v\in V_p$, all $x_i\in K(i,w,p)$, and all $y_i\in
    K(i,v,p)$ set
    \begin{align*}
      c_i(x_i,y_i) := \{ (q,q')\in A_E \mid q\run{x_i\otimes
        y_i}{\Ac_E} q'\}.
    \end{align*}
    For $w,v\in V_p$ 
    the colours $c_i(w_i,v_i)$ determine whether $(w,v)\in E$ because
    \begin{align*}
    &(w_{p_0} w_{q_1} w_{p_1} \dots w_{q_m} w_{p_m},
    v_{p_0} v_{q_1} v_{p_1} \dots v_{q_m} v_{p_m})\in E\\
    \Longleftrightarrow 
    &\exists q_0, \dots, q_k\in Q_E \quad \left(
    \begin{aligned}
      &q_0\in I_E, q_k\in F_E,
      \text{ and } \\     
      &q_0 
      \run{w_{p_0}\otimes v_{p_0}}{\Ac_E} q_1 
      \run{w_{q_1}\otimes v_{q_1}}{\Ac_E} q_2     
      \run{w_{p_1}\otimes v_{p_1}}{\Ac_E} \dots  
      \run{w_{q_m}\otimes v_{q_m}}{\Ac_E} q_{k-1}
      \run{w_{p_m}\otimes v_{p_m}}{\Ac_E} q_k
    \end{aligned} \right)
    \\
    \Longleftrightarrow
    &\exists q_0, \dots, q_k\in Q_E \quad 
    \left(
      \begin{aligned}
        &q_0\in I_E, q_k\in F_E,   \text{ and }\\
        &(q_i,q_{i+1})\in c_j(w_j,v_j)        
       \text{ where } j=
        \begin{cases}
          p_k &\text{if }i=2k,\text{ and}\\
          q_k &\text{if } i=2k-1,
        \end{cases}
      \end{aligned} \right)
    \end{align*}
  \end{enumerate}
\qed \end{proof}



 

\subsection{Bounds for Forests on Shuffle Orders}
\label{sec:TreeboundShuffle}

Combining the ideas of the proofs of 
Theorem \ref{thm:Shuffle-BoundsonScatteredOrders} and
Theorem \ref{thm:BoundsOnTreeRanksDet} (second part), we can prove a
bound on the rank of shuffle-automatic forests.

\begin{theorem}
  Let $\alpha$ be the countable shuffle of $\alpha_1, \dots, \alpha_n$
  and let $\gamma=\max\{\FC(\alpha_i)\mid 1\leq i \leq n\}$. 
  If $\Ff$ is an $\alpha$-automatic forest, then 
  $\rank(\Ff) < \omega^{\omega \cdot (\gamma +2)}$.
  Moreover, if the set of finite $\alpha_i$-words admits a scattered
  $\alpha_i$-oracle-automatic linear order, then 
  $\rank(\Ff) < \omega^{\gamma + \omega}$. 
\end{theorem}
\begin{proof}
  {\bf todo spell this out analogously to the case of linear orders}
\qed \end{proof}





\begin{example}
    Is there a $\Q$-automatic tree of big rank ?$\rank$

  I think yes:

  Let $\Sigma = \{\diamond, 1, a, b\}$
  Define a tree $\Tf_1:=(T_1, \leq_1)$ where
  some finite $\Q$-word $w\in T_1$ iff
  $  w \in  \diamond^\Q (1 \{a,b,\diamond\}^\Q)^*$ such that
  \begin{enumerate}
  \item   $w$ ends with $1 \diamond^\Q$  or $w=\diamond^\Q$ and
  \item   for $w=\diamond^\Q1w_1 1w_2 1 \dots 1 w_m 1 \diamond^\Q$ we
    have 
    $w_i = \diamond^\Q$ then $w_{i-1}=\diamond^\Q$ for all $m\geq i>1$. 
  \end{enumerate}
 We define $<_1$ for 
 $w=\diamond^\Q1w_1 1w_2 1 \dots 1 w_m 1 \diamond^\Q$ and 
 $v=\diamond^\Q1v_1 1v_2 1 \dots 1 v_m 1 \diamond^\Q$
 by $w<_1 v$ if there are $k<j\leq m$ such that
 $ w_1=w_2=\dots =w_j=v_1=v_2=\dots v_k=\diamond^\Q$,
 $v_{k+1}\neq \diamond^\Q$, and $v_{j+1}=w_{j+1}, \dots, 
 v_m=w_m$. 

 Note that $\infrank( \diamond^\Q (1 \diamond^\Q)^k) = k-1$ and
 $\infrank(\diamond^\Q) =1$.

 We claim that $\Tf_1$ is $\Q$-automatic. 
 An automaton for $T_1$ is
 $\Ac_1=(Q, \Sigma_\diamond, q_i, F, \Delta)$ where
 $Q=\{q_i, q_w, q_n, q_f\}$, 
 $F=\{q_i,q_w,q_f\}$, 
 $\Sigma=\{1,a,b,\diamond\}$, and $\Delta$ is given by
 $(q_i, \diamond, q_i), \{q_i\} \to q_i, q_i\to \{q_i\}$, 
 $(q_i, 1, q_w), \{q_w\} \to q_w, q_w \to \{q_w\}$, 
 $(q_w, 1, q_w), (q_w, \diamond, q_w)$, 
 $(q_w, a, q_n), (q_w, b, q_n)$, 
 $\{q_n\} \to q_n, q_n \to \{q_n\}$, 
 $(q_n, \diamond, q_n), (q_n, a, q_n), (q_n, b, q_n)$, 
 $(q_n, 1, q_f)$, 
 $(q_f, \diamond, q_f)$,
 $(q_f, a, q_n), (q_f, b, q_n)$,
 $q_f\to\{q_f\}, \{q_f\} \to q_f$. 
 Explanation: $q_i$ before the first non-diamond letter
 this first letter is $1$!
 Then in $q_w$ wait for the first occurrence of $a$ or $b$. 
 With this, switch to $q_n$ in $q_n$ we stay reading diamond, a, or b
 until $1$ occurs, then we go to $q_f$ we accept in $q_f$ if only
 diamond follows, computation stops when $1$ occurs and we go back to
 $q_n$ when $a$ or $b$ occurs. 

 The automaton for $\Ac_{<_1}$ is constructed similarly. 

 
 Now we can lift the alphabet $\Sigma$ to $\Sigma=\{\diamond, a, b, 1,
 \dots, n\}$ in order to generate trees of rank $\omega^n$. 
 
 Idea, use words for $T_n$ of the form
 $w=\diamond^\Q 1 w_1 1 \dots w_m 1 \diamond^\Q$ where
 $w_i$ are $T_{n-1}$-words. 
 If $w_{i}$ is $\diamond^\Q$ then also $w_{i-1}$.
 Otherwise $w_{i+1}$ should be a leaf. 

 $w<_n v$ if $v$  if the minimal non-diamond $v_i$ satisfies
 ( $w_i$ is  below $v_i$ with respect to 
 $<_{n-1}$ 
 or $w_{i-1}$ is not $\diamond^Q$ but $v_{i-1}$ is)
 and $w_{i+1}=v_{i+1} \dots w_m =v_m$.  

 Claim: $\Tf_n$ has rank $\omega^n$. Idea, for each $c$ there is a
 subtree that consists of a $c$-fold iteration of $\Tf_{n-1}$. 

 

 {\bf todo spell it out more detailed!}

\end{example}
\begin{problem}
 Does this lift to $\sum_\Q \alpha$ for $\alpha\geq 1$ some ordinal?
\end{problem}


\begin{problem} \begin{enumerate} 
\item Is there an $\alpha$-automatic scattered linear order on the set of $\alpha$-words for every scattered linear order $\alpha$? 
\item Is there, for every $k$, some $n$ such that no scattered linear order on the set of finite $\mathbb{Z}^n$-words is recognised by a $\mathbb{Z}^n$-automaton with $\leq k$ states? 
\item Let $\mathcal{C}_n$ denote the set of all $\Sigma$-trees (see\marginpar{cite} Jain-Khoussainov-Schlicht-Stephan) whose branching nodes contain at most $n$ $1$'s. Is there, for every $k$, some $n$ such that no tree-automatic scattered linear order on $\mathcal{C}_n$ recognised by a tree automaton with $\leq k$ states? 
\end{enumerate} 
\end{problem} 

We describe a partial result for the second question. It is more convenient to consider an automaton $\mathcal{A}_<$ with three sets $\mathcal{S}_<$, $\mathcal{S}_=$, $\mathcal{S}_>$ of states such that $u<v$, $u=v$, or $u>v$ if the final state is in $\mathcal{S}_<$, $\mathcal{S}_=$, or $\mathcal{S}_>$. 

\begin{lemma} Suppose $L$ is the set of finite $\mathbb{Z}^n$-words and $(L,<)$ is a linear order. Suppose $\mathcal{A}_<$ is a nondeterministic $\mathbb{Z}^n$-automaton recognising $<$. 




\begin{enumerate} 
\item Suppose $\mathcal{A}_<$ is a $\mathbb{Z}$-automaton recognising $L$. Moreover, suppose $|\mathsf{range}(\sigma)|$, $|\mathsf{range}(\tau)|$, $|\mathsf{range}(\nu)|\in \{1,n\}$ for $n=|\mathcal{S}_{\neq}|$. 
Then there is $w\in \Sigma^*$ such that $(\Sigma_w,<)\cong (\mathbb{Q},<)$ or $(\Sigma_w,>)\cong (\mathbb{Q},<)$. 
\item Suppose $\mathcal{A}$ is a $\mathbb{Z}^n$-automaton with $\leq k$ states. Suppose $x<y$ in $\mathbb{Z}^n$ and $d(x,y)\geq k+1$. Suppose $i\leq x$ for every $i\in \mathsf{supp}(w)$. Moreover, suppose 


\item Suppose that $<$ is a linear order on the set of finite $\mathbb{Z}^3$-words and $A_{<}$ is a $\mathbb{Z}^3$-automaton recognising $<$. Moreover, suppose $|\mathcal{S}_{<}|=|\mathcal{S}_{>}|=1$. Then $<$ is not scattered. 
\end{enumerate} 
\end{lemma} 

\begin{proof} (1) 

By a finite $\mathbb{Z}$-automaton, we mean a $\mathbb{Z}$-automaton which reads a finite $\mathbb{Z}$-word and $w$ from $\min (\mathsf{supp}(w))$ to $\max(\mathsf{supp}(w))$. Let $\Sigma =\{1\}$. Suppose $L$ is the set of finite $\mathbb{Z}$-words and $<$ is a linear order on $L$. Suppose $A_{<}$ is a deterministic $\mathbb{Z}$-automaton finite $\mathbb{Z}$-automaton with states in $\mathcal{S}_{<}\sqcup \mathcal{S}_{=}\sqcup \mathcal{S}_{>}$ corresponding to the final states for deciding whether $v<w$, $v=w$, or $v>w$ for $v,w\in L$. Let $\mathcal{S}_{\neq}=\mathcal{S}_{<}\sqcup \mathcal{S}_{>}$. Moreover, suppose the input $(\diamond,\diamond)$ does not change the state. Then after input of the first pair $(\diamond,\diamond)$, $(\diamond, 1)$, or $(1,1)$, the state is in $\mathcal{S}_{\neq}$ and does not leave $\mathcal{S}_{\neq}$. Then $(1,\diamond)$, $(\diamond, 1)$, and $(1,1)$ define functions $\sigma,\tau, \nu\colon \mathcal{S}_{\neq}\rightarrow S_{\neq}$. 

Suppose $w\in \Sigma^*$. Let $\Sigma_{w}$ denote the set of finite $\mathbb{Z}$-words $u=\diamond^{\omega^*}w^{n_0}\diamond^{n n_1} w^{n_2} \diamond^{n n_3} ... w^{n_k}\diamond ^{\omega}$ such that $|w|$ divides $\min(\mathsf{supp}(u))$. 


(2) 


\qed \end{proof} 






\section{Ranks of Scattered-Automatic 
  Well-Founded 
  Partial Orders}

We call a partial order $\Pf$ a \emph{well-founded upwards linear partial
  order} (or wulpo for short), if it is well-founded and upwards
linear in the sense that for each  $p\in\Pf$ the induced order
$\Pf{\restriction}_{\{x\mid p<x\}}$ is linear.  This is a common
generalisation of well-founded forests and of ordinals. 
  
In \cite{HuKaLiLo12Arxiv}, an careful analysis of tamely-colourable
sum-augmentation box-augmentation of wulpo's was carried out.
With a careful look at the proofs, we obtain the following theorem. 

\begin{theorem} \label{thm:Wulpotrank-indecomposable}
  \cite{HuKaLiLo12Arxiv}
  If $\Pf$ is a wulpo of rank $\omega^\beta$ for some ordinal
  $\beta$ such that $\Pf$ is tamely-colourable sum-augmentation of
  box-augmentations of classes $\Cc_1, \dots, \Cc_k$, 
  then there is a substructure $\Pf'\subseteq \Pf$ 
  and structures $\Cf_1\in \Cc_1, \dots, \Cf_k\in \Cc_k$ 
  such that $\Pf'$ is  tamely-colourable box-augmentation of $\Cf_1,
  \dots, \Cf_k$ and  $\rank(\Pf')= \rank(\Pf)$. 
  Moreover, if $\rank(\Cf_i) < \beta_i$, 
  then 
  $\rank(\Pf') \leq \beta_1 \otimes \dots\otimes \beta_n \otimes c$
  for some constant $c < \omega$.  
\end{theorem}

We derive the following theorem for wulpos that are $\alpha$-oracle
automatic. 

\begin{theorem}\label{thm:BoundsOnWulpos}
  For a scattered linear order $\alpha$ with 
  $\FC(\alpha)= 1+ \gamma$, 
  every $\alpha$-oracle-automatic wulpo has rank
  strictly below $\omega^{\omega^{\gamma+1}}$.
\end{theorem}
\begin{proof}
  For $\gamma=0$, every $\alpha$-oracle-automatic wulpo is finite
  whence its rank is strictly below
  $\omega=\omega^1=\omega^{\omega^\gamma}$.  
  
  We proceed by induction on $\gamma$. 
  Let $\alpha$ be  a scattered linear order of $\FC$ rank
  $1+\gamma>0$. 
  Heading for a contradiction assume that $\Pf$ is a
  $\alpha$-oracle-automatic wulpo of rank
  at least $\omega^{\omega^{\gamma+1}}$.
  Then there is a parameter automaton $\Ac$ (corresponding to the
  formula $x<y$ and parameters $p_n$ for $n\in\N$ such that
  $\rank(\Pf_{p_n}) = \omega^{\omega^{\gamma} \cdot n}$. 
  Assume that $\Ac$ has $q$ many states and the order automaton of
  $\Ff$ has $q_<$ many states. 
  Now fix $n_0 = 2^{3\cdot \exp(q^2+2q_<^2)}$. 
  Due to Theorem \ref{thm:Decomposition}, 
  there are sets
  $\Cc_0, \Cc_1$ of size $\exp(q^2+2q_<^2)$
  such that for each $n\leq n_0$, $\Pf_{p_n}$ is a tamely-colourable
  sum-augmentation of box-augmentations of $\Cc_0, \Cc_1$ and 
  some sets  of $\beta_i$-oracle-automatic structures where
  $\FC(\beta_i)< 1+ \gamma$ for each $i$.
  By choice of $n_0$, there is some $m\in\N\setminus\{0\}$ such that
  $2m \leq n_0$ and 
  \begin{equation}
    \label{eq:FCRankGapswulpo}
    \begin{aligned}
      &\rank(\Af) < \omega^{\omega^{\gamma} \cdot m}\text{ or}\\
      &\rank(\Af) > \omega^{\omega^{\gamma} \cdot 2m}   
    \end{aligned}
  \end{equation}
  for all  structures  $\Af\in \Cc_0\cup \Cc_1$.
  Moreover, by induction hypothesis, every $\beta_i$-oracle-automatic
  wulpo has rank strictly below 
  $\omega^{\omega^{\FC(\beta_i)}}\leq \omega^{\omega^{\gamma}}$. 
  Thus, $\Ff_{p_{2m+1}}$ is a tamely-colourable sum-augmentation of
  box-augmentations of classes of structures such that none of these
  structures has $\rank$ between $\omega^{\omega^{\gamma}\cdot m}$ and
  $\omega^{ \omega^{\gamma} \cdot 2m}$. 
  Due to Theorem \ref{thm:treerank-indecomposable}, 
  There are substructures $\Ff'_{p_{2m+1}}, \Cf_0, \dots, \Cf_1, \Bf_1,
  \dots, \Bf_k$ of $\Ff_{p_{2m+1}}$ such that
  $\rank(\Ff'_{p_{2m+1}})=\rank(\Ff_{p_{2m+1}})
  =\omega^{\omega^{\gamma}\cdot (2m+1)}$ and 
  $\Ff'_{p_{2m+1}}$ is tamely-colourable box-augmentation of 
  $\Cf_0, \Cf_1, \Bf_1, \dots, \Bf_k$ where $\Cf_i\in\Cc_i$ and
  $\Bf_i$ is $\beta_i$-oracle-automatic for some
  $\beta_i$ with $\FC(\beta_i)< 1+\gamma$.  
  Due to \ref{eq:FCRankGapswulpo} all these substructure satisfy
  $\rank(\Cf_i) < \omega^{\omega^{\gamma} \cdot m}$ and
  $\rank(\Bf_i) < \omega^{\omega^{\gamma}}$ whence
  by Theorem \ref{thm:Wulpotrank-indecomposable}
  \begin{align*}
    &\rank(\Pf'_{p_{2m+1}}) \leq \omega^{\omega^{\gamma}\cdot m}
    \otimes \omega^{\omega^{\gamma}\cdot m} \otimes \delta 
    \text{  for}\\
    &\delta :=(\rank(\Bf_1)+1) \otimes (\rank(\Bf_2)+1) 
    \otimes \dots \otimes  (\rank(\Bf_k)+1)
  \end{align*}
  Since $\delta<\omega^{\omega^{\gamma}}$, 
  we conclude that
  \begin{align*}
    \rank((\Pf'_{p_{2m+1}}) \leq \omega^{\omega^{\gamma}\cdot 2m}
    \otimes \delta < \omega^{\omega^{\gamma}\cdot (2m+1)}, 
  \end{align*}
  which clearly contradicts the fact that  parameter $p_{2m+1}$
  induces a substructure 
  $\Pf_{p_{2m+1}}$ of rank 
  $\rank(\Pf_{p_{2m+1}}) = \omega^{\omega^{\gamma}\cdot (2m+1)} = 
  \rank(\Pf'_{p_{2m+1}})$.
\qed \end{proof}


Unfortunately, there is no hope to lift the decomposition technique of
Delhomm{\'{e}} to all $\alpha$-automatic well-founded partial
orders. Partial orders of any rank decompose as the box of $2$
antichains, i.e., of substructures of rank $1$. 
\begin{example}
  Let $(\alpha, \subseteq)$ be an arbitrary ordinal. 
  Let $(\beta, \subseteq)$ be an infinite ordinal.
  We now define a partial order 
  $\Pf=(\alpha\times \beta, \sqsubseteq)$ by
  $(a,b) \sqsubset (a',b')$ if
  $a \subseteq a'$ and $b' \subseteq b$. 
  Note that $\Pf$ is well-founded because $\alpha$ is. 
  Moreover, $\Pf$ is box-augmentation of the antichains.
  $(\alpha, =)$ and $(\beta, =)$.
  It is easy to prove that $\rank( (a,b), \Pf) = \rank(a,\alpha)$
  whence the ranks of $\Pf$ and $\alpha$ coincide. 
  Thus, partial orders of arbitrary  rank can decompose as
  box-augmentations of rank $1$ structures. Moreover, if $\alpha <
  \omega^{\gamma+1}$, then $\Pf$ is $\omega^{1+\gamma}$-automatic. 
\end{example}
This example shows that there is no hope to improve Delhomm{\'{e}}'s
decomposition result in order to obtain bounds on the ranks of
well-founded partial orders. 












V4.2Scattered-Automatic-Structures.bbl
\begin{thebibliography}{10}

\bibitem{BGR11}
Vince B{\'a}r{\'a}ny, Erich Gr{\"a}del, and Sasha Rubin.
\newblock Automata-based presentations of infinite structures.
\newblock In Javier Esparza, Christian Michaux, and Charles Steinhorn, editors,
  {\em {Finite and Algorithmic Model Theory}}, pages 1--76. Cambridge
  University Press, March 2011.

\bibitem{BedonBesCartonRispal2010}
Nicolas Bedon, Alexis B{\`e}s, Olivier Carton, and Chlo{\'e} Rispal.
\newblock Logic and rational languages of words indexed by linear orderings.
\newblock {\em Theory Comput. Syst.}, 46(4):737--760, 2010.

\bibitem{BLumensath1999}
A.~Blumensath.
\newblock Automatic structures. {Diploma} thesis, {RWTH A}achen, 1999.

\bibitem{BruyereC01}
V{\'e}ronique Bruy{\`e}re and Olivier Carton.
\newblock Automata on linear orderings.
\newblock In Jiri Sgall, Ales Pultr, and Petr Kolman, editors, {\em MFCS}, Vol.
  2136 of LNCS, pages 236--247. Springer, 2001.

\bibitem{Delhomme04}
C.~Delhomm{\'e}.
\newblock Automaticit{\'e} des ordinaux et des graphes homog{\`e}nes.
\newblock {\em C.R. Acad. Sci. Paris Ser. I}, 339:5--10, 2004.

\bibitem{FinkelT12}
Olivier Finkel and Stevo Todorcevic.
\newblock Automatic ordinals.
\newblock {\em CoRR}, abs/1205.1775, 2012.

\bibitem{Huschenbett12}
Martin Huschenbett.
\newblock The rank of tree-automatic linear orderings.
\newblock {\em CoRR}, abs/1204.3048, 2012.

\bibitem{Huschenbett13}
Martin Huschenbett.
\newblock The rank of tree-automatic linear orderings.
\newblock In Natacha Portier and Thomas Wilke, editors, {\em STACS}, volume~20
  of {\em LIPIcs}, pages 586--597. Schloss Dagstuhl - Leibniz-Zentrum fuer
  Informatik, 2013.

\bibitem{KaLiLo12}
Alexander Kartzow, Jiamou Liu, and Markus Lohrey.
\newblock Tree-automatic well-founded trees.
\newblock In {\em Proc. CIE 2012}, LNCS. Springer-Verlag, 2012.

\bibitem{DBLP:journals/apal/KhoussainovM09}
B.~Khoussainov and M.~Minnes.
\newblock Model-theoretic complexity of automatic structures.
\newblock {\em Ann. Pure Appl. Logic}, 161(3):416--426, 2009.

\bibitem{KhoussainovN94}
B.~Khoussainov and A.~Nerode.
\newblock Automatic presentations of structures.
\newblock In {\em LCC}, pages 367--392, 1994.

\bibitem{DBLP:journals/lmcs/KhoussainovNRS07}
B.~Khoussainov, A.~Nies, S.~Rubin, and F.~Stephan.
\newblock Automatic structures: Richness and limitations.
\newblock {\em Logical Methods in Computer Science}, 3(2), 2007.

\bibitem{KhoussainovRS05}
Bakhadyr Khoussainov, Sasha Rubin, and Frank Stephan.
\newblock Automatic linear orders and trees.
\newblock {\em ACM Trans. Comput. Log.}, 6(4):675--700, 2005.

\bibitem{KuLiLo11}
Dietrich Kuske, Jiamou Liu, and Markus Lohrey.
\newblock The isomorphism problem on classes of automatic structures with
  transitive relations.
\newblock to appear in {\em Transactions of the American Mathematical Society},
  2011.

\bibitem{RispalC05}
Chloe Rispal and Olivier Carton.
\newblock Complementation of rational sets on countable scattered linear
  orderings.
\newblock {\em Int. J. Found. Comput. Sci.}, 16(4):767--786, 2005.

\bibitem{rosenstein82}
Joseph~G. Rosenstein.
\newblock {\em Linear Ordering}.
\newblock Academic Press, 1982.

\bibitem{SchlichtS11}
Philipp Schlicht and Frank Stephan.
\newblock Automata on ordinals and automaticity of linear orders.
\newblock {\em Annals of Pure and Applied Logic}, 164(5):523 -- 527, 2013.

\end{thebibliography}
