% !TeX encoding = UTF-8
% !TeX spellcheck = en_US
\documentclass[draft]{adm-paper}
\usepackage{amsfonts,amsmath,amsthm,amscd,amssymb,latexsym,hyperref}

\begin{document}
	
\title{Free products of semigroups defined by automata}%Paper title
\author{Eugenia Kochubinska and Andriy Oliynyk}%Authors names
\shorttitle{Free products of semigroups defined by automata}%Short paper title for the headers
\shortauthor{E.Kochubinska, A.Oliynyk}%Short authors names for the headers
\address[E.~Kochubinska]{Taras Shevchenko National University of Kyiv, Volodymyrska 60, 01601 Kyiv, Ukraine}{ekochubinska@knu.ua}{}	
\address[A.~Oliynyk]{Taras Shevchenko National University of Kyiv, Volodymyrska 60, 01601 Kyiv, Ukraine}{aolijnyk@gmail.com}{}%www.fauthor.domain.com
	
%\thanks{}
	
\communicated{Anatoliy Petravchuk}
	
\research% Type of the paper. \survey command may be used also.
	
%\date{11.05.2003}
	
%Change theorem environments according to your needs...
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\theoremstyle{definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
	
\maketitle
	
\begin{abstract}
It is shown that the free product of semigroups defined by (finite) automata over a finite alphabet is defined by (finite) automata over the same alphabet.
\end{abstract}
	
\subjclass{2020}{20M05, 20M30, 20M35}
	
\keywords{Free product of semigroups, finite automaton, group defined by automata}
	
\section{Introduction}
\label{section_Introduction}
Automata, especially finite, over finite alphabets give efficient way to define semigroups and inverse semigroups. Defined in this way they naturally act as endomorphisms or partial automorphisms of regular rooted trees respectively (\cite{MR1841755, MR2367514, MR2738551, MR4305508}). On of the natural questions is to understand which semigroup theoretical operations preserve the property to be defined by automata. Semigroups defined by automata are rich of free subsemigroups \cite{MR1629906}. They are convenient to generate monogenic free inverse semigroups (\cite{MR2738551,MR4133021,MR4729944}). 

More sophisticated approach to define semigroups by automata is to generate a semigroups using all states of a given automaton. Semigroups defined in this way are referred as automaton semigroups. In \cite{MR3345953, MR3634703} the authors show that the class of automaton semigroups is very close to be closed under the free product. However, the complete answer is still under investigation.

The main our result is Theorem~\ref{thm_free_product}. We show that for arbitrary semigroup defined by automata over a finite alphabet their free product is defined by automata over the same alphabet. Moreover, if the automata defining initial semigroups are finite then their free  product is defined by finite automata as well. In other words, the finite state wreath power \cite{MR2796035} of the symmetric transformation semigroup is closed under free products.

The paper is organized as follows. In Section~\ref{section_preliminaries} we recall basic definitions and notation involving transformations defined by automata over finite alphabets. For more detailed introduction to the topic one can refer to \cite{MR1841755, MR2738551, MR2583696}. In Section~\ref{thm_reduction_alphabet} we prove an auxiliary statement that allows us to reduce the  size of the alphabet. Section~\ref{section_actions_of_free_products} contains the proof of the main result of the paper.
	
\section{Preliminaries}
\label{section_preliminaries}
		
Let $\mathsf{X}$ be a finite alphabet with $|\mathsf{X}| > 1$. The set $\mathsf{X}^* = \cup_{i=0}^\infty \mathsf{X}^i$, consisting of all finite words over $\mathsf{X}$, including the empty word $\Lambda$, forms a free monoid with basis $\mathsf{X}$ under concatenation. The length of a word $w = x_1 \ldots x_n \in \mathsf{X}^*$, where $x_1, \ldots, x_n \in \mathsf{X}$, is $n$ and is denoted by $|w|$; i.e., $w \in \mathsf{X}^{|w|}$.  
	
The right Cayley graph of the monoid $\mathsf{X}^*$ with respect to the basis $\mathsf{X}$ defines a structure of a regular rooted tree $\mathcal{T}(\mathsf{X})$ on $\mathsf{X}^*$ as its vertex set. Two words $u, v \in \mathsf{X}^*$ are joined by an edge if and only if $u = vx$ or $v = ux$ for some $x \in \mathsf{X}$. The empty word $\Lambda$ serves as the root of $\mathcal{T}(\mathsf{X})$.  
	
For every $n \geq 0$, the set $\mathsf{X}^n$ forms the $n$-th level of this tree, and the union $\mathsf{X}^{(n)} = \cup_{i=0}^n \mathsf{X}^i$ represents the vertex set of a regular rooted subtree of depth $n$.  

	
An automaton over alphabet $\mathsf{X}$ is a triple $\mathcal{A}=(Q, \lambda, \mu)$ such that $Q$ is a non-empty set, the set of states, $\lambda : Q \times \mathsf{X} \to Q$ is the transition function, $\mu : Q \times \mathsf{X} \to Q$ is the output function.  The automaton $\mathcal{A}$ is called finite if the set $Q$ of its states is finite.
	
The transition function $\lambda$ and the output function $\mu$ can be recursively extended to the set $Q \times \mathsf{X}^{*}$ using the equalities
\[
\lambda(q,\Lambda)=q, \quad \lambda(q,xw)=\lambda(\lambda(q,x),w),
\]
\[
\mu(q,\Lambda)=\Lambda, \quad \mu(q,xw)=\mu(q,x)\mu(\lambda(q,x),w),
\]
where $q\in Q$, $x\in \mathsf{X}$, $w\in \mathsf{X}^*$. Then at each state $q\in Q$ the automaton $\mathcal{A}$ defines a transformation $\mu_{q}$ on the set $\mathsf{X}^{*}$ by the following rule
\[
\mu_{q}(w)=\mu(q,w), \quad w \in \mathsf{X}^{*}.
\]

We say that a transformation $f$ on $\mathsf{X}^{*}$ is defined by an automaton over $\mathsf{X}$ if $f=\mu_{q}$ for some automaton $\mathcal{A} = (Q, \lambda, \mu)$ and its state $q$. All transformations defined by automata over $\mathsf{X}$ form a semigroup $SA(\mathsf{X})$ under superposition. The semigroup $SA(\mathsf{X})$ is the semigroup of endomorphisms of the rooted tree $\mathcal{T}(\mathsf{X})$. 
All transformations on $\mathsf{X}^{*}$ defined by finite automata form a countable subsemigroup $FSA(\mathsf{X})$ of $SA(\mathsf{X})$. 

For arbitrary transformation $f \in SA(\mathsf{X})$ the minimal automaton $\mathcal{A}_f=(Q_f, \lambda_f, \mu_f)$ such that $\mathcal{A}_f$ defines $f$ is constructed as follows.
Since $f$ is a length preserving and prefix preserving transformation on $\mathsf{X}^{*}$
for each $w \in \mathsf{X}^{*}$ the transformation $f_{w} \in SA(\mathsf{X})$ such that 
\[
f(wu) = f(w)f_{w}(u), \quad u \in \mathsf{X}^{*},
\]
is well defined. The transformation $f_{w}$ is called the state of $f$ at $w$. In particular, $f_{\Lambda} = f$. Then the set of states $Q_f$ of $\mathcal{A}_f$ is the set $\{ f_{w} : w \in \mathsf{X}^{*} \}$. The set $Q_f$ is finite iff $f \in FSA(\mathsf{X})$. The transition and the output functions $\lambda_f, \mu_f$ are defined by the equalities
\[
\lambda_f(f_{w},x) =  f_{wx}, \quad 
\mu_f(f_{w},x) = f_{w}(x), \quad w \in \mathsf{X}^{*}, x \in \mathsf{X}.
\]
Then $f$ is defined by $\mathcal{A}_f$ at its state $f_{\Lambda}$.


\section{Semigroups defined by automata}
\label{section_semigroups_defined_by_automata}
	
We say that a semigroup $S$ is defined by (finite) automata over alphabet $\mathsf{X}$ if $S$ is isomorphic to a subsemigroup of $SA(\mathsf{X})$ (of $FSA(\mathsf{X})$).
	
Assume that $S$ is a subsemigroup of $SA(\mathsf{X})$. For each transformation $f \in S$
consider the minimal automaton $\mathcal{A}_f=(Q_f, \lambda_f, \mu_f)$ over $\mathsf{X}$ such that $f={\mu_f}_{q}$ for some state $q \in Q_f$. For each state $q\in Q_f$	define a transformation $t_q : \mathsf{X} \to \mathsf{X}$ as follows
\[
t_q(x) = \mu_f(q,x), x \in \mathsf{X}.
\]
The set of transformations $\{t_q \mid q\in Q_f, f \in S\}$ generates a subsemigroup in the symmetric transformation semigroup on $\mathsf{X}$.  We call this semigroup the base transformation semigroup associated with $S$ and denote it by $T_S$. The following theorem allows for to reduce the size of the alphabet $\mathsf{X}$.
	
\begin{theorem}
\label{thm_reduction_alphabet}
Let $\mathsf{X}$, $\mathsf{Y}$ be finite alphabets, $S$ be a semigroup defined by (finite) automata over alphabet $\mathsf{X}$ and $T_S$ be the base semigroup associated with $S$. 
If there exists $m\ge 1$ such that $T_S$ is isomorphic as a transformation semigroup on $\mathsf{X}$ to a subsemigroup of the $m$th wreath power of the symmetric transformation semigroup $T(\mathsf{Y})$ acting on $\mathsf{Y}^m$ then the semigroup $S$ is defined by (finite) automata over alphabet $\mathsf{Y}$.
\end{theorem}
	
\begin{proof}
Denote by $\varphi$ an isomorphic embedding of $T_S$ into the $m$th wreath power $\wr_{i=1}^{m} T(\mathsf{Y})^{(i)} $, $T(\mathsf{Y})^{(i)} \simeq T(\mathsf{Y})$, $1\le i \le m$,  and by $\psi$ an injection from $\mathsf{X}$ to $\mathsf{Y}^m$ such that 
\[
\psi(x^t)=(\psi(x))^{\varphi(t)}, \quad x \in \mathsf{X}, t \in T_S.
\]
Let $\mathsf{Y}_1$ be the image of $\mathsf{X}$ under $\psi$. Then $(T_S,\mathsf{X})$ is isomorphic as a transformatation semigroup to $(\varphi(T_S), \mathsf{Y}_1)$. Recall that the wreath product $\wr_{i=1}^{m} T(\mathsf{Y})^{(i)}$ acts on $\mathsf{Y}^{(m)}$. This action is length preserving and prefix preserving. Hence, $\varphi(T_S)$ acts on the set $\mathsf{Y}_2$ that consists of all prefixes of all words from $\mathsf{Y}_1$.


Let $f \in S$ and $\mathcal{A}_f=(Q, \lambda, \mu)$ be the minimal automaton over $\mathsf{X}$ such that $f=\mu_{q_{f}}$ for some state $q_f \in Q$. We define the automaton $\mathcal{B}= (Q_1,\lambda_1, \mu_1)$ over $\mathsf{Y}$. The set of sates $Q_1$ of $\mathcal{B}$ is the Cartesian product $ Q \times \mathsf{Y}^{(m-1)}$. The transition function $\lambda_1$ is defined by the equality
\[
\lambda_1((q,w),y)=
\begin{cases}
		(q,wy), & \text{ if } |w| < m-1 \text{ and } wy \in \mathsf{Y}_2 \\
		(\lambda(q,\psi^{-1}(wy)),\Lambda),&  \text{ if } |w| = m-1 \text{ and } wy \in \mathsf{Y}_1\\
		(q,w),&  \text{ otherwise }
\end{cases}.
\]
Since $\psi$ is injective the definition is correct. The output function $\mu_1$ is defined by the equality
\[
\mu_1((q,w),y)=
\begin{cases}
	y_1, & \text{ if }  wy \in \mathsf{Y}_2 \text{ and } 
	(wy)^{\varphi(\mu_q)}= 	(w)^{\varphi(\mu_q)}y_1\\
	y,&  \text{ otherwise }
\end{cases}.
\]
Since $\varphi(\mu_q)$, $q \in Q$, is length preserving and prefix preserving on $\mathsf{Y}_2$ the definition is correct.
		
To complete the proof we show that the mapping $\mu_{q_f} \mapsto {\mu_1}_{(q_f,\Lambda)}$, $f \in S$, defines an isomorphism.

Consider the monoid monomorphism $\Psi: \mathsf{X}^* \to \mathsf{Y}^*$ that extends injection $\psi$. Then the image $\Psi(\mathsf{X}^*)$ is a free monoid with basis $\mathsf{Y}_1$. Hence, $\Psi(\mathsf{X}^*)=\mathsf{Y}_1^*$. 
		
For arbitrary $q \in Q$, $x \in \mathsf{X}$ and $w \in \mathsf{X}^*$ we have the equalities
\begin{multline*}		
		\Psi(xw)^{{\mu_1}_{(q,\Lambda)}}=(\psi(x)\Psi(w))^{{\mu_1}_{(q,\Lambda)}}=\\
		(\psi(x))^{{\mu_1}_{(q,\Lambda)}}\Psi(w)^{{\mu_1}_{(\lambda(q,x),\Lambda)}}=
		\psi(x^{{\mu}_{q}})\Psi(w)^{{\mu_1}_{(\lambda(q,x),\Lambda)}}.
\end{multline*}
Since $\psi(x) \in \mathsf{Y}_1$  the last equality follows from the definition of the output function $\mu_1$. Therefore, transformation semigroup  $(S, \mathsf{X}^*)$ is isomorphic to a transformation semigroup on $\mathsf{Y}_1^*$.
		
Consider an arbitrary $w\in \mathsf{Y}^*$. Then there exist unique 
$w_1\in \mathsf{Y}_1^*$, $w_2\in \mathsf{Y}_2 \setminus \mathsf{Y}_1$, $w_3\in \mathsf{Y}^*$ such that $w=w_1w_2w_3$ and the word $w_2$ is the longest prefix of $w_2w_3$ from $\mathsf{Y}_2$.
Let $q \in Q$. Then 	
\[
	w^{{\mu_1}_{(q,\Lambda)}}=w_1^{{\mu_1}_{(q,\Lambda)}}w_4w_3 
\]
for some $w_4 \in \mathsf{Y}_2 \setminus \mathsf{Y}_1$ such that for arbitrary $w_1w_2u \in \mathsf{Y}_1^*$, $u \in \mathsf{Y}^*$, the word $w_1^{{\mu_1}_{(q,\Lambda)}}w_4$ is a prefix of $(w_1w_2u)^{{\mu_1}_{(q,\Lambda)}}$.
Hence, the action of  ${\mu_1}_{(q,\Lambda)}$ on $\mathsf{Y}^*$ is completely defined by its action on $\mathsf{Y}_1^*$.
The proof is complete.
\end{proof}

\section{Actions of free products}
\label{section_actions_of_free_products}

\begin{theorem}
	\label{thm_free_product}
	Let $\mathsf{X}$ be a finite alphabets, $|\mathsf{X}|>1$, $S_1,S_2$ be semigroups defined by (finite) automata over $\mathsf{X}$. Then the free product $S_1*S_2$ is defined by (finite) automata over $\mathsf{X}$.	
\end{theorem}

\begin{proof}

Let $\mathsf{X} = \{x_0,x_1, \ldots, x_n\}$, $n\ge 1$. Consider a disjoint alphabet $\mathsf{Y} = \{y_0,y_1, \ldots, y_n\}$ of the same size $n+1$. Assume that $S_1$ and $S_2$ are defined by (finite) automata over $\mathsf{X}$ and $\mathsf{Y}$ correspondingly. For the alphabet
\[
\mathsf{Z} = \mathsf{X} \cup \mathsf{Y} \cup (\{0,\ldots, n\} \times \{0,\ldots, n\})
\]
of size $n^2+4n+3$ we construct a subsemigroup $S$ of $SA(\mathsf{Z})$ (of $FSA(\mathsf{Z})$) isomorphic to the free product $S_1*S_2$. Then we apply Theorem~\ref{thm_reduction_alphabet} to reduce the size of the alphabet and complete the proof.

For each $s\in S_i$, $i=1,2$, consider the minimal automaton $\mathcal{A}_s=(Q, \lambda, \mu)$ over $\mathsf{X}$ or $\mathsf{Y}$ correspondingly such that $s$ is defined by $\mathcal{A}_s$ at some state $q_s \in Q$. Define an automaton $\mathcal{B}_s=(Q_1, \lambda_1, \mu_1)$ over $\mathsf{Z}$. The set of states $Q_1$  is obtained from $Q$ by adding $4$ new states $q_{sI},q_{sT},q_{s0},q_{s1}$. Without loss of generality we assume that $i=1$, i.e. $\mathcal{A}_s$ is an automaton over $\mathsf{X}$. Then the functions $\lambda_1, \mu_1$ are extentions of the functions $\lambda, \mu$ from $Q \times \mathsf{X}$ to $Q_1 \times \mathsf{Z}$ defined for $q \in Q_1$, $z\in \mathsf{Z}$ by the following equations:
\begin{equation*}
	\lambda_1(q,z) =
	\begin{cases}
		q_{s}, & q=q_{sI}, z = x_0 \\
		q_{sI}, & q=q_{sI},  z \in \mathsf{X}, z \ne  x_0  \text{ or } q=q_{s0},q_{s1}, z \in \mathsf{Y} \\
		q_{s0}, & q \in Q, z = (k,l), 0\le k,l \le n, \text{ and } \mu(q,x_k) \ne x_l  \\						
		q_{s1}, & q \in Q, z = (k,l), 0\le k,l \le n, \text{ and } \mu(q,x_k) = x_l \\						
		q_{sT}, & \text{otherwise} \\		
	\end{cases}, 	
\end{equation*}
\begin{equation*}
	\mu_1(q,z) =
	\begin{cases}			
		y_{0}, & q = q_{s1}, z = y_1 \\						
		z, & \text{otherwise} \\		
	\end{cases}. 	
\end{equation*}
In case $i=2$, i.e. $\mathcal{A}_s$ is an automaton over $\mathsf{Y}$ in this definition letters from $\mathsf{X}$ are replaced by letters from $\mathsf{Y}$ and vice versa. Denote by $\hat{s}$ the transformation of $\mathsf{Z}^*$ defined by $B_s$ at $q_{sI}$.

Let $S$ be the semigroup generated by the set  $\{\hat{s} : s\in S_1 \cup S_2\}$. We will show that $S$ splits into the free product $S_1*S_2$. 

Each non-empty word $w$ over $\mathsf{Z}$ can be uniquely decomposed as a product
\[
w=w_1w_2\ldots w_k 
\]
such that each word $w_1,w_2,\ldots, w_k$ is a word over one of the alphabets $\mathsf{X}$, $\mathsf{Y}$ or $\{0,\ldots, n\} \times \{0,\ldots, n\}$. Then for arbitrary $s \in S_1$ the image $w^{\hat{s}}$ has the form
\[
w^{\hat{s}} = w_1^{s_1}w_2^{s_2}\ldots w_k^{s_k}, 
\]
where for each $i$, $1\le i \le k$, the transformation $s_i$ is the identity except the following two cases. Let $w_0 = \Lambda$.
\begin{enumerate}
	\item 
	If $\lambda_1(q_{sI},w_0w_1\ldots w_{i-1})=q_s$ and $w_i=x_0u$ for some $u\in \mathsf{X}^*$ then $w_i^{s_i}= x_0u^{s}$. 
	\item 	
	If $i>2$, $\lambda_1(q_{sI},w_0w_1\ldots w_{i-3})=q_{sI}$,  $w_{i-2}=x_0u$ for some $u\in \mathsf{X}^*$, $w_{i-1}= (k,l)$ for some $k,l$, $0\le k,l \le n$,  such that  $\mu(\lambda(q_s,u),x_k) = x_l$, $w_i=y_1v$ for some $v\in \mathsf{Y}^*$,  then $w_i^{s_i}= y_0v$.
\end{enumerate}
It immediately implies that the mapping $s \mapsto \hat{s}$, $s \in S_1$, is an isomorphism. 
Similarly, the mapping $s \mapsto \hat{s}$, $s \in S_2$, is an isomorphism as well.

Now consider two distinct words 
\[
W_1 = s_{11}\ldots s_{1m_1}, W_2 = s_{21}\ldots s_{2m_2}, 1\le m_1 \le m_2,
\]
such that $s_{ij}$, $s_{ij+1}$, $1\le j < m_i$, $i=1,2$, belong to different semigroups  $S_1,S_2$.
We need to show that $W_1$ and $W_2$ define distinct transformations on $\mathsf{Z}^*$. It is sufficient to find a word over $\mathsf{Z}$ with distinct images under $W_1$ and $W_2$.

Without loss of generality we may assume that $s_{21} \in S_1$. For each $k$, $1 \le k \le m_2$, let
\[
z_k = (k,l_k), 
\]
where $\mu_{s_{2k}}(q_{s_{2k}}, t_k) = t_{l_k}$ and $(t_k, t_{l_k})$ equals $(x_k, x_{l_k})$ or $(y_k, y_{l_k})$ depending on $s_{2k} \in S_2$ or $s_{2k} \in S_1$.
Define a word
\[
u = x_0z_1y_1z_2x_1\ldots z_{m_2}t_1
\]
of length $2m_2+1$. 
Consider 3 cases.

Case 1.
The length of the word $W_1$ is less than the length of the word $W_2$, i.e. $m_1<m_2$.  Then $W_2$ transforms the word $u$ to the word with the last symbol $x_0$ or $y_0$ correspondingly. On the other hand $W_1$ preserves the last symbol of the word $u$.

Case 2.
Words $W_1$ and $W_2$ have the same length, i.e. $m_1=m_2$, and
the first letters of $W_1$ and $W_2$ belong to different semigroups $S_1,S_2$. Under our assumptions it means that $s_{11} \in S_2$. Then $W_1$ preserves the last symbol $x_1$ of the word $u$ as above.

Case 3.
Words $W_1$ and $W_2$ have the same length $m_2$ and $s_{11} \in S_1$. Let $j$ be the smallest index such that $s_{1j} \ne s_{2j}$. Then $1\le j \le m_2$ and both elements $s_{1j},  s_{2j}$ belong to the same semigroup $S_1,S_2$. Without loss of generality we suppose that they belong to $S_1$. Choose a word $v \in \mathsf{X}^{*}$ of the shortest length such that the images of $v$ under $s_{1j},  s_{2j}$ are distinct. Then the last letters of these images are distinct. Let the last letters of $v$ and it image under $s_{2j}$ be $x_{j_1},x_{j_2}$, $0 \le j_1,j_2 \le n$, correspondingly. Consider $z = (j_1,j_2)$. Then 
\[
\lambda_1(q_{s_1},vz) = q_{{s_1}0}, \lambda_1(q_{s_2},vz) = q_{{s_2}1}.
\]
Define a word
\[
u_1 = x_0z_1y_1z_2x_1\ldots z_{j-1}x_{j-1}vzy_1z_{j+1} \ldots z_{m_2}t_1
\]
of length $2m_2+|v|+1$. Then the last symbol of $u_1$ under the action of $W_2$ is
$x_0$ or $y_0$ but $W_1$ preserves the last symbol of $u_1$.



Hence, the semigroup $S$ is isomorphic to the free product $S_1*S_2$.

The base semigroup $T_{S}$ associated with $S$ is a subsemigroup of the direct sum of $T(\mathsf{X})$, $T(\mathsf{Y})$ and the trivial semigroups. Hence $T_{S}$ is isomorphic as a transformation semigroup to the third wreath power of $T(\mathsf{X})$. Applying Theorem~\ref{thm_reduction_alphabet} we complete the proof.
\end{proof}


\bibliographystyle{amsplain}
%\bibliographystyle{plainurl}
\bibliography{references.bib}


%\begin{thebibliography}{10}
		
%\bibitem{MR1841755}
%R.~I. Grigorchuk, V.~V. Nekrashevich, and V.~I. Sushchanski\u{\i}.
%\newblock Automata, dynamical systems, and groups.
%\newblock {\em Tr. Mat. Inst. Steklova}, 231:134--214, 2000.
			
%\bibitem{MR2796035}
%A.~S. Oliynyk.
%\newblock Finite state wreath powers of transformation semigroups.
%\newblock {\em Semigroup Forum}, 82(3):423--436, 2011.
%\newblock \href {https://doi.org/10.1007/s00233-011-9292-z}
%{\path{doi:10.1007/s00233-011-9292-z}}.
		
%\end{thebibliography}
	
\end{document}


