# A new similarity law for transonic-supersonic flow

Luoqin Liu<EMAIL_ADDRESS>Physics of Fluids Group, Max Planck Center
Twente for Complex Fluid Dynamics, University of Twente, 7500 AE Enschede, The
Netherlands

###### Abstract

How to determine accurately and efficiently the aerodynamic forces of the
aircraft in high-speed flow is one of great challenges in modern aerodynamics.
In this Letter we propose a new similarity law for steady transonic-supersonic
flow over thin bodies. The new similarity law is based on the local Mach
number frozen principle. It depends on both the specific heat ratio and the
free-stream Mach number. The new similarity law enables one to determine the
lift and drag coefficients of the aircraft from that of a reference state
which is more reachable. The validity of the new similarity law has been
confirmed by the excellent agreement with numerical simulations of both two-
dimensional airfoil flows and three-dimensional wing flows.

###### keywords:

Similarity law, transonic flow, supersonic flow, lift, drag

Introduction. The similarity laws of aerodynamics were developed starting in
the twenties of the last century [1, 2, 6, 8, 3]. They were usually obtained
by solving the steady full potential equation, either through linearization
approach [1, 2, 6] or hodograph transformation [8]. However, as the simplified
full potential equation has different mathematical properties at subsonic,
transonic, and supersonic flows, these similarity laws are valid only over a
certain range of Mach number and cannot transform smoothly from one to
another. In this Letter we derive a new similarity law for steady high-speed
flow over thin bodies. Instead of solving the full potential equation, the
derivation is based on the local Mach-number frozen principle. Therefore, the
new similarity law holds for both transonic and supersonic flows, provided
that subsonic and supersonic regimes coexist on the aircraft surfaces. The
validity of the proposed similarity law is confirmed by the numerical
simulations of steady flows over a two-dimensional airfoil and a three-
dimensional wing.

Similarity law. Consider the steady flow of perfect gas over a thin airfoil.
The pressure coefficient $C_{p}$ on the airfoil surface is defined by

$C_{p}=\frac{p-p_{\infty}}{\frac{1}{2}\rho_{\infty}U_{\infty}^{2}}=\frac{2}{\gamma
M_{\infty}^{2}}\left(\frac{p}{p_{\infty}}-1\right),$ (1)

where the subscript $\infty$ denotes the value at infinity of upstream, $p$ is
the pressure, $\rho$ is the density, $U$ is the velocity magnitude, $\gamma$
is the specific heat ratio, and $M$ is the Mach number. The pressure $p$ is
related to the stagnation pressure $p_{0}$, namely

$\frac{p_{0}}{p}=\left(1+\frac{\gamma-1}{2}M^{2}\right)^{\frac{\gamma}{\gamma-1}}.$
(2)

For isentropic flows, the stagnation pressure on the body surface is the same
as that at far upstream. For flows with only weak shocks, the variance of
stagnation pressure is only a third-order small term [4]. These two facts
enable us to neglect the variance of stagnation pressure. Thus,

$C_{p}=\frac{2}{\gamma
M_{\infty}^{2}}\left\\{\left[\frac{2+(\gamma-1)M_{\infty}^{2}}{2+(\gamma-1)M^{2}}\right]^{\frac{\gamma}{\gamma-1}}-1\right\\}.$
(3)

To calculate $\textrm{d}C_{p}/\textrm{d}M_{\infty}$, we rewrite (3) as

$\ln\left(1+\frac{\gamma
M_{\infty}^{2}}{2}C_{p}\right)=\frac{\gamma}{\gamma-1}\ln\left[\frac{2+(\gamma-1)M_{\infty}^{2}}{2+(\gamma-1)M^{2}}\right].$
(4)

Differentiating equation (4) with respect to $M_{\infty}$, there is

$\begin{split}&\frac{\textrm{d}C_{p}}{\textrm{d}M_{\infty}}=\frac{2}{M_{\infty}}\frac{2-(2-M_{\infty}^{2})C_{p}}{2+(\gamma-1)M_{\infty}^{2}}-\left(C_{p}+\frac{2}{\gamma
M_{\infty}^{2}}\right)\frac{2\gamma
M}{2+(\gamma-1)M_{\infty}^{2}}\frac{\textrm{d}M}{\textrm{d}M_{\infty}}.\end{split}$
(5)

On the one hand, the local Mach-number frozen principle states that $M$
becomes stationary as $M_{\infty}$ passes through unity [4, 7],

$\left(\frac{\textrm{d}M}{\textrm{d}M_{\infty}}\right)_{M_{\infty}=1}=0.$ (6)

This fact enables us to safely neglect the second term in the right hand side
of equation (5), provided that $M_{\infty}$ is large enough such that
supersonic and subsonic zones coexist on the body surface. On the other hand,
to simplify the integration procedure, we set $M_{\infty}=1$ in the first term
of equation (5). Thus, equation (5) can be approximated as

$\frac{\textrm{d}C_{p}}{\textrm{d}M_{\infty}}=\frac{2}{\gamma+1}\left(2-C_{p}\right).$
(7)

This is a first-order ordinary differential equation for the pressure
coefficient. Note that equation (7) is exactly valid at $M_{\infty}=1$ [4, 7].
But now we presumably that it is also approximately valid in the vicinity of
$M_{\infty}$.

The lift coefficient is calculated as

$C_{l}(M_{\infty})=\frac{1}{c}\int_{0}^{c}(C_{p,L}-C_{p,U})\textrm{d}x,$ (8)

where $c$ is the chord length, and the subscripts $L$ and $U$ denote the lower
and upper airfoil surfaces. From the mean value theorem, equation (8) can be
integrated as

$C_{l}(M_{\infty})=C_{p}(M_{L};M_{\infty})-C_{p}(M_{U};M_{\infty}),$ (9)

where $M_{L}$ and $M_{U}$ are the characteristic Mach numbers on the lower and
upper airfoil surfaces, respectively. Combining equations (7) and (9), we get
a first-order ordinary differential equation for the lift coefficient,

$\frac{\textrm{d}C_{l}}{\textrm{d}M_{\infty}}=-\frac{2}{\gamma+1}C_{l}.$ (10)

The solution of equation (10) is

$\frac{C_{l}}{C_{l,\sqrt{2}}}=\exp\left[\frac{2}{\gamma+1}\left(\sqrt{2}-M_{\infty}\right)\right],$
(11)

where $C_{l,\sqrt{2}}$ is the lift coefficient of the aircraft at the
reference state $M_{\infty}=\sqrt{2}$. Note that in thin airfoil theory
$C_{l,\sqrt{2}}=4\alpha_{0}$, where $\alpha_{0}$ is incident angle of the free
stream [4].

Following Ramm [7], the drag coefficient $C_{d}$ can be written as

$C_{d}(M_{\infty})=\frac{1}{2h}\int_{-h}^{h}\alpha(y)C_{p}(M(y);M_{\infty})\textrm{d}y,$
(12)

