<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{seminar}
\special{landscape}
\usepackage[usenames]{color}
%\usepackage[polish]{babel}

\usepackage{graphics,graphicx,latexsym}
%
%
%-------------------------- from thue.tex -----------------

\newcommand{\TM}{\textsl{TM}\ }
\newcommand{\sarrow}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\dotdot}{\ldotp\ldotp}

\newcommand{\dziwny}{$\mathcal{D}$}
\newcommand{\mult}{\textsf{mult}}
\newcommand{\dawg}{\textsf{dawg}}
\newcommand{\cdawg}{\textsf{cdawg}}
\newcommand{\per}{\textsf{per}}
\newcommand{\myvalue}{\textsf{value}}


%--------------- end from thue.tex ---------------------
%
%
\date{}

%---------------------------------------------------
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.55}
\def\gr4{\textcolor{OliveGreen}}
\def\re4{\textcolor{BrickRed}}
\def\bl4{\textcolor{MyDarkBlue}}
\renewcommand{\labelitemi}{\fcolorbox{green}{Dandelion}{\color{Violet}{\textgreater}}}
\newcommand{\bsl}{\begin{slide}}
\newcommand{\esl}{\end{slide}}
\newcommand{\qed}{$\Box$}
%
%\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\newcommand{\arrow}[1]{\stackrel{#1}{\longrightarrow}}
%\setlength{\textwidth}{8in}
\newcommand{\myparagraph}[1]{{\smallskip\noindent{\bf #1}}}
\newcommand{\etal}{{\em et al} }
\newcommand{\myif}{{\mbox{\rm\ if \ }}}
\newcommand{\mycase}[1]{\noindent\mbox{{\underline{Case #1}}:\/}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% various leters
%\newenvironment{observation}{\begin{observationpart}\sl}{\end{observationpart}}
\newtheorem{theorempart}{\bf Theorem}
\newtheorem{observationpart}[theorempart]{\bf Observation}
\newcommand{\suchthat}{{\,:\,}}
\newcommand{\half}{{\mbox{$\frac{1}{2}$}}}
\newcommand{\onehalf}{{\half}}
\newcommand{\onethird}{{\frac{1}{3}}}
\newcommand{\onefourth}{{\frac{1}{4}}}
\newcommand{\reals}{{\bf R}}
 \newcommand{\St}{{\rm st}}
 \newcommand{\s}{{\sl S}}
 \newcommand{\Nd}{{\rm nd}}
 \newcommand{\Rd}{{\rm rd}}
 \newcommand{\Th}{{\rm th}}

 \newcommand{\bfNP}{{\bf NP}}
 \newcommand{\bfP}{{\bf P}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% all sorts of letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bfx}{{\bf x}}

\newcommand{\bara}{{\bar a}}
\newcommand{\barm}{{\bar m}}
\newcommand{\barA}{{\bar A}}

\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\barr}{{\bar r}}

\newcommand{\calA}{{\mathcal A}}
\newcommand{\calB}{{\mathcal B}}
\newcommand{\calC}{{\mathcal C}}
\newcommand{\calD}{{\mathcal D}}
\newcommand{\calE}{{\mathcal E}}

\newcommand{\F}{{\mathcalF}_{\infty}}

\newcommand{\G}{{{\mathcal G}}}
\newcommand{\calH}{{\mathcal H}}
\newcommand{\calI}{{\mathcal I}}
\newcommand{\calJ}{{\mathcal J}}
\newcommand{\calK}{{\mathcal K}}
\newcommand{\calL}{{\mathcal L}}
\newcommand{\calM}{{\mathcal M}}
\newcommand{\calN}{{\mathcal N}}
\newcommand{\calO}{{\mathcal O}}
\newcommand{\calP}{{\mathcal P}}
\newcommand{\A}{{\mathcal B}}
\newcommand{\calQ}{{\mathcal Q}}
\newcommand{\calR}{{\mathcal R}}
\newcommand{\calS}{{\mathcal S}}
\newcommand{\calT}{{\mathcal T}}
\newcommand{\calU}{{\mathcal U}}
\newcommand{\calV}{{\mathcal V}}
\newcommand{\calW}{{\mathcal W}}
\newcommand{\calX}{{\mathcal X}}
\newcommand{\calY}{{\mathcal Y}}
\newcommand{\Z}{{\mathcal Z}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\f}{{f}}
\newcommand{\LW}{\sl{RANK}}
\newcommand{\SUF}{{\textsl{SUF}}}
\newcommand{\SHIFT}{{\textsl{ROT}}}

\newcommand{\Rn}{{\textsl{R}}}
\newcommand{\rep}{{\cal{Z}}}
\newcommand{\prep}{{\cal{R}}}
\newcommand{\code}{{\bar{\cal{Z}}}}

\newcommand{\myskip}{\vskip 0.4cm \noindent}
\newcommand{\ms}{\myskip}
\newcommand{\bs}{\vskip 1cm \noindent}
\newcommand{\wZ}{\widehat{\cal{Z}}}
\newcommand{\SR}{ShortRep}
\newcommand{\SRP}{ShortRep'}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{conjecture}{Conjecture}
\newenvironment{proof}{{\it Proof:\/}}{\hfill $\Box$\vskip 0.1in}
\newenvironment{proof2}{{\it Proof\/}}{\hfill $\Box$\vskip 0.1in}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
%%%%%%%%%%%%%%%%%%% from heniek *************************
\newcommand{\heading}[1]{%
  \begin{center}
    {\ \\                               % percent out when not using
                                        % centerslidesfalse
%    \Large\bf
    \large\bf
    \psframebox[linecolor=blue,
                linewidth=0.5mm,
                fillstyle=solid,
                fillcolor=lightskyblue]{{\black{#1}}}
    }
  \end{center}
  \vspace{1ex minus 1ex}}

%*********************************************************************
\date{}
        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        \slideframe{}
 \onlyslides{}
 \begin{document}
 %SLIDE COMMANDS
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.55}

\def\gr4{\textcolor{OliveGreen}}
\def\re4{\textcolor{BrickRed}}
\def\bl4{\textcolor{MyDarkBlue}}
%\definecolor{light-yellow}{yellow}{0.7}

\centerslidesfalse           %percent out for centering slides vertically
                             %keeps slide heading close to the top of
                             %the slide

%=============================================================================
%%% DEFINE HEADER AND FOOTER: setting pagestyle
\pagestyle{headings}         %empty
%\slidepagestyle{mypagestyle} %percent out if using fancy (and fancydr)
                             %or if not wanting header nor footer

%\pagestyle{fancy}           %requires fancyhdr
%\lfoot{\tiny\it ICLP-2002}
%{\rfoot{\tiny \thepage}}    %page numbers on the right
%\cfoot{}
%\rhead{\tiny\it \hfill Title}
%=============================================================================

\centerslidesfalse           %percent out for centering slides vertically

 \bsl
% \pagecolor{yellow}
 \vspace*{0.5cm}
 \centerline{\bf {\color{blue}  \Large 3PCC}}
 \ms
\begin{center}
{\bf
%(Note)\\
  {\color{red}  \Large The structure of graphs representing all  \vskip 0.3cm
  subwords of Thue-Morse sequences}
\myskip {\color{BlueViolet}   Jakub Radoszewski, Wojciech Rytter }

\myskip {Instytut Informatyki,\\
           Uniwersytet Warszawski, \\
           Warszawa%/, Poland
}
}
\end{center}
\esl

%%%%%%%%%%%%%%%%%%%%%%%%
\bsl
{\color{MyDarkBlue}\large
The syntactic properties of Thue-Morse words are related
  to special type of automata/graphs.


  The directed acyclic subword graph ({\em dawg}, in short) is a useful
  deterministic automaton accepting all suffixes of the word.
  Its compacted version (resulted by compressing chains of states)
  is denoted by {\em cdawg}.
\ms
  The cdawgs of Thue-Morse words have regular and very simple structure,
  in particular they offer a powerful (exponential) compression of the set
  of all subwords in case of finite Thue-Morse words.
  }
\esl\bsl{\color{MyDarkBlue}\large
{\color{MyDarkBlue}
  Using the special structure of cdawgs
  several unknown properties of Thue-Morse words as well as new (graph-based) proofs of some well-known
  properties are demonstrated.
  \ms \ms
  A slight modification of the compact cdawg of the infinite Thue-Morse word
  yields an infinite graph with ''2-counting property''.
  Also a new numeration system is introduced and its relation to cdawgs of
  Thue-Morse words is discussed.
}
}\esl
%------------------------------------
\bsl{\color{MyDarkBlue}\large
Denote:
\ms
$$infinite\ \ graph:\ \ \ G\ =\ cdawg(\tau)$$
\ms
$$finite\ \ graph:\ \ \ G_n\ =\ cdawg(\tau_n)$$
}
\esl
%--------------------------------------------
\bsl{\color{MyDarkBlue}\large
Let $\bar{x}$ be the sequence resulting by negating the bits of $x$.
The finite \TM words are defined as follows:
  $$\tau_0\ =\ 0;\ \ \tau_{n}\ =\ \tau_{n-1} \bar{\tau}_{n-1} \quad\textrm{for}\ \ n&gt;0.$$
\ms
The infinite \TM word $\tau$ is the {\em limit} of $\tau_n$ words, the limit in the sense that
each $\tau_n$ is a prefix of $\tau$.
\myskip
Also let $\varphi$ be the \TM morphism:
$$
  \varphi(0)=01,\ \ \ \varphi(1)=10.
$$
Then $$\tau_n\ =\ \varphi^n(\tau_0).$$}
\esl
\bsl {\color{MyDarkBlue}\large
$$
  \tau_0=0,$$ $$ \tau_1=01,$$ $$ \tau_2=0110,$$ $$
 \tau_3=01101001 $$ $$ \tau_4=0110100110010110
$$

$$
  \tau\ =\ 0110100110010110100101100110\ldots \ldots
$$

}\esl
%--------------------------------------------------------------------
\bsl{\color{MyDarkBlue}\large
\noindent Denote by $Sub(u)$ the set of all finite subwords (factors) of $u$.
\ms
The word $v\in\{0,1\}^*$ is a \fcolorbox{MyDarkBlue}{GreenYellow}{{ right special factor}} of the word $u$ iff
$v0,\,v1 \in Sub(u)$.
\ms
\noindent $v\in\{0,1\}^*$ is a \fcolorbox{MyDarkBlue}{GreenYellow}{{ left special factor} } of the word $u$ iff
$0v,\,1v \in Sub(u)$.

\noindent The word is a \fcolorbox{MyDarkBlue}{GreenYellow}{{ bispecial factor}} iff it is both left and right special.
}
\esl

%------------------------------------
\bsl{\color{MyDarkBlue}\large
\ms
The internal vertices of the subword graph correspond to left special
factors.
\ms \ms
The internal vertices of the { compacted}

subword graph correspond to bispecial
factors.
\ms
$G_n$ is exponentially  compressed representation of subwords of $\tau_n$.
For $n\ge 3 $ the number of vertices of $G_n$ is:
\ms
\centerline{ \fboxsep=5mm \fboxrule=0.1mm
  \fcolorbox{MyDarkBlue}{yellow}{{\color{RedViolet}$4n-6\ =\ 4\;\log |\tau_n| - 6$}}}
}
\esl
\bsl{\color{MyDarkBlue}\large
\begin{figure}[!ht]
\begin{center}
\includegraphics{cdawg3_min-crop}
\end{center}
\end{figure}

\noindent
  The cdawg for $\tau_3\ =\ 01101001$.  The internal vertices are
 the bispecial factors of 01101001.
  $\cdawg(\tau_3)$ is not extremely regular, the regular structure starts from $\tau_4$.
  Labels of edges outgoing from the same vertex start with
  different symbols, they correspond to factors of $\tau$.
}\esl

\bsl{\color{MyDarkBlue}\large

Define a family of operations, $DelQuart_i$, which remove from the word $w$
the $i$-th quarter, assuming $|w|$ is divisible by 4:
$$
  w\ =\ w_1w_2w_3w_4   \ \ \&amp; \ \   |w_1|=|w_2|=|w_3|=|w_4|
$$
\ms \ms
$$\Rightarrow\ DelQuart_1(w)=w_2w_3w_4\ \ \&amp;\ \ DelQuart_3(w)=w_1w_2w_4.$$
\ms
We introduce special factors of {\em rank} $n$:
\ms
$$
  \sigma_n\ =\ DelQuart_3(\tau_n),\quad \tau'_n\ =\ DelQuart_1(\tau_n).
$$
}
\esl
\bsl{\color{MyDarkBlue}\large

\begin{example}
 $$DelQuart_3:\ \ \tau_3\ =\ 0110\;\underline{10}\;01\ \ \Rightarrow\ \
                           011001\ =\ \sigma_3$$
 $$DelQuart_1:\ \ \tau_3\ =\ \underline{01}\;101001\ \ \Rightarrow\ \
                           101001\ =\ \tau'_3$$
\end{example}

\medskip
\noindent
Equivalently
$$
  \sigma_n\ =\ \varphi^{n-2}(\sigma_2),\ \ \textrm{where}\ \sigma_2=010.
$$
We also have:
$$
  \sigma_n\ =\ \tau_{n-2}\bar{\tau}_{n-1}\ =\ \tau_{n-1}\tau_{n-2}, \quad
  \tau'_n\ =\ \bar{\tau}_{n-2}\bar{\tau}_{n-1}.
$$
}
\esl
%--------------------------------------------------------------------

\bsl{\color{MyDarkBlue}\large
\begin{lemma}
A word $u\in Sub(\tau)$ starting with the letter 0 is a left special factor of the
infinite Thue-Morse word if and only if it is a prefix of $\varphi^{n}(\sigma_2)$ for some $n$.
\end{lemma}
\bs
\begin{lemma}
A word $u\in Sub(\tau),\ |u|&gt;4$, is a bispecial factor of the infinite
Thue-Morse word if and only if it is a morphic image (under $\varphi$)
of a shorter bispecial word.
\
Moreover, $\tau_0$, $\tau_1$, $\sigma_2$ and their negations are bispecial
factors of $\tau$.
\end{lemma}
}
\esl
%--------------
\bsl{\color{MyDarkBlue}\large
We have exactly  8 bispecial words of length at most 4 in $\tau$.
They are
$$\tau_0=0,\ \sigma_2=010,\ \tau_1=01,\ \tau_2=0110$$
and their negations.
\ms We know that:
 $$\varphi(\tau_i)=\tau_{i+1},\ \varphi(\sigma_i)=\sigma_{i+1}$$

Hence the internal vertices of the { compacted}
subword graph correspond precisely to
words $\tau_i, \sigma_i$ and their negations for $i\ge 0$.}
\esl
%--------------
\bsl{\color{MyDarkBlue}\Large
\begin{theorem}\label{thm:edges_infty}
  The edges of $G$ are as follows (other edges are symmetric copies
  by bitwise negation):
  \ms
  \begin{equation}\label{eq:edges1}
    \varepsilon \sarrow{\tau_0} \tau_0,
      \quad\quad  \tau_0 \sarrow{\tau_1}\ \bar{\tau}_2,
  \end{equation}
  \ms
  \begin{equation}\label{eq:edges2}
    \tau_i \sarrow{\bar{\tau}_i}\ \tau_{i+1} \ \mbox{ for }\ i \ge 0,
      \quad\quad  \tau_i \sarrow{\tau_{i-1}} \ \sigma_{i+1} \ \mbox{ for }\ i \ge 1,
  \end{equation}
  \ms
  \begin{equation}\label{eq:edges3}
    \sigma_i \sarrow{\tau_{i-1}}\ \tau_{i+1},
      \quad\quad  \sigma_i \sarrow{\tau'_i}\ \bar{\tau}_{i+1} \ \mbox{ for }\ i \ge 2.
  \end{equation}
\end{theorem}

}
 \esl
\bsl{\color{MyDarkBlue}\large
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=12.5cm]{cdawginfty_min-crop}
\end{center}
\end{figure}
\ms
\centerline{The cdawg for $\tau$ --- an initial part.}

}\esl
%------------------------------------------
\bsl{\color{MyDarkBlue}\large
The vertices of $G_n=cdawg(\tau_n)$ are vertices of $G$ with the sink $\tau_n$
and other indices smaller thean $n-1$.
\ms
\noindent The  characterization of edges of $G_n$:

\begin{theorem}\label{thm:edges_fin}
  The edges of $G_n$ (for $n \ge 4$) are of the form \eqref{eq:edges1}, \eqref{eq:edges2}, \eqref{eq:edges3}
  for $i \le n-2$ (and their negations), and additionally the following edges pointing to the sink:
  \ms
  \begin{equation}\label{eq:edges4}
    \tau_{n-2} \sarrow{\bar{\tau}'_{n-1},\ \tau'_n}\ \tau_n,
      \quad\quad  \bar{\tau}_{n-2} \sarrow{\bar{\tau}_{n-1},\ \tau_{n-2}}\ \tau_n,
  \end{equation}
  \ms
  \begin{equation}\label{eq:edges5}
    \sigma_{n-2} \sarrow{\tau'_{n-2},\ \tau_{n-3}\bar{\tau}_{n-1}}\ \tau_n,
      \quad\quad \bar{\sigma}_{n-2} \sarrow{\bar{\tau}_{n-3},\ \bar{\tau}'_{n-2}\bar{\tau}_{n-1}}\ \tau_n.
  \end{equation}
  \ms
\end{theorem}

}
\esl
%------------------------------------------
\bsl{\color{MyDarkBlue}\large
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=12.5cm]{edges_example_min-crop}
\end{center}
\end{figure}

  The edges $$\sigma_3 \ \sarrow{\tau_2}\ \tau_4$$
  $$\sigma_3 \ \sarrow{\bar{\tau}_1\bar{\tau}_2}\ \bar{\tau}_4$$
}\esl
\bsl{\color{MyDarkBlue}\large
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=12.5cm]{cdawg7_min-crop}
\end{center}
\end{figure}


\ms
  The cdawg for $\tau_7$.
  Note the power of compaction: $|\tau_7|=128$ and it contains $6\,232$
  distinct factors, however
  $|V(G_7)|=22$ and $|E(G_7)|=42$.

}\esl
%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\begin{theorem}
  We can  test if a word $w$ is a factor of a \TM word $\tau_n$
  in time $O(|w|)$ and $O(1)$ space. The number of occurrences can be found within the same complexity.
\end{theorem}

\begin{proof}
  It is easy to see that we can test if a specified factor of $w$ is a \TM word in linear time
  and constant space.
  Then we can traverse $\cdawg(\tau_n)$ without remembering it explicitly, just keeping track
  of the current position within $w$ and the current vertex of the cdawg.
  Traversing an edge of the cdawg reduces to one or several tests if a factor of $w$ is a \TM word,
  which take $O(|w|)$ time in total.
\end{proof}
}
\esl
%-----------------------------------------------------------------------

\bsl{\color{MyDarkBlue} \large
\noindent
Let $\#occ(x,w)$ be the number of occurrences of factor $x$ in $w$.\\
The node of $G_n$ is accepting iff the correspoding word is a suffix of $\tau_n$.
We can show:
\begin{itemize}
\item The accepting nodes are $$\tau_n,\ \tau_{n-2},\ \bar{\tau}_{n-3},\ \tau_{n-4},\ ,\ \bar{\tau}_{n-5} \ldots$$
\ms
\item
The number of occurrences of $x$ equals the number of paths from the implicit node
corresponding to $x$ to accepting node
\ms
\item
The number of such path equals the number of such paths from the closest
explicit node to  accepting node
\end{itemize}
}\esl
%--------------------------------------

\noindent
\bsl{\color{blue} \large
\noindent
\centerline{The numbers $\#occ(\tau_k,\tau_7)$ }
\ms
\begin{center}
\begin{tabular}{ccccccccccccccccccc}
$k\ =\ $&amp;1&amp;2&amp;3&amp;4&amp;5&amp;6 \\
$\#occ=$&amp;1&amp;3&amp;5&amp;11&amp;21&amp;43
\end{tabular}
\end{center}
\ms
\ms
}
{\color{Violet}\large
\centerline{The numbers $\#occ(\bar{\tau}_k,\tau_7)$ }
\ms
\begin{center}
\begin{tabular}{ccccccccccccccccccc}
$k\ =\ $&amp;1&amp;2&amp;3&amp;4&amp;5&amp;6 \\
$\#occ=$&amp;1&amp;2&amp;5&amp;10&amp;21&amp;42
\end{tabular}
\end{center}
}
\ms
{\color{red}\large \centerline{What about   simple formulas ?}
}
\esl
%-----------------------------
\bsl{\color{MyDarkBlue} \large
\noindent
 For $1 \le i &lt; n$ we have:
\ms
\begin{itemize}
\item
$\#occ(\tau_i,\tau_n)\ =\ \lceil (2^{n-i+1}-1)/{3} \rceil$
\ms
\item
$\#occ(\bar{\tau}_i,\tau_n)\ =\ \lfloor (2^{n-i+1}-1)/{3} \rfloor$
\end{itemize}
\ms\ms
For $2\le i&lt;n-2$ we have:
\ms
\begin{itemize}
\item
$\#occ(\sigma_i)\ =\#occ(\tau_{i+1})+\#occ(\bar{\tau}_{i+1})$
\end{itemize}
\ms
This implies simple calculation of $\#occ(x,\tau_n)$ for any $x$.
}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\ms \ms
\noindent
The following theorem provides a compact formula for the number of distinct factors of a \TM word.
\ms \ms
\begin{theorem}\mbox{ \ }
\ms
  The number of different factors of $\tau_n$ for $n \ge 4$ equals\ms
\centerline{\fcolorbox{Red}{yellow}{\color{RedViolet}{
  $\frac{73}{192}  |\tau_n|^2+\frac{8}{3}.$}}}
\end{theorem}
}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\ms \ms
Denote by $\mult(v)$ the number
  of paths from initial node $\varepsilon$ to $v$.
  \ms\ms
  For $2 \le i \le n-2$, by simple induction we obtain
\ms \ms
  $$\mult(\tau_i)=\mult(\bar{\tau}_i)=2^{i-1}$$
  \ms \ms $$ \mult(\sigma_i)=\mult(\bar{\sigma}_i)=2^{i-2}.$$
}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\noindent
The total number of different factors of $\tau_n$ equals
\ms \ms
  $$S(\tau_n)=\sum_{e=(u,v)\,\in\,E(G_n)}\ \mult(u)\cdot|e|.$$
\ms
\ms
  We compute $S(\tau_n)$ level by level, using the fact that
  $$|\tau_i|=|\bar{\tau}_i|=2^i
\quad\mbox{and}\quad |\tau'_i|=|\bar{\tau}'_i|=3 \cdot 2^{i-2}.$$
}
\esl




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\noindent

The \fcolorbox{MyDarkBlue}{GreenYellow}{{local period}} at inter-position $p_i$ as $|v|$, where $vv$ is the
shortest square centered at this inter-position.
The \fcolorbox{MyDarkBlue}{GreenYellow}{{critical factorization point}} of a word $u$ is
an inter-position of $u$ for which the local period equals the (global)
period of $u$.
\ms \ms
\begin{theorem}
  The critical factorization point of the \TM
 word $\tau_n$, for $n \ge 4$, is
  the inter-position $p_i$ for $i=2^{n-1}+1$.
\end{theorem}
}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl{\color{MyDarkBlue} \large
\noindent

  It is a known fact  that the critical factorization point
  of a word $u$ corresponds to the first letter of the shorter of the following two suffixes:
  \begin{enumerate}%[(1)]
    \item the lexicographically largest suffix of $u$ under the standard order of letters: $0&lt;1$
    \item the lexicographically largest suffix of $u$ under the reversed order of letters: $1\prec0$.
  \end{enumerate}

}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl
{\color{MyDarkBlue} \large
\noindent
To get suffix (1) we traverse $G_n$, starting from $\varepsilon$,
  along the lexicographically largest path, i.e.:
  \ms \ms
  \centerline{\large \fboxsep=5mm \fboxrule=0.1mm
  \fcolorbox{MyDarkBlue}{yellow}{{\color{RedViolet}
  $
    \varepsilon \sarrow{\bar{\tau}_0} \bar{\tau}_0 \sarrow{\bar{\tau}_1} \tau_2 \sarrow{\bar{\tau}_2} \tau_3
    \sarrow{\bar{\tau}_3} \ldots \sarrow{\bar{\tau}_{n-3}} \tau_{n-2} \sarrow{\tau'_n} \tau_n.
  $}}}
 \ms \ms
\noindent
  The length of this path is
  the length of $\tau_n$ minus 1, hence it is $2^n-1$.
   }
  \esl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl
{\color{MyDarkBlue} \large
  On the other hand, the suffix (2) corresponds to the maximal path starting from
  $\varepsilon$ that always prefers 0:
  \ms
  \centerline{\large \fboxsep=5mm \fboxrule=0.1mm
  \fcolorbox{MyDarkBlue}{yellow}{{\color{RedViolet}$
    \varepsilon \sarrow{\tau_0} \tau_0 \sarrow{\tau_1} \bar{\tau}_2 \sarrow{\tau_2} \bar{\tau}_3
    \sarrow{\tau_3} \ldots \sarrow{\tau_{n-3}} \bar{\tau}_{n-2} \sarrow{\tau_{n-2}} \tau_n.
  $}}}
  \ms
  \noindent
  The length of this path is
   $|\bar{\tau}_{n-1}|-1$ , since
  the label of this path equals $\bar{\tau}_{n-1}$ with the first letter removed.
 Thus the suffix (2) has length $2^{n-1}-1$ and is always shorter than (1) and using it we obtain the
  critical factorization point:
  $$|\tau_n|-(2^{n-1}-1)=2^{n-1}+1$$

}
\esl
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bsl

{\color{MyDarkBlue} \large
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=12cm]{2paths_min-crop}
\end{center}
\end{figure}
\ms
The red path = maximal suffix (with $0&lt;1$)
\\
The (completely) upper path = $\tau_n$.
\ms
The blue path = maximal suffix (with $1&lt;0$)
\\
The (completely) lower path = $\bar{\tau}_{n-1}$.

}
  \esl
 \bsl{\color{MyDarkBlue}
Let $G'$ be an infinite labeled graph obtained from $G$ by removing all vertices
$\sigma_n$, $\bar{\sigma}_n$ and replacing pairs of edges traversing
them with single edges with concatenated labels.
We call $G'$ the \emph{pseudo-cdawg} of $\tau$.
\ms
We say that a weighted directed graph with a designated source vertex has
\emph{$k$-counting property} if there are exactly $k$ different paths for each length
$n&gt;0$ starting from the source and ending in some arbitrary vertex.
\ms
Let $H$ be a directed weighted graph obtained from $G'$ by replacing labels
of edges with their lengths.
Note that the edges of $H$ can be divided into three groups: the backbone
(two series of edges $1,1,2,4,8,\ldots$), in-branch edges
(two series $3,6,12,24,\ldots$) and inter-branch edges
}
\esl
 \bsl{\color{MyDarkBlue}

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=12.5cm]{pseudocdawginfty_min-crop}
\end{center}
\end{figure}

  The pseudo-cdawg for $\tau$ --- an initial part.

}\esl \bsl{\color{MyDarkBlue}\large

\begin{figure}
\begin{center}
\includegraphics[width=12.5cm]{pseudocdawginftyweighted_min-crop}
\end{center}
\end{figure}

The initial part of the weighted graph $H$ obtained from $G'$ by replacing labels
with their lengths.
This graph has 2-counting property.

}\esl \bsl{\color{MyDarkBlue} \large


\begin{figure}
\begin{center}
\includegraphics[width=12.5cm]{1counting_min-crop}
\end{center}
\end{figure}

The initial part of the weighted graph $H'$ obtained from $H$ by removing
the vertex $\varepsilon$ and gluing the upper and lower branch.
This graph has 1-counting property.
}\esl
\bsl{\color{MyDarkBlue} \large


}
\esl
\end{document} </pre></body></html>