A conjecture about binary trees
Kron A.
A binary tree ${\cal T}$ is a tree with an origin and such that
each node of ${\cal T}$ either has exactly two immediate
successors or it is an end-node.
A subtree ${\cal T}'$ of a tree ${\cal T}$ is a tree such
that every node of ${\cal T}'$ is a node of ${\cal T}$ and the
immediate successor relation in
${\cal T}'$ is the immediate successor relation in ${\cal T}$. A tree
${\cal T}$ is a {\sl formula-like tree\/} (FLT) iff it has no proper subtree
that is isomorphic to ${\cal T}$, and
no proper subtree ${\cal T}'$ of ${\cal T}$
has a proper subtree ${\cal T}''$ isomorphic to ${\cal T}'$.
With every node of a FLT ${\cal T}$ one of the
numbers 0 or 1 is associated, as follows: 0 is
associated with the origin of ${\cal T}$; if 0 (1)
is associated with a node at level
$n$, then 1 (0) is associated with its left
hand immediate successor and 0 (1) is associated with
its right hand immediate successor.
If 0 (1) is associated with the origin of a subtree ${\cal T}'$,
then ${\cal T}'$ is a 0-subtree (1-subtree).
Let us define the following operations on a FLT.
{\narrower
\item{SU$^0$} Let ${\cal T}$ be a FLT and let
${\cal T}_1{\cal T}_2$ be one of its 0-subtrees;
then the subtree ${\cal T}_1{\cal T}_2$ can be cut off and
a subtree $({\cal T}_2{\cal T}_3)({\cal T}_1{\cal T}_3)$
can be inserted in ${\cal T}$ instead, where ${\cal T}_3$ is any FLT.
\item{PR$^0$} Let ${\cal T}$ be a FLT and let
${\cal T}_2{\cal T}_3$ be one of its 0-subtrees;
then the subtree ${\cal T}_2{\cal T}_3$ can be cut off and
a subtree $({\cal T}_1{\cal T}_2)({\cal T}_1{\cal T}_3)$
can be inserted in ${\cal T}$ instead, where ${\cal T}_1$
is any FLT.
\item{SU$^1$} Let ${\cal T}$ be a FLT and let $({\cal
T}_2{\cal T}_3)({\cal T}_1{\cal T}_3)$
be one of its 1-subtrees;
then the subtree $({\cal T}_2{\cal T}_3)({\cal T}_1{\cal
T}_3)$ can be cut off and
the subtree ${\cal T}_1{\cal T}_2$
can be inserted in ${\cal T}$ instead.
\item{PR$^1$} Let ${\cal T}$ be a FLT and let $({\cal
T}_1{\cal T}_2)({\cal T}_1{\cal T}_3)$
be one of its 1-subtrees;
then the subtree $({\cal
T}_1{\cal T}_2)({\cal T}_1{\cal T}_3)$ can be cut off and
the subtree ${\cal T}_2{\cal T}_3$
can be inserted in ${\cal T}$ instead.
\item{RP} Let ${\cal T}$ be a FLT and let
${\cal T}_1({\cal T}_2{\cal T}_3)$ be one of its 0-or-1-subtrees;
then the subtree ${\cal T}_1({\cal T}_2{\cal T}_3)$ can be
cut off and the subtree ${\cal T}_2({\cal T}_1{\cal T}_3)$
can be inserted in ${\cal T}$ instead.}
Suppose that starting with a FLT ${\cal T}'$ and successively
performing the operations SU$^0$, PR$^0$, SU$^1$, PR$^1$, and RP any
finite
number of times, in any order, and such that at least one of the first
four
rules is applied at least once, we can obtain a FLT ${\cal T}''$. In such
a case we shall write ${\cal T}'\longrightarrow {\cal T}'$.
In the paper we shall give some evidence for the following conjecture:
if ${\cal T}'\longrightarrow {\cal T}'$, then there is a natural number
$n$
such that for any $m$ and ${\cal T}_1,\dots , {\cal T}_m$, if
$$
{\cal T}'\longrightarrow {\cal T}_1\longrightarrow \dots \longrightarrow
{\cal T}_m\longrightarrow {\cal T}'',
$$
then $m\leq n$.