where $h$ is the half-thickness of the airfoil and $\alpha$ is the local angle
of attack. From the mean value theorem, equation (12) can be writen as

$C_{d}(M_{\infty})=\bar{\alpha}C_{p}(M_{d};M_{\infty}),$ (13)

where $M_{d}$ is a characteristic Mach number related to the drag coefficient,
and

$\bar{\alpha}=\frac{1}{2h}\int_{-h}^{h}\alpha(y)\textrm{d}y$ (14)

is the mean value of the angle of attack. We emphasis that for shock-free flow
there is $\bar{\alpha}=\alpha_{0}$. For shock flow, however, both shock wave
induced flow separation and shock wave increased wake width will increase the
drag, and thus $\bar{\alpha}\neq\alpha_{0}$. In general, $\bar{\alpha}$ should
depend on both $M_{\infty}$ and $\alpha_{0}$. For simplicity, we assume it is
independent of $M_{\infty}$. Then, from equations (7) and (13) we obtain a
first-order ordinary differential equation for the drag coefficient,

$\frac{\textrm{d}C_{d}}{\textrm{d}M_{\infty}}=\frac{2}{\gamma+1}\left(2\bar{\alpha}-C_{d}\right).$
(15)

The solution of equation (15) is

$\frac{C_{d}-2\bar{\alpha}}{C_{d,\sqrt{2}}-2\bar{\alpha}}=\exp\left[\frac{2}{\gamma+1}(\sqrt{2}-M_{\infty})\right],$
(16)

where $C_{d,\sqrt{2}}$ is the drag coefficient of the aircraft at the
reference state $M\infty=\sqrt{2}$. Note that in thin airfoil theory
$C_{d,\sqrt{2}}=4\alpha_{0}^{2}$ [4].

We remark that, the new similarity law for the lift coefficient (11) and the
drag coefficient (16) has a unique feature compared to existing similarity
laws [1, 2, 6, 8, 3]. That is, the new similarity law depends on
$M_{\infty}^{1}$ while the existing ones depend on $M_{\infty}^{2}$. Similar
to the existing transonic similarity laws [e.g., 3], the new similarity law
also depends on the specific heat ratio $\gamma$. Besides, the new similarity
law for the drag coefficient (16) has considered the effects of shock-induced
flow separation and shock-increased wake width. In addition, although the new
similarity law of equations (11) and (16) is derived for two-dimensional thin
airfoils, it is also valid for three-dimensional thin wings. This is because
the essential assumption of the derivation is based on the local Mach number
frozen principle, which is independent of the dimensionality of the aircraft
and the space.

Numerical validation. To verify the correctness of the new similarity law
given by equations (11) and (16) for transonic-supersonic flow, comparisons
with the numerical results are made for steady viscous and compressible flows
over both a two-dimensional airfoil and a three-dimensional wing. In two
dimensions, Liu et al. [5] performed a series of Reynolds-averaged Navier-
Stokes simulations of the flow over an RAE-2822 airfoil. In these simulations,
the Reynolds number is $Re=6.5\times 10^{6}$, and two angles of attack are
considered, namely $\alpha_{0}=2.31^{\circ}$ and $5.00^{\circ}$. The
simulations were performed by the OpenCFD-EC2D-1.5.4 program developed by
Professor Xinliang Li of the Chinese Academy of Sciences. More details of the
simulations can be found in Liu et al. [5]. In three dimensions, Vinh [9]
performed a series of large eddy simulations of the flow over an isolate wing.
In these simulations, the Reynolds number is about $Re=5.0\times 10^{5}$ and
the angle of attack is $\alpha_{0}=20.0^{\circ}$. The simulations were
performed with the commercial software package ANSYS. More details of the
simulations can be found in Vinh [9].

Figure 1 shows the comparison of the new similarity law for the lift
coefficient given by equation (11) and the numerical simulations performed by
Liu et al. [5] and Vinh [9]. Also shown is the theoretical prediction of the
Ackeret law [1],

$\frac{C_{l}}{C_{l,\sqrt{2}}}=\frac{C_{d}}{C_{d,\sqrt{2}}}=\frac{1}{\sqrt{M_{\infty}^{2}-1}}.$
(17)

Note that the theoretical results obtained from both the new similarity law
for the lift coefficient given by equation (11) and the Ackeret law given by
equation (17) agree excellently with the numerical results at the supersonic
regime $M_{\infty}\geq 1.4$. But at the transonic regime $0.9\leq
M_{\infty}\leq 1.3$, only the new similarity law agrees well with the
numerical results. This result shows the superiority of the new similarity law
over the Ackeret law.

Figure 1: Mach-number dependence of the lift coefficient of a two-dimensional
airfoil and a three-dimensional wing. Filled circles: numerical results with
$\alpha_{0}=2.31^{\circ}$ performed by Liu et al. [5]; filled squares:
numerical results with $\alpha_{0}=5.00^{\circ}$ performed by Liu et al. [5];
filled triangles: numerical results with $\alpha_{0}=20.0^{\circ}$ performed
by Vinh [9]; dashed-dotted line: the prediction of the Ackeret law given by
equation (17); solid line: the prediction of the new similarity law given by
equation (11).  Figure 2: Mach-number dependence of the drag coefficient of a
two-dimensional airfoil and a three-dimensional wing. Filled circles:
numerical results with $\alpha_{0}=2.31^{\circ}$ performed by Liu et al. [5];
filled squares: numerical results with $\alpha_{0}=5.00^{\circ}$ performed by
Liu et al. [5]; filled triangles: numerical results with
$\alpha_{0}=20.0^{\circ}$ performed by Vinh [9]; dashed-dotted line: the
prediction of the Ackeret law given by equation (17); solid line: the
prediction of the new similarity law given by equation (16) with
$\bar{\alpha}=0.03$.

Figure 2 shows the comparison of the new similarity law for the drag
coefficient given by equation (16) and the numerical simulation performed by
Liu et al. [5] and Vinh [9]. Also shown is the theoretical prediction of the
Ackeret lawgiven by equation (17). Note that the theoretical results obtained
from both the new similarity law for the drag coefficient given by equation
(16) with $\bar{\alpha}=0.03$ and the Ackeret law given by equation (17) agree
excellently with the numerical results at the supersonic regime
$M_{\infty}\geq 1.4$. But at the transonic regime $0.9\leq M_{\infty}\leq
1.3$, only the new similarity law agrees well with the numerical results. Note
that the normalized drag coefficient
$(C_{d}-2\bar{\alpha})/(C_{d,\sqrt{2}}-2\bar{\alpha})$ of the three-
dimensional wing at $M_{\infty}=1.2$ falls accidentally on the curve of the
Ackeret law. The reason for this isolate point is not known yet since we don’t
know the details of the simulation. Therefore, more careful simulations of
three-dimensional thin bodies are helpful to further evaluate the performance
of the new similarity law for the drag coefficient. Nevertheless, since all
other points of the three-dimensional wing (including the sonic point at
$M_{\infty}=1$) and all points of the two-dimensional airfoil nearly collapse
to the curve of the new similarity law, we confirm once more the superiority
of the new similarity law over the Ackeret law.

Conclusions. In this Letter we propose a new similarity law for high-speed
flow over thin bodies. The new similarity law is based on the local Mach
number frozen principle and thus is valid for both transonic and supersonic
flows. In contrast to existing similarity laws which depend on the square of
free-stream Mach number $M_{\infty}^{2}$, the new similarity law depends on
$M_{\infty}^{1}$. Similar to the existing transonic similarity laws, the new
similarity law also depends on the specific heat ratio $\gamma$. The new
similarity law enables one to determine the lift and drag coefficients of the
aircraft in steady transonic-supersonic flow from that of a reference state.
The validity of the new similarity law has been confirmed by the excellent
agreement with numerical simulations of the flow over both a two-dimensional
airfoil and a three-dimensional wing.

## Acknowledgments

The author is grateful to Prof. Jiezhi Wu for insightful discussions. The
author acknowledges Dr. Shufan Zou for providing the literature of wing
simulations.

## References

  * Ackeret [1925] Ackeret, J. (1925).  Air forces on airfoils moving faster than sound.  J. Aviation Eng. Motorized-Airship Aeronaut., 16, 72–74.
  * Glauert [1928] Glauert, H. (1928).  The effect of compressibility on the lift of an aerofoil.  Proc. R. Soc. Lond. A, 118, 113–119.
  * von Kármán [1947] von Kármán, T. (1947).  The similarity law of transonic flow.  J. Math. Phys., 16, 182–190.
  * Liepmann & Roshko [1957] Liepmann, H., & Roshko, A. (1957).  Elements of Gasdynamics.  New York: Wiley.
  * Liu et al. [2015] Liu, L. Q., Zhu, J. Y., & Wu, J. Z. (2015).  Lift and drag in two-dimensional steady viscous and compressible flow.  J. Fluid Mech., 784, 304–341.
  * Prandtl [1930] Prandtl, L. (1930).  On flows whose velocities are comparable to the velocity of sound.  J. Aeronaut. Res. Inst., 5, 25–34.
  * Ramm [1990] Ramm, H. J. (1990).  Fluid Dynamics for the Study of Transonic Flow.  Oxford: Oxford University Press.
  * Tsien [1939] Tsien, H. S. (1939).  Two-dimensional subsonic flow of compressible fluids.  J. Aeronaut. Sci., 6, 399–407.
  * Vinh [2015] Vinh, N. Q. (2015).  Determination of the aerodynamic characteristics of flying vehicles using method large eddy simulation with software ANSYS.  Automation, Control and Intelligent Systems, 3, 118–123.


15411 LABEL:LastPageApr. 19, 2018Nov. 27, 2019

Research supported by the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (ERC consolidator grant
LIPA, agreement no. 683080).

#  A non-regular language of infinite trees
that is recognized by a sort-wise finite algebra

Mikołaj Bojańczyk  University of Warsaw<EMAIL_ADDRESS>and  Bartek Klin
University of Warsaw<EMAIL_ADDRESS>
###### Abstract.

$\omega$-clones are multi-sorted structures that naturally emerge as algebras
for infinite trees, just as $\omega$-semigroups are convenient algebras for
infinite words. In the algebraic theory of languages, one hopes that a
language is regular if and only if it is recognized by an algebra that is
finite in some simple sense. We show that, for infinite trees, the situation
is not so simple: there exists an $\omega$-clone that is finite on every sort
and finitely generated, but recognizes a non-regular language.

###### Key words and phrases:

algebraic language theory, infinite tree, $\omega$-clone

##  1\. Introduction

The central theme in the algebraic theory of languages is that regular
languages are exactly those which are recognized by finite algebras. Here,
“regular” means definable in monadic second order logic (mso), or recognizable
by a suitable kind of finite automata. This theme occurs for many kinds of
objects. Important examples are: finite words (here the algebras are
semigroups), $\omega$-words (here the algebras are $\omega$-semigroups, see
[PP04]), scattered countable linear orders (here the algebras are
$\Diamond$-semigroups, see [RC05]) or unrestricted countable linear orders
(here the algebras are $\circ$-semigroups, see [She75, CCP11]).

In all of these cases the languages recognized by algebras with a finite
universe are exactly those that can be defined in mso. This fact is remarkable
especially for the infinite structures, because then the multiplication
operation of an algebra is usually infinitary and hence it may be an infinite
object, even when the universe of the algebra is finite. The implication “if a
language is recognized by a finite algebra then it is definable in mso” uses a
subtle interplay between the finiteness of the universe and the associativity
of a multiplication operation in an algebra, which can be exploited together
with regularity results like Ramsey’s Theorem (used implicitly already by
Büchi and more explicitly in [Wil91, PP04] for $\omega$-words), Hausdorff’s
theorem on scattered linear orders used in [RC05], or Simon’s Factorisation
Forest Theorem used in [CCP11]. The equivalence of recognizability by finite
algebras and mso definability carries over to other finite structures, such as
finite ranked trees [TW68] or finite graphs of bounded treewidth [BP16].

A missing piece of this puzzle is the equivalence of algebraic recognizability
and mso for infinite trees. The hard part is proving that if a language of
infinite trees is recognized by a finite algebra, then it is definable in mso.
A subproblem is defining what a “finite algebra” actually is.

So far there have been three approaches to this question [BI09, Blu13, IMB16],
each one only partially successful.

The solution proposed in [BI09] is a two-sorted algebra that intuitively
represents regular trees (i.e. ones that have only finitely many non-
isomorphic subtrees) with zero or one free variable. The chosen notion of
finiteness is that the universe is finite on each of the two sorts, and the
multiplication operation is mso-definable. This approach has two
disadvantages: (a) a design choice of the algebra is that it only represents
regular trees and not arbitrary infinite trees; and (b) the definition of a
“finite algebra” uses the mso logic, and hence a correspondence of such
algebras with mso is not so surprising.

Another algebra for infinite trees was proposed in [IMB16]. There the notion
of a finite algebra used purely structural conditions, but it modeled only
trees with countably many branches. Such trees cannot feature recursive
branching, and they do not capture the full complexity of truly infinite
trees.

Yet another approach was proposed by Blumensath in [Blu13]. Here the algebras
are $\omega$-hyperclones, which represent arbitrary infinite trees (with
variables) and not just regular ones, thus overcoming disadvantage (a).
Blumensath’s notion of “finite algebra” is an $\omega$-hyperclone which is
finite on every sort (these are infinitely sorted algebraic structures) and
which satisfies an additional condition called _path continuity_. A
disadvantage of this approach is that path-continuous $\omega$-hyperclones are
not closed under homomorphic images, and in particular minimising an algebra
can lead outside the class. Furthermore, the notion of path continuity has a
similar, if less flagrant, issue as (b), in the sense that it can be seen as
imposing an implicit automaton structure on the algebra.

In this paper we study $\omega$-clones, which are essentially the same thing
as the $\omega$-hyperclones used in [Blu13]. The difference is cosmetic: we
represent single trees instead of tuples of trees. An $\omega$-clone is an
infinitely sorted algebraic structure, with sorts indexed by natural numbers:
the $n$-th sort represents possibly infinite trees with $n$ variables, with
each variable appearing possibly multiple times (even infinitely often).

Since $\omega$-clones generalize $\omega$-semigroups in the same way as
infinite trees generalize $\omega$-words, they are a natural candidate for an
algebra of infinite trees. The question is: what is the right definition of
“regular” $\omega$-clone that would correspond to mso for infinite trees? One
would want such a definition to use only structural properties such as
finiteness, and not to mention mso in any way. Ideally, “regular”
$\omega$-clones should also be closed under basic algebraic operations such as
taking homomorphic images, products and finitely generated subalgebras.

In this paper we refute the most natural candidate for such a structural
characterisation of regular $\omega$-clones: we construct an $\omega$-clone
which is finitely generated, finite on every sort, but it recognizes a tree
language that is not regular. This shows that, alone, finiteness of the
universe is insufficient for regularity (unlike in all the algebras for
infinite words, or for finite trees). Although this might seem unsurprising
(given the infinitely many sorts), simple ideas for a counterexample fail to
work and our construction turns out to be rather delicate. This is in contrast
with the setting of (finite) graphs, where such counterexamples are easy to
find [Cou91].

##  2\. Infinite trees

A _ranked set_ is a set where every element has an associated rank, which is a
natural number. For a ranked set $\Sigma$, the set of elements of rank $n$ is
denoted $\Sigma_{n}$. A _tree over $\Sigma$_ is a tree, possibly with infinite
branches or leaves or both, where every node is labelled by an element of
$\Sigma$. The number of children for a node must be equal to the rank of its
label, and we assume that children are ordered, so that we can speak of the
first child, the second child, etc. Here is a picture of a ranked alphabet
(with two letters of rank 2 and one of rank 0) and a tree over it.

a ranked alphabet | a tree over it
---|---
|

We use standard tree terminology like root, child, parent, leaf, descendant
and ancestor. A _branch_ in a tree is a maximal (inclusionwise) set of nodes
that is totally ordered by the descendant relation. A branch might end in a
leaf or be infinite. A _tree language_ over a ranked alphabet $\Sigma$ is a
set of trees over this alphabet.

The main focus of this paper is _regular_ tree languages, i.e. those tree
languages that can be recognized by automata (equivalently, are mso
definable). The automata we use are nondeterministic parity automata, as
defined below. A nondeterministic parity tree automaton consists of:

  * •

an _input alphabet_ , which is a finite ranked set $\Sigma$;

  * •

a finite set of _states_ $Q$ with a chosen _initial state_ $q_{0}\in Q$,

  * •

a function that assigns to each state in $Q$ a natural number called its
parity value,

  * •

for every letter $\sigma\in\Sigma$, a _transition relation_

$\displaystyle\delta_{\sigma}\subseteq Q\times Q^{\mathrm{rank}(\sigma)}.$

Since this is the only kind of automata that we use, we will simply call them
automata.

A _run_ of an automaton over a tree $t$ over the input alphabet $\Sigma$ is a
labelling of its nodes by states such that for every node $v$ with label
$\sigma\in\Sigma$, say of rank $n$, the transition relation $\delta_{\sigma}$
contains the tuple consisting of the state in $v$ and the states in the
children of $v$, listed from left to right. A run is said to satisfy the
parity condition if on every infinite branch, the maximal parity value seen
infinitely often is even. A tree is accepted if there is a run on it which has
the initial state in the root and which satisfies the parity condition. The
language _recognized_ by an automaton is defined to be the set of all trees
that it accepts. A tree language is called _regular_ if it is recognized by
some automaton.

A single infinite tree can also be called regular: it is when it contains only
finitely many non-isomorphic subtrees. Equivalently, a tree is regular if it
arises as an unfolding of a finite $\Sigma$-labeled graph, in an obvious
sense. It is a standard result due to Rabin (see e.g. [Tho97, Thm. 6.18]) that
a non-empty regular tree language necessarily contains a regular tree.

Another famous theorem of Rabin is that regular tree languages are exactly
those that can be defined in monadic second-order logic (mso), see e.g.
[Tho97] for details.

##  3\. $\omega$-clones

For a ranked set $\Sigma$, a _term over $\Sigma$ with $n$ ports_ is a tree
over the disjoint union set $\Sigma+[n]$, where numbers from
$[n]=\\{1,\ldots,n\\}$, called here ports, are viewed as symbols of rank zero
(and can therefore only appear as labels of leaves). We require every port
from $1$ to $n$ to appear at least once in such a term, although this is
mainly for presentation reasons: it is not difficult to transport our results
to a setting where this requirement is not made. Terms may be infinite, and a
port may appear infinitely many times in a single term.

Intuitively, ports in a term are locations where other trees can be grafted to
form a larger tree. It is therefore natural to consider a term with $n$ ports
as an element of rank $n$ in a ranked alphabet of terms.

More formally, for a ranked set $\Sigma$, define a ranked set
$\mathsf{C}\Sigma$ so that elements of rank $n$ are terms over $\Sigma$ with
$n$ ports, excluding (for reasons that will become apparent in a moment) the
“trivial” tree of rank $1$ whose root is labelled with port $1$.

This construction is equipped with the following structure:

  * •

_Action on functions._ A rank-preserving function $f:\Sigma\to\Gamma$ between
ranked sets is lifted to a rank-preserving function
$\mathsf{C}f:\mathsf{C}\Sigma\to\mathsf{C}\Gamma$ by node-wise application of
$f$ preserving ports, as in the following example picture:

$f:\Sigma\to\Gamma$ |  $\mathsf{C}f$ applied to a rank-2 element of $\mathsf{C}\Sigma$
---|---
|

  * •

Unit. A letter $\sigma\in\Sigma$ of rank $n$ is viewed as a term with $n$
ports which has $\sigma$ in the root and ports in its children, as in the
following picture:

a rank-3 letter in $\Sigma$ | and its rank-3 unit in $\mathsf{C}\Sigma$
---|---
|

This, for any $\Sigma$, defines a rank-preserving unit function
$\eta_{\Sigma}:\Sigma\to\mathsf{C}\Sigma$.

  * •

Flattening. The (rank-preserving) flattening function
$\mu_{\Sigma}:\mathsf{C}(\mathsf{C}\Sigma)\to\mathsf{C}\Sigma$ is defined as
follows. Suppose that $t\in\mathsf{C}(\mathsf{C}\Sigma)$ has rank $n$. Let the
root label of $t$ be $s$ (itself a term in $\mathsf{C}\Sigma$ of rank, say,
$k$), and let $t_{1},\ldots,t_{k}$ be the immediate subtrees of the root in
$t$, seen as terms in $\mathsf{C}(\mathsf{C}\Sigma)$ with rank $n$ each (here,
for a brief moment, we allow trees where some ports from $[n]$ may not
appear). Then the flattening of $t$ is the term obtained from $s$ by
substituting for (each occurrence of) the $i$-th port the flattening of
$t_{i}$, defined recursively, with the special case of $t_{i}$ being a port
(in $t$), which is flattened to itself. (Note that in the flattening of $t$,
each of the $n$ ports appears again.) The following picture should make the
idea clear:

an element of $\mathsf{C}(\mathsf{C}\Sigma)$, of rank 2 | its flattening in $\mathsf{C}\Sigma$, also of rank 2
---|---
|

######  Remark 1.

For a more formal definition it is useful think of nodes in a tree in terms of
the unique (finite) branches from the root to those nodes. For a term
$t\in\mathsf{C}(\mathsf{C}\Sigma)$, a node in the flattening $\mu_{\Sigma}(t)$
is uniquely determined by the following data:

  * •

a finite branch $(v_{1},v_{2},v_{3},\ldots v_{k})$ in $t$ (let $s_{i}$ denote
the term in $\mathsf{C}\Sigma$ that is the label of $v_{i}$; for $i=k$ this is
defined only if $v_{k}$ is not a port in $t$),

  * •

a sequence $(w_{1},\ldots,w_{k-1})$, where each $w_{i}$ is an occurrence in
$s_{i}$ of the port $j$ such that $v_{i+1}$ is the $j$’th child of $v_{i}$ in
$t$, and

  * •

a node $w_{k}$ (not a port) in $s_{k}$ if $v_{k}$ is not a port; the resulting
node in $\mu_{\Sigma}(t)$ is then labelled with the label of $w_{k}$.

If $v_{k}$ is a port in $t$, then the resulting node in $\mu_{\Sigma}(t)$ is
also a port, with the same number.

######  Remark 2.

The trivial term whose root is labelled with port $1$ rather than with an
element of $\Sigma$ is excluded from $\mathsf{C}\Sigma$ because it does not
agree well with infinite paths. To see this, for any $\Sigma$, consider a tree
which is an infinite path (of rank $0$) whose every node is labelled with the
trivial term. One would be in trouble picking a candidate of rank $0$ in
$\mathsf{C}\Sigma$ for the flattening of that infinite path. The same issue
arises already in the theory of infinite words, and is the reason why
semigroups have more importance than monoids in that theory.

######  Remark 3.

The construction $\mathsf{C}$ together with its extension to functions, unit,
and flattening operations, forms a monad on the category of ranked sets and
rank-preserving functions. Briefly, the unit and flattening operations are
natural transformations, flattening is associative, and unit is a two-sided
unit for flattening. To keep the exposition elementary we avoid category-
theoretic terminology here, but categorical considerations do provide a strong
justification for the notion of $\omega$-clones (see below), which are simply
Eilenberg-Moore algebras for the monad $\mathsf{C}$ (see e.g. [ML98, Chap. VI]
for the relevant definitions).

Trees are a natural generalization of words, and the construction $\mathsf{C}$
is a generalization of the construction of potentially infinite words out of
an alphabet. In the same fashion, the following is a generalization of the
notion of $\omega$-semigroup.

An $\omega$-clone consists of:

  * •

a ranked set $A$ equipped with

  * •

a rank-preserving function $\mathsf{pr}^{A}:\mathsf{C}A\to A$ (the product
operation),

such that:

  1. (1)

for every $a\in A$, the product of the unit of $a$ is $a$ itself:

$\mathsf{pr}^{A}(\eta_{A}(a))=a,$

  2. (2)

for every $t\in\mathsf{C}(\mathsf{C}A)$, applying the product operation to the
flattening of $t$ yields the same value in $A$ as applying it to the term
obtained from $t$ by node-wise application of the product operation:

$\mathsf{pr}^{A}(\mu_{A}(t))=\mathsf{pr}^{A}(\mathsf{C}\,\mathsf{pr}^{A}(t)).$

Intuitively, $\mathsf{pr}^{A}$ describes a way folding terms labeled with
elements of $A$ into single elements of $A$. We call it the product following
the standard terminology for a corresponding operation in $\omega$-semigroups
(see e.g. [PP04]).

The first axiom of $\omega$-clones says that products of unit terms are
computed trivially; the second axiom says that taking the product is
compositional with respect to flattening of composite terms.

A homomorphism from an $\omega$-clone $A$ to $B$ is a rank-preserving function
$h:A\to B$ that commutes with the respective product operations in the
expected sense:

$h(\mathsf{pr}^{A}(t))=\mathsf{pr}^{B}(\mathsf{C}h(t))\quad\mbox{for every
}t\in\mathsf{C}A.$

It easily follows from the definition that for any ranked set $\Sigma$, the
set $\mathsf{C}\Sigma$ is an $\omega$-clone, with the flattening taken as the
product operation. Indeed, it is the free $\omega$-clone over $\Sigma$: for
any $\omega$-clone $A$, every rank-preserving function from $\Sigma$ to $A$
extends uniquely to an $\omega$-clone homomorphism from $\mathsf{C}\Sigma$ to
$A$.

A tree language $L$ over a ranked alphabet $\Sigma$ can be seen as a subset of
$\mathsf{C}\Sigma$ that only contains terms of rank $0$. We say that an
$\omega$-clone $A$ recognizes $L$ if there is a homomorphism
$h:\mathsf{C}\Sigma\to A$, and a subset $B\subseteq A$, such that the inverse
image of $B$ along $f$ is exactly $L$.

Inspired by similar results regarding regular languages of words, infinite
words or finite trees (see Introduction), one would ideally want that a tree
language over a finite alphabet is regular if and only if it is recognized by
a finite $\omega$-clone. This turns out to be false very quickly. Indeed, if a
ranked set $A$ has some element of rank more than $1$, then the set
$\mathsf{C}A$ has elements of arbitrary finite rank. Since the product
operation in an $\omega$-clone must be rank-preserving, for $A$ to be an
$\omega$-clone it must be non-empty on every rank, so it cannot be finite. As
a result, all finite $\omega$-clones have only elements of rank at most $1$,
so they are essentially $\omega$-semigroups and they cannot recognize anything
beyond languages of infinite words.

One must therefore relax the finiteness restriction on $\omega$-clones to hope
for a correspondence to regular tree languages. A natural idea is to require a
clone to be rank-wise finite (i.e. finite on every rank), and finitely
generated. An $\omega$-clone $A$ is finitely generated if there is a finite
subset $G\subseteq A$ such that every element of $A$ can be obtained as the
product of some term in $\mathsf{C}G$.

With this relaxed definition, one direction of the desired correspondence
holds:

######  Theorem 4.

Every regular tree language over a finite alphabet is recognized by a rank-
wise finite, finitely generated $\omega$-clone.

######  Proof 3.1 (Proof (sketch)).

The $\omega$-clone to recognize a regular tree language is built of “profiles”
of automata runs. Consider runs of an automaton $\mathcal{A}$ over input
alphabet $\Sigma$ on a $\Sigma$-tree $t$ with $n$ ports. Restrict attention to
those runs that satisfy the parity condition, i.e. those where on every
infinite branch the maximal parity value seen infinitely often is even. The
profile of such a run consists of:

  * •

the initial state, i.e., the state at the root of $t$,

  * •

for each (occurrence of a) port $i\in[n]$ in $t$, a triple $(q^{\prime},m,i)$,
where $q^{\prime}$ is the state at that occurrence (which is a leaf in $t$),
and $m$ is the maximal parity value at the (finite) branch leading to that
leaf.

For each automaton $\mathcal{A}$, there are finitely many possible profiles of
every rank $n$. The set of sets of those profiles can be equipped with an
$\omega$-clone structure (memoryless determinacy of parity games is used to
ensure that it is indeed an $\omega$-clone). This $\omega$-clone recognizes
the language accepted by $\mathcal{A}$.

A full proof of Theorem 4 is rather technical. We omit the details, however,
because our main message in this paper is that the converse implication fails.
The remainder of this paper is devoted to defining a tree language, over a
finite alphabet, that is not regular but is nevertheless recognized by a rank-
wise finite, finitely generated $\omega$-clone.

##  4\. Densely antiregular trees

Fix a ranked alphabet $\\{a,b\\}$ with two letters, both of them of rank 2.
Since this alphabet has no letters of rank 0, every tree (without ports) over
it is a full binary tree. Call such a tree _antiregular_ if every two
different nodes have different subtrees.

######  Lemma 5.

Antiregular trees exist.

######  Proof 4.1.

A node in the full binary tree can be viewed as a word in $\\{0,1\\}^{*}$,
with $0$ indicating a left turn and $1$ indicating a right turn. A tree over
the alphabet $\\{a,b\\}$ can be viewed as a subset of $\\{0,1\\}^{*}$, i.e. a
language of finite words, which contains those words which correspond to nodes
labeled with $a$. It is not difficult to show that a tree is antiregular if
and only if in the corresponding language of finite words, the Myhill-Nerode
equivalence relation has only singleton equivalence classes. Languages with
the latter property exist, e.g. the language of palindromes.

The set of antiregular trees itself is not recognized by any rank-wise finite
$\omega$-clone. Intuitively, in order to determine whether a tree is
antiregular, assuming that both subtrees $t_{0},t_{1}$ of the root are
antiregular, one needs to store an infinite amount of information, namely all
subtrees of $t_{0}$ and all subtrees of $t_{1}$. We shall therefore relax the
antiregularity condition now.

A set $V$ of nodes in a tree is called _dense_ if every node of the tree has a
descendant (not necessarily proper) in $V$. Call a tree over $\\{a,b\\}$
_densely antiregular_ if the set $\\{v:\mbox{$v$ is a node whose subtree is
antiregular}\\}$ is dense.

######  Lemma 6.

The language of densely antiregular trees is not regular.

######  Proof 4.2.

Every antiregular tree is densely antiregular, so by Lemma 5 the language of
densely antiregular trees is not empty. Furthermore, a regular tree cannot be
densely antiregular. The lemma follows from the the fact that every non-empty,
regular tree language contains a regular tree (see e.g. [Tho97, Thm. 6.18]).

We will show that the set of densely antiregular trees is recognized by an
$\omega$-clone $A$ that is finite on every rank and finitely generated. To
define $A$, we use a classification of terms into four kinds. Consider a term
in $\mathsf{C}\\{a,b\\}$ of rank $n$. Such a term is a tree which uses labels
$a,b$ in non-leaf nodes, and ports $1,\ldots,n$ in leaves. A term can be of
one of four mutually exclusive kinds:

  * 1:

some subtree has no ports and is not densely antiregular;

  * 2:

some subtree has no ports and every subtree without ports is densely
antiregular;

  * 3:

every subtree has a port and some port name is used at least twice;

  * 4:

every subtree has a port and every port name is used exactly once.

For illustration, here are examples of terms of the four kinds:

kind 1: | kind 2:
---|---
|
kind 3: | kind 4:
|

Note that a term of kind 4 must be finite and its number of leaves is equal to
its rank; as a consequence, for every rank there are only finitely many terms
of kind 4.

Define a ranked set $A$ so that its element of rank $n$ is:

  * •

a term of kind 4 of rank $n$, or

  * •

a kind name (1, 2 or 3) together with the number $n$ (the rank); kind name 3
is included only if $n$ is positive.

By the above remark, $A$ is finite on every rank.

There is an easy (surjective) rank-preserving function
$h:\mathsf{C}\\{a,b\\}\to A$ that maps terms of kind ${\bf 4}$ identically,
and maps every other term to its kind and rank. Note that all trees of rank
$0$ are of kind 1 or 2. The function $h$ maps densely antiregular trees to 2,
and all the other ones to 1. In particular, $h$ recognizes the set of densely
antiregular trees.

We will build an $\omega$-clone structure on the set $A$ that will make $h$ a
homomorphism. To this end we will show that the value of $h$ on the flattening
of a term $t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$ can be derived just from the
external structure of $t$ and from the values of $h$ on its nodes.

Here and in the following, $t|_{v}$ denotes the subtree of $t$ rooted at a
node $v$.

######  Lemma 7.

For every subtree $s$ of the flattening of
$t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$, one of the following conditions holds:

  * (A)

some label of a node in $t$ contains $s$ as a subtree; or

  * (B)

for some node $v$ of $t$, the flattening of $t|_{v}$ is a proper subtree of
$s$.

######  Proof 4.3.

Easy from the definition of flattening. Looking at the formulation in Remark
1, if the root of $s$ is determined by sequences

$(v_{1},v_{2},\ldots,v_{k})\qquad\text{and}\qquad(w_{1},w_{2},\ldots,w_{k})$

and $s_{k}$ is the label of $v_{k}$, then case $(A)$ holds if the subtree of
$s_{k}$ rooted at $w_{k}$ contains no ports, since then $s$ is identical to
that subtree. On the other hand if that subtree contains a port, say of number
$j$, then the flattening of the $j$’th subtree of $v_{k}$ in $t$ is a proper
subtree of $s$ and case (B) holds.

Terms in $\mathsf{C}\\{a,b\\}$ cannot have any leaves other than ports, so the
terms “leaf” and “port” can be used interchangeably for them. However, this
does not apply to terms $t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$, as such a term
can have a leaf labeled with a tree in $\mathsf{C}\\{a,b\\}$ of rank $0$.
Reading the following discussion, one should keep this distinction in mind.

######  Lemma 8.

Every subtree of the flattening of $t$ has a port if and only if:

  * •

every subtree of $t$ has a port, and

  * •

all nodes in $t$ are of kind 3 or 4.

######  Proof 4.4.

If $t$ has a node of kind 1 or 2, then the label of that node has a subtree
with no ports, and that subtree persists in the flattening of $t$. If $t$
itself has a subtree with no ports, then the flattening of that subtree has no
ports.

Conversely, assume that the flattening of $t$ contains a subtree $s$ with no
ports. In the case (A) from Lemma 7, $s$ was a subtree of the label of a node
in $t$, and that node must have been of kind ${\bf 1}$ or ${\bf 2}$. In the
case (B), there is a node $v$ of $t$ such that the flattening of $t|_{v}$ has
no ports. This can happen only if $t|_{v}$ has no ports.

######  Lemma 9.

Assume that every subtree of the flattening of $t$ has a port. Some port name
is used in the flattening of $t$ at least twice if and only if:

  * •

some port occurs in $t$ at least twice, or

  * •

some node in $t$ is of kind 3.

######  Proof 4.5.

By Lemma 8, every subtree of $t$ has a port and all nodes in $t$ are of kind 3
or 4.

If some port occurs in $t$ at least twice, then the port occurs at least twice
in the flattening of $t$ too. On the other hand, if some node $v$ in $t$ is of
kind 3, then pick a port name $k$ that is used at least twice in the label of
$v$. The subtree of $t$ rooted at the $k$-th child of $v$ has some port $w$.
That port appears at least twice in the flattening of $t$.

Conversely, if every port name in $t$ is used only once and every node in $t$
is of type 4, then it is easy to see that every port name in the flattening of
$t$ is also used only once.

######  Lemma 10.

Assume that $t$ has no ports. Then the flattening of $t$ is densely
antiregular if and only if

  1. (i)

no node in $t$ is of kind 1; and

  2. (ii)

every node in $t$ has a descendant $v$ such that:

    1. (a)

the label of $v$ is of kind 2; or

    2. (b)

all nodes in $t|_{v}$ are of kind 4 and the flattening of $t|_{v}$ is densely
antiregular.

######  Proof 4.6.

Let us first show the “if” part. Assume that
$t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$ has no ports and satisfies conditions
(i) and (ii). We need to show that every subtree $s$ of the flattening of $t$
has a subtree that is antiregular. Notice that the flattening of $t$ has no
ports; as a consequence, $s$ has no ports either.

Consider first the case (A) from Lemma 7, i.e. that $s$ is a subtree of some
label $r\in\mathsf{C}\\{a,b\\}$ of a node in $t$. In particular the label $r$
has a subtree without ports, and therefore $r$ must be of kind 1 or 2.
Assumption (i) rules out kind 1, and therefore $r$ has kind 2, which implies
that $s$ is densely antiregular, and thus has an antiregular subtree. We are
left with case (B), where some subtree of $s$ is equal to the flattening of
$t|_{w}$ for some node $w$ in $t$. By assumption (ii), $w$ has a descendant
$v$ in $t$ that satisfies one of (a) or (b) as in the statement of the lemma.
In either case the flattening of $t|_{v}$ (and hence also $s$) contains an
antiregular subtree.

For the “only if” part, suppose that the flattening of
$t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$ is densely antiregular. Clearly no node
in $t$ can have kind 1, since every subtree of a densely antiregular tree is
also densely antiregular. It remains to prove condition (ii). Take some node
$u$ in $t$. If $u$ has a descendant with label of kind 2 then (ii) is
satisfied. Suppose otherwise. Assume first that $u$ has some descendant $v$
such that the subtree $t|_{v}$ uses only labels of kind 4. Since the
flattening of $t|_{v}$ is a subtree of the flattening of $t$, it must be
densely antiregular, and therefore (ii) holds thanks to (b). The remaining
case is when no such $v$ exists, hence nodes of kind 3 are dense in the
subtree $t|_{u}$. But then every subtree of the flattening of $t|_{u}$
contains two identical subtrees and is therefore not antiregular, which
contradicts the assumption that the flattening of $t$ is densely antiregular.

######  Corollary 11.

For any term $t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$, the following properties
hold:

  * (a)

If some node of $t$ is of kind 1 then the flattening of $t$ is of kind 1.

  * (b)

If some subtree of $t$ has no ports and does not satisfy condition (ii) in
Lemma 10, then the flattening of $t$ is of kind 1.

  * (c)

If:

    * –

no node of $t$ is of kind 1,

    * –

some subtree of $t$ has no ports, and

    * –

every subtree of $t$ with no ports satisfies condition (ii) in Lemma 10,

then the flattening of $t$ is of kind 2.

  * (d)

If:

    * –

no node of $t$ is of kind 1,

    * –

every subtree of $t$ has ports, and

    * –

some node of $t$ is of kind 2,

then the flattening of $t$ is of kind 2.

  * (e)

If:

    * –

all nodes of $t$ are of kind 3 or 4,

    * –

every subtree of $t$ has ports, and

    * –

some node of $t$ is of kind 3,

then the flattening of $t$ is of kind 3.

  * (f)

If:

    * –

all nodes of $t$ are of kind 4,

    * –

every subtree of $t$ has ports, and

    * –

some port name appears in $t$ more than once,

then the flattening of $t$ is of kind 3.

  * (g)

If:

    * –

all nodes of $t$ are of kind 4,

    * –

every subtree of $t$ has ports, and

    * –

every port name appears in $t$ exactly once,

then the flattening of $t$ is of kind 4.

Moreover, cases (a)-(g) cover all terms $t$ in
$\mathsf{C}(\mathsf{C}\\{a,b\\})$.

######  Proof 4.7.

The final remark is easy to check.

  * (a)

If the label of a node $v$ in $t$ is of kind 1 then it contains a subtree
which has no ports and it not densely antiregular. That subtree appears in the
flattening of $t$, therefore the flattening of $t$ is of kind 1.

  * (b)

Let $v$ be a node in $t$ such that $t|_{v}$ has no ports and does not satisfy
condition (ii) in Lemma 10. Then the flattening of $t|_{v}$ has no ports and,
by Lemma 10, it is not densely antiregular. As a result, the flattening of $t$
is of kind 1.

  * (c)

Let $v$ be a node of $t$ such that $t|_{v}$ has no ports. Such a node exists
by our second assumption. Clearly, the flattening of $t|_{v}$ has no ports.

Now consider any subtree $s$ of the flattening of $t$ that has no ports. We
need to prove that $s$ is densely antiregular, i.e., that every subtree
$s^{\prime}$ of $s$ contains an antiregular subtree. Apply Lemma 7 to
$s^{\prime}$. In case (A), $s^{\prime}$ is a subtree of (the label of) a node
$v$ of $t$. Since $t$ has no nodes of kind 1, $v$ must be of kind 2, hence
$s^{\prime}$ is densely antiregular. In case (B), there is a node $v$ in $t$
such that the flattening of $t|_{v}$ is a subtree of $s^{\prime}$. Since
$s^{\prime}$ has no ports, $t|_{v}$ cannot have ports either so, by our
assumptions, $t|_{v}$ satisfies condition (ii) in Lemma 10. Since $t$ has no
nodes of kind 1 condition (i) is also satisfied, hence by Lemma 10 the
flattening of $t|_{v}$ is densely antiregular so it contains an antiregular
subtree as required.

As a result, the flattening of $t$ is of kind 2.

  * (d)

If some node $v$ of $t$ is of kind 2, then its label has a subtree with no
ports, and that subtree persists in the flattening of $t$.

Now consider any subtree $s$ of the flattening of $t$ such that $s$ has no
ports. We need to prove that $s$ is densely antiregular. Apply Lemma 7 to $s$.
In case (A), $s$ is a subtree of a node $v$ of $t$. Since $t$ has no nodes of
kind 1, $v$ must be of kind 2, hence $s$ is densely antiregular. In case (B),
there must be a node $v$ in $t$ such that the flattening of $t|_{v}$ is a
subtree of $s$. But by our assumptions $t|_{v}$ has ports, so the flattening
of $t|_{v}$ has ports, which is a contradiction. As a result, case (B) cannot
happen, $s$ is densely antiregular and the flattening of $t$ is of kind 2.

  * (e)

By the first two assumptions and by Lemma 8, every subtree of the flattening
of $t$ has a port. Furthermore, since $t$ has a node of kind 3, by Lemma 9 the
flattening of $t$ is of kind 3.

  * (f)

Proved similarly to (e).

  * (g)

By the first two assumptions and by Lemma 8, every subtree of the flattening
of $t$ has a port. Since $t$ has no node of kind 3 and no port is used more
than once in $t$, by Lemma 9 the flattening of $t$ is of kind 4.

The rather tiresome Corollary 11 shows how, given a tree
$t\in\mathsf{C}(\mathsf{C}\\{a,b\\})$, one can determine the kind of the
flattening of $t$ just by looking at the external structure of $t$ and at the
kinds of (the labels of) its nodes. More precisely, it is enough to look at
the tree $\mathsf{C}h(t)\in\mathsf{C}A$. The procedure can be described by a
decision diagram:

Some node is of kind 1? yes(a)no Every subtree has a port? yesno Some node is
of kind 2? yes(d)no Every subtree with no ports satisfies condition (ii) in
Lemma 10? no(b)yes(c) Some node is of kind 3? no Some port name appears more
than once? no(g)$\textstyle{\bf 1}$$\textstyle{\bf 2}$$\textstyle{\bf
3}$$\textstyle{\bf 4}$yes(e)yes(f)

Final decisions in the diagram are labeled with respective subcases of
Corollary 11 that justify them.

Note that the only path that leads to outcome 4 guarantees that all nodes
(apart from ports) in $t$ are of kind 4. In this case, the tree
$\mathsf{C}h(t)$ retains full information about all nodes. This means that
$\mathsf{C}h(t)$ contains enough information to determine not just the kind of
the flattening of $t$, but also the value of $h$ on that flattened tree.
Formally, this defines a function, which we denote
$\mathsf{pr}^{A}:\mathsf{C}A\to A$, such that the following diagram commutes:

$\textstyle{\mathsf{C}(\mathsf{C}\\{a,b\\})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{C}h}$$\scriptstyle{\mu_{\\{a,b\\}}}$$\textstyle{\mathsf{C}A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{pr}^{A}}$$\textstyle{\mathsf{C}\\{a,b\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\textstyle{A.}$

This almost means that $h$ is a homomorphism; the only thing that remains to
be proved is that $\mathsf{pr}^{A}$ is an $\omega$-clone on $A$. This would be
tedious to check by hand, but fortunately it follows from abstract
considerations: for every commuting diagram of functions

$\textstyle{\mathsf{C}B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{C}h}$$\scriptstyle{f}$$\textstyle{\mathsf{C}A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\textstyle{A,}$

if $f$ is an $\omega$-clone on $B$ and $h$ is surjective then $g$ is an
$\omega$-clone on $A$. This holds for Eilenberg-Moore algebras for any monad
in place of $\mathsf{C}$, and it is a folklore result proved in passing by
several authors, see e.g [ML98, p. 152] or [BW05, p. 96]. A more explicit
statement and proof can be found in [Boj15, Lem. 3.3].

Finally, it is easy to see that the $\omega$-clone $A$ is finitely generated
by the set of all its elements of rank at most $2$.

This completes the proof that the language of densely antiregular trees,
although not regular, is recognized by a rank-wise finite, finitely generated
$\omega$-clone.

## References

  * [BI09] Mikołaj Bojańczyk and Tomasz Idziaszek.  Algebra for infinite forests with an application to the temporal logic EF.  In Procs. CONCUR’09, pages 131–145, 2009.
  * [Blu13] Achim Blumensath.  An algebraic proof of Rabin’s tree theorem.  Theor. Comput. Sci., 478:1–21, 2013.
  * [Boj15] Mikołaj Bojańczyk.  Recognisable languages over monads.  CoRR, abs/1502.04898, 2015.
  * [BP16] Mikołaj Bojańczyk and Michał Pilipczuk.  Definability equals recognizability for graphs of bounded treewidth.  In Procs. LICS 2016, pages 407–416. ACM, 2016.
  * [BW05] Michael Barr and Charles Wells.  Toposes, triples and theories, volume 12 of Reprints in Theory and Applications of Categories.  2005\.
  * [CCP11] Olivier Carton, Thomas Colcombet, and Gabriele Puppis.  Regular languages of words over countable linear orderings.  In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, pages 125–136, 2011.
  * [Cou91] Bruno Courcelle.  The monadic second-order logic of graphs v: on closing the gap between definability and recognizability.  Theoretical Computer Science, 80(2):153 – 202, 1991.
  * [IMB16] Tomasz Idziaszek, Michał Skrzypczak, and Mikołaj Bojańczyk.  Regular languages of thin trees.  Theory Comput. Syst., 58(4):614–663, 2016.
  * [ML98] Saunders Mac Lane.  Categories for the Working Mathematician.  Springer, 2nd edition, 1998.
  * [PP04] Dominique Perrin and Jean-Éric Pin.  Infinite Words: Automata, Semigroups, Logic and Games.  Elsevier, 2004.
  * [RC05] Chloe Rispal and Olivier Carton.  Complementation of rational sets on countable scattered linear orderings.  Int. J. Found. Comput. Sci., 16(4):767–786, 2005.
  * [She75] Saharon Shelah.  The monadic theory of order.  The Annals of Mathematics, 102(3):379–419, 1975.
  * [Tho97] Wolfgang Thomas.  Handbook of Formal Languages: Volume 3 Beyond Words, chapter Languages, Automata, and Logic, pages 389–455.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1997.
  * [TW68] J.W. Thatcher and J.B. Wright.  Generalized finite automata with an application to a decision problem of second order logic.  Math. Syst. Theory, 2:57–82, 1968.
  * [Wil91] Thomas Wilke.  An Eilenberg theorem for infinity-languages.  In Procs. ICALP’91, pages 588–599, 1991.