\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,amsfonts}
\usepackage{fullpage}
\renewcommand{\baselinestretch}{1.2}

%BU KISIM PICTURE'LARA FIGURE NUMARASI DUZENLER
\makeatletter
\long\def\@makecaption#1#2{%
  \vskip\abovecaptionskip
  \sbox\@tempboxa{#1 #2}%
  \ifdim \wd\@tempboxa >\hsize
    #1: #2\par
  \else
    \global \@minipagefalse
    \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}%
  \fi
  \vskip\belowcaptionskip}
\makeatother

\def\ok{\longrightarrow}
\def\cift{\twoheadrightarrow}
\def\incl{\lhook\joinrel@>>>\!\!\!\!@>>>}
\def\<{\left<}
\def\>{\right>}
\def\Aut{\mathop{Aut}}
\def\ds{\displaystyle}
\setcounter{MaxMatrixCols}{10}

\hyphenation{author another created financial paper re-commend-ed Post-Script}
\newcommand{\ttbs}{\char'134}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}


\title{Complete Rewriting System and Growth Series for Extended Generalized Hecke Groups}
\author{{Esra K{\i}rm{\i}z{\i} \c{C}etinalp$^{(1)}$,Eylem G{\"{u}}zel Karpuz$^{(1)}$, Recep \c{S}ahin$^{(2)}$}, F\i rat Ate\c{s}$^{(2)}$}
\date{$^{(1)}$ Karamano\u{g}lu Mehmetbey University, Kamil \"{O}zda\u{g} Science Faculty,\\
Department of Mathematics, Yunus Emre Campus, 70100, Karaman-Turkey\\
$^{(2)}$ Bal\i kesir University, Art and Science Faculty,\\
Department of Mathematics, 10145, Bal\i kesir-Turkey\\
{\it esrakirmizi@kmu.edu.tr, \quad eylem.guzel@kmu.edu.tr,\quad rsahin@balikesir.edu.tr,\quad firat@balikesir.edu.tr}}

\begin{document}
\maketitle
\begin{abstract}
\footnotesize{In this paper we obtain a complete rewriting system for monoid presentation of generalized extended Hecke group $\overline{H}_{p,q}$, which is firstly defined in \cite {DKR1}. It gives an algorithm for getting normal form of elements and hence solving the word problem in this group. By
using the normal form structure of elements of $\overline{H}_{p,q}$, we also calculate growth series}.
\end{abstract}

\par
\footnotesize{2010 {\it Mathematics Subject Classification:} 16S15, 20E22, 20M05 
\par
{\it Keywords and Phrases:} Hecke groups, rewriting systems, normal form, growth series}
\normalsize

\section{Introduction and Preliminaries}
\hspace{0.5cm}
\par
Presentations arise in various areas of mathematics such as knot theory, topology, and geometry. Another motivation for studying presentations is the advent of softwares for symbolic computations like $GAP$(Groups, Algorithms and Programming. Providing algorithms to compute presentations of given monoids is a great help for the developers of these softwares. So, in this work, we consider monoid presentation of generalized extended Hecke group $\overline{H}_{p,q}$, which is firstly defined in \cite {DKR1}. By considering this monoid presentation, we find a complete rewriting system. Thus, by this complete rewriting system we characterize the structure of elements of this product. Therefore, we obtain solvability of the word problem.
\par
Algorithmic problems such as the \textit{word, conjugacy} and \textit{isomorphism problems} have played an important role in group theory since the work of M. Dehn in early 1900's. These problems are called \textit{decision problems} which ask for a \textquotedblleft yes\textquotedblright\ or \textquotedblleft no\textquotedblright\ answer to a specific question. Among these decision problems especially the word problem has been studied widely in groups and semigroups (see \cite{AD}). It is well known that the word problem for finitely presented groups is not solvable in general; that is, given any two words obtained by generators of the group, there may be no algorithm to decide whether these words represent the same element in this group. 
\par
There is a long history of studying combinatorial structures in the context of infinite groups. One example is growth series, where for a given set of generators, one counts the number of elements of length $n$, and converts this sequence into a formal power series. By calculating such series, it becomes possible to classify related groups. In this way, in recent years, the growth series have been studied by many authors. They have computed the growth series for some special groups, such as, for surface groups (\cite{can2}), for Fuchsian groups (\cite{flo}), for Heisenberg and Nil groups (\cite{sha}), for hyperbolic groups (\cite{can}) and for Hecke groups (\cite{KR}). Some other authors have also studied the growth series for special group products (extensions). For example, in \cite{Mann}, Mann studied growth series on free products of groups. In \cite{Alonso} and \cite{edj}, the authors calculated the growth series of amalgamated free products and $HNN$-extensions. Johnson (\cite{john}) presented some results on the growth series of wreath products. Recently, in \cite{KCe}, the authors obtained growth series for crossed and two-sided crossed products of groups. 
\par
In this paper, we study on generalized extended Hecke group and show that this group has solvable word problem. To do that, we obtain a complete rewrtiting system and thus construct normal form of elements of this group (see subsection $2.1$). Then by using the normal form structure of elements of generalized extended Hecke group, we calculate growth series (see subsection $2.2$). As known Hecke group and its derivations have especially been of great interest in many fields of Mathematics, for example number theory, automorphic function theory and group theory. 

\begin{center}
(a) \textit{Extended Generalized  Hecke Group}
\end{center}
\par
In \cite{Hecke}, Hecke introduced an infinite class of discrete groups $H(\lambda_{q})$ of linear fractional transformations preserving the upper-half line. The \textit{Hecke group} is the group generated by 
\begin{eqnarray*}
x(z)=-\frac{1}{z}\qquad \text{and}\qquad u(z)=z+\lambda_{q},
\end{eqnarray*}
where $\lambda_q=2cos\pi/q$ for the integer $q\geq 3$. Let $y=xu=-\frac{1}{z+\lambda_{q}}$. Then $H(\lambda_{q})$ has a presentation ${H(\lambda_{q})}=\left\langle x, y ; x^{2}, y^{q}\right\rangle$.
For $q=3$, the resulting Hecke group $H(\lambda_{3})=\textbf{M}$ is the \textit{Modular group} $PSL(2,\mathbb Z)$. By adding the reflection $r(z)=1/\overline{z}$ to the generators of the modular group, the extended modular group $\overline{H}(\lambda_3)=\overline{\textbf{M}}$ was defined in \cite{JT}. Then the \textit{extended Hecke group}, denoted by $\overline{H}(\lambda_q)$, was firstly defined in \cite{Huang} by adding the reflection $r(z)=1/\overline{z}$ to the generators of $H(\lambda_{q})$ similar to the extended modular group $\overline{\textbf{M}}$. The Hecke group $H(\lambda_{q})$ is a subgroup of index $2$ in $\overline{H}(\lambda_q)$. By \cite{JT}, we know that the extended Hecke group $\overline{H}(\lambda_q)$ is isomorphic to $D_2*_{\mathbb Z_2}D_q$ (where $D_q$ is the dihedral group having $2q$ elements) and has a presentation 
\begin{eqnarray} \label{1}
{\overline{H}(\lambda_q)}=\left\langle x, y, r ; x^{2}, y^{q}, r^{2}, (xr)^{2}, (yr)^{2}\right\rangle.
\end{eqnarray}  
Again, for $q=3$, it is obtained the \textit{extended modular group} $\overline {\textbf{M}}$. The Hecke groups $H(\lambda_q)$, extended Hecke groups $\overline{H}(\lambda_q)$ and their normal subgroups have been extensively studied from many points of view in the literature (\cite{CSIK}, \cite{IKS}, \cite{KSÝ}, \cite{KSIC}, \cite{SÝ}, \cite{SIK}, \cite{SIKC}, \cite{SIS}). The Hecke group $H(\lambda_3)$, the modular group $PSL(2,\mathbb Z)$, and its normal subgroups have especially been of great interest in many fields of Mathematics, for example number theory, automorphic function theory and group theory. As a different view, in \cite{COS}, the authors showed that the extended Hecke group $\overline{H}(\lambda_q)$ is the semi-direct product (split extension) of the Hecke group $H(\lambda_{q})$ by a cyclic group of order $2$. Moreover, by considering the presentation (\ref{1}), they gave the necessary and sufficient conditions of (\ref{1}) to be \textit{efficient} (which is an algebraic property) on the minimal number of generators. 
\par
Recently, in \cite{DKR1, DKR2}, the authors defined extended generalized Hecke groups $\overline{H}_{p,q}$, similar to extended Hecke groups $\overline{H}_{q}$, by adding the reflection $R(z)=1/\overline{z}$ to the generators of generalized Hecke groups $H_{p,q}$. Then, extended generalized Hecke groups $\overline{H}_{p,q}$ have a presentation
\begin{eqnarray*}
\overline{H}_{p,q}=\left\langle x, y, r \:;\:x^p=y^q=r^2=(rx)^2=(ry)^2=1\right\rangle\cong D_p*_{\mathbb Z_2}D_q .
\end{eqnarray*}
It is clear that $\left[\overline{H}_{p,q} : H_{p,q}\right]=2$. In \cite{DKR1}, the authors also determined the conjugacy classes of the torsion elements in $\overline{H}_{p,q}$. 

\begin{center}
(b) \textit{String Rewriting System}
\end{center}
\par
Let $X$ be a set and let $X^{*}$ be the free monoid consisting of all words obtained by the elements of $X$. A \textit{string rewriting system}, or simply a rewriting system, on $X^{*}$ is a subset $R\subseteq X^{*}\times X^{*}$ and an element $(u,v)\in R$, also can be written as $u\rightarrow v$, is called a rule of $R$. The idea for a rewriting system is an algorithm for substituting the right-hand side of a rule whenever the left-hand side appears in a word. In general, for a given rewriting system $R$, we write $x\rightarrow y$ for $x,y\in X^{*}$ if $x=uv_1w$, $y=uv_2w$ and $(v_1,v_2)\in R$. Also we write $x\rightarrow^{*}y$ if $x=y$ or $x\rightarrow x_1\rightarrow x_2\rightarrow \cdots \rightarrow y$ for some finite chain of reductions and $\leftrightarrow ^{*}$ is the reflexive, symmetric, and transitive closure of $\rightarrow$. We should note that when $x\rightarrow y$ a good case is when $\left|x\right|\geq \left|y\right|$ always holds. Furthermore an element $x\in X^{*}$ is called irreducible with respect to $R$ if there is no possible rewriting (or reduction) $x\rightarrow y$; otherwise $x$ is called \textit{reducible}. The rewriting system $R$ is called
\begin{itemize}
	\item \textit{Noetherian} if there is no infinite chain of rewritings $x\rightarrow x_1\rightarrow x_2\rightarrow \cdots $ for any word $x\in X^{*}$,
	\item \textit{Confluent} if whenever $x\rightarrow^{*}y_1$ and $x\rightarrow^{*}y_2$, there is a $z\in X^{*}$ such that $y_1\rightarrow^{*}z$ and $y_2\rightarrow^{*}z$,
	\item \textit{Complete} if $R$ is both Noetherian and confluent.  
\end{itemize}
A \textit{critical pair} of a rewriting system $R$ is a pair of overlapping rules such that one of the forms 
\par \textbf{(i)} ($r_1r_2,s$), ($r_2r_3,t$)$\in R$ with $r_2\neq 1$\quad or \quad \textbf{(ii)} ($r_1r_2r_3,s$) ($r_2,t$)$\in R\, ,$ \\
is satisfied. Also a critical pair is \textit{resolved} in $R$ if there is a word $z$ such that $sr_3\rightarrow^{*} z$ and $r_1t\rightarrow^{*} z$ in the first case or $s\rightarrow^{*} z$ and $r_1tr_3\rightarrow^{*} z$ in the second. A Noetherian rewriting system is complete if and only if every critical pair is resolved (\cite{Sims}). Knuth and Bendix have developed an \textit{algorithm} for creating a complete rewriting system $R'$ which is equivalent to $R$, so that any word over $X$ has an (unique) irreducible form with respect to $R'$. By considering overlaps of left-hand sides of rules, this algorithm basicly proceeds forming new rules when two reductions of an overlap word result in two distinct reduced forms. We finally note that the reader is referred to \cite{BO} and \cite{Sims} for a detailed survey on (complete) rewriting systems. 
\par
Throughout this paper, we order words in given alphabet in the deg-lex way by comparing two words first with their degrees (lengths), and then lexicographically when the lengths are equal. Additionally, the notations $(i)\cap(j)$ and $(i)\cup(j)$ will denote the intersection and inclusion overlapping words of left hand side of relations $(i)$ and $(j)$, respectively.


\begin{center}
(c) \textit{Growth Series}
\end{center}
\par
Let $G$ be a finitely presented group with a semigroup generating set $S=\left\{s^{\mp1}_{1},s^{\mp1}_{2}, \cdots s^{\mp1}_{l}\right\}$. By the length $\left|g\right|$ of $g\in G$ with respect to $S$, we mean the quantity 
$$
\left|g\right|= \inf \left\{k: g=s_{1}s_{2}\cdots s_{k},\: s_{i}\in S,\: 1\leq i\leq k\right\}\, .
$$
\par
The function $f: \mathbb{N}\cup \left\{0\right\}\rightarrow \mathbb{N}$ defined by $f(0)=a_{0}=1$ and
$$
f(n)=a_{n}=\#\left\{g\in G:\left|g\right|=n, \:n\geq 1\right\}
$$
is called the \textit{growth function} of $G$ with respect to $S$, and the series
$\beta(z)=\displaystyle{\sum^{\infty}_{n=0}} a_{n}z^{n}$ is called the \textit{growth series} of $G$ (see, for example, \cite{Alonso, har}).
\par
There are several approaches to the evaluation of the growth series and growth functions, according to different methods solving the word problem in a given group. One of them is to obtain normal form of elements of this group. 

\section{Main Results}

\subsection{Rewriting System for Extended Generalized Hecke Group $\overline{H}_{p,q}$}
\hspace{0.5cm}
Let us consider the monoid presentation of extended generalized Hecke group $\overline{H}_{p,q}$. It is not hard to see that the monoid presentation for $\overline{H}_{p,q}$ is given as
\begin{eqnarray}\label{p1}
\overline{H}_{p,q}=\left\langle x, y, r, X, Y \:;\:x^p=y^q=r^2=(rx)^2=(ry)^2=1, xX=Xx=yY=Yy=1\right\rangle.
\end{eqnarray}
By considering the presentation (\ref{p1}), we order the set $\left\{x, y, r, X, Y\right\}^*$ lexicographically by using the ordering $x>y>r>X>Y$. Now we can give the first result of this paper. Before that we explain some notations that used in the proof of Theorem \ref{T1}.
\par
$W_{[x,y]}$, $W^*_{[x,y]}$ and $W^{**}_{[x,y]}$ denote all reduced words obtained by the generators $x$ and $y$. Similarly, $W_{[X,Y]}$, $W^*_{[X,Y]}$ and $W^{**}_{[X,Y]}$ denote all reduced words obtained by $X$ and $Y$. We note that the words $W_{[X,Y]}$ and $W_{[x,y]}$ (and others) are of the same form obtained by replacing $X$ by $x$,$Y$ by $y$ and vice versa. We also note that, the words $\underline{W}_{[X,Y]}$ and $\overline{W}_{[X,Y]}$ denote reduced words without last and first generator of the word $W_{[X,Y]}$, respectively. For instance, let $W_{[X,Y]}=XYXX$. Then we have $\underline{W}_{[X,Y]}=XYX$ and $\overline{W}_{[X,Y]}=YXX$.
\begin{theorem}\label{T1}
A complete rewriting system for extended generalized Hecke group $\overline{H}_{p,q}$ with monoid presentation given by (\ref{p1}) consists of the following relations:
\begin{eqnarray*}
&(1)&\:x^{p}=1, \qquad \qquad\qquad(2)\:y^{q}=1,\qquad \qquad\qquad(3)\:r^{2}=1,\\
&(4)&\:xX=1,\qquad (5)\:Xx=1,\qquad (6)\:yY=1,\qquad(7)\:Yy=1,
\end{eqnarray*}
\begin{displaymath}
(8)\:x^{p-k}=X^{k}\:
\left( \begin{array}{cc}
\text{if p is even then}\quad 1\leq k\leq \frac{p}{2} \\
\text{if p is odd then}\quad 1\leq k\leq \frac{p-1}{2}
\end{array} \right)\end{displaymath}

\begin{displaymath}
(8^{*})\:X^{k}=x^{p-k}\:
\left( \begin{array}{cc}
\text{if p is even then}\quad \frac{p+2}{2}\leq k\leq p \\
\text{if p is odd then}\quad \frac{p+1}{2}\leq k\leq p
\end{array} \right)\end{displaymath}

\begin{displaymath}
(9)\:y^{q-m}=Y^{m}\:
\left( \begin{array}{cc}
\text{if q is even then}\quad 1\leq m\leq \frac{q}{2} \\
\text{if q is odd then}\quad 1\leq m\leq \frac{q-1}{2}
\end{array} \right)\end{displaymath}

\begin{displaymath}
(9^{*})\:Y^{m}=y^{q-m}\:
\left( \begin{array}{cc}
\text{if q is even then}\quad \frac{q+2}{2}\leq m\leq q \\
\text{if p is odd then}\quad \frac{q+1}{2}\leq m\leq q
\end{array} \right)\end{displaymath}

\begin{eqnarray*}
&(10)&\:rx=Xr,\qquad (11)\:ry=Yr,\qquad (12)\:xr=rX,\qquad(13)\:yr=rY,\\
&(14)&\:XrX=r,\qquad (15)\:YrY=r,\qquad (16)\:rW_{[X,Y]}r=W_{[X,Y]},\\
&(17)&\:xW^{*}_{[X,Y]}r=rXW^{*}_{[X,Y]},\qquad (18)\:yW^{**}_{[X,Y]}r=rYW^{**}_{[X,Y]}.
\end{eqnarray*}
\end{theorem}

\begin{proof} 
Since we have the ordering $x>y>r>X>Y$, there are no infinite reduction steps for all overlapping words. Hence the rewriting system is Noetherian. It remains to show that the confluent property holds. To do that we have the following overlapping words and corresponding critical pairs, respectively.
\begin{eqnarray*}
&(1)\cap (1)&: x^{p+1},(x,x),\qquad \qquad\qquad\qquad\quad\:(1)\cap(4): x^{p}X,(X,x^{p-1}),\\
&(1)\cup(8)&: x^{p},(1,x^{k}X^{k}),\qquad\:\:\qquad\qquad\qquad (1)\cap(12): x^{p}r,(r,x^{p-1}rX),\\
&(1)\cap(17)&: x^{p}W^{*}_{[X,Y]}r,(W^{*}_{[X,Y]}r,x^{p-1}rXW^{*}_{[x,y]}),\\
&(2)\cap(2)&: y^{q+1},(y,y),\qquad \qquad\qquad\qquad\qquad(2)\cap(6): y^{q}Y,(Y,y^{q-1}),\\
&(2)\cup(9)&: y^{q},(1,y^{m}Y^{m}),\quad\:\:\qquad\qquad\qquad\quad (2)\cap(13): y^{q}r,(r,y^{q-1}rY),\\
&(2)\cap(18)&: y^{q}W^{**}_{[X,Y]}r,(W^{**}_{[X,Y]}r,y^{q-1}rYW^{**}_{[x,y]}),\\
&(3)\cap(3)&: r^{3},(r,r),\qquad \qquad\qquad\qquad\qquad\quad(3)\cap(10): r^{2}x,(x,rXr),\\
&(3)\cap(11)&: r^{2}y,(y,rYr),\qquad \qquad\qquad\qquad\quad(3)\cap(16): r^{2}W_{[X,Y]}r,(W_{[X,Y]}r,rW_{[x,y]}),\\
&(4)\cap(5)&: xXx,(x,x),\qquad \qquad\qquad\qquad\quad(4)\cap(8^{*}): xX^{k},(x^{k-1},xX^{p-k}),\\
&(4)\cap(14)&: xXrX,(rX,xr),\qquad \qquad\qquad\quad(5)\cap(1): Xx^{p},(x^{p-1},X),\\
&(5)\cap(4)&: XxX,(X,X),\qquad \qquad\:(5)\cap(8): Xx^{p-k},(x^{p-k-1},Xx^{k}),\\
&(5)\cap(12)&: Xxr,(r,XrX),\qquad \qquad(5)\cap(17): XxW^{*}_{[X,Y]}r,(W^{*}_{[X,Y]}r,XrXW^{*}_{[x,y]}),\\
&(6)\cap(7)&: yYy,(y,y),\qquad \qquad\qquad(6)\cap(9^{*}): yY^{m},(Y^{m-1},yY^{q-m}),\\
&(6)\cap(15)&: yYrY,(rY,yr),\qquad \qquad(7)\cap(2): Yy^{q},(y^{q-1},Y),\\
&(7)\cap(6)&: YyY,(Y,Y),\qquad \qquad\quad(7)\cap(9): Yy^{q-m},(y^{q-m-1},YY^{m}),\\
&(7)\cap(13)&: Yyr,(r,YrY),\qquad \qquad\quad(7)\cap(18): YyW^{**}_{[X,Y]}r,(W^{**}_{[X,Y]}r,YrYW^{**}_{[x,y]}),\\
&(8)\cap(4)&: x^{p-k}X,(X^{k}X,x^{p-k-1}),\quad \:(8)\cap(8): x^{p-k+1},(X^{k}x,xX^{k}),\\
&(8)\cap(12)&: x^{p-k}r,(X^{k}r,x^{p-k-1}X),\\
&(8)\cap(17)&: x^{p-k}W^{*}_{[X,Y]}r,(X^{k}W^{*}_{[X,Y]}r,x^{p-k-1}rXW^{*}_{[X,Y]}),\\
&(8^{*})\cap(5)&: X^{k}x,(x^{p-k}x,X^{k-1}),\qquad \qquad(8^{*})\cap(8^{*}): X^{k+1},(x^{p-k}X,Xx^{p-k}),\\
&(8^{*})\cap(14)&: X^{k}rX,\:(x^{p-k}rX,X^{k-1}r),\qquad \qquad(9)\cap(6): y^{q-m}Y,\:(Y^{m}Y,y^{q-m-1}),\\
&(9)\cap(9)&: y^{q-m+1},\:(Y^{m}y,yY^{m}),\qquad \qquad\qquad (9)\cap(13): y^{q-m}r,\:(Y^{m}r,y^{q-m-1}rY),\\
&(9)\cap(18)&: y^{q-m}W^{**}_{[X,Y]}r,\:(Y^{m}W^{**}_{[X,Y]}r,y^{q-m-1}rYW^{**}_{[x,y]}),\\
&(9^{*})\cap(7)&: Y^{m}y,\:(y^{q-m}y,Y^{m-1}),\qquad \qquad\qquad (9^{*})\cap(9^{*}): Y^{m+1},\:(y^{q-m}Y,Yy^{q-m})\\
&(9^{*})\cap(15)&: Y^{m}rY,\:(y^{q-m}rY,Y^{m-1}r),\qquad \quad\qquad (10)\cap(1): rx^{p},\:(Xrx^{p-1},r),\\
&(10)\cap(4)&: rxX,\:(Xrx,r),\qquad \qquad\qquad\qquad (10)\cap(8): rx^{p-k},\:(Xrx^{p-k-1},rX^{k}),\\
&(10)\cap(12)&: rxr,\:(Xr^{2},r^{2}X),\\
&(10)\cap(17)&: rxW^{*}_{[X,Y]}r,\:(XrW^{*}_{[X,Y]}r,r^{2}XW^{*}_{[x,y]}),
\end{eqnarray*}

\begin{eqnarray*}
&(11)\cap(2)&: ry^{q},\:(Yry^{q-1},r),\qquad \qquad\qquad(11)\cap(6): ryY,\:(Yry,r),\\
&(11)\cap(9)&: ry^{q-m},\:(Yry^{q-m-1},rY^{m}),\qquad \qquad(11)\cap(13): ryr,\:(Yr^{2},r^{2}Y),\\
&(11)\cap(18)&: ryW^{**}_{[X,Y]}r,\:(YrW^{**}_{[X,Y]}r,r^{2}YW^{**}_{[x,y]}),\\
&(12)\cap(3)&: xr^{2},\:(rXr,x),\qquad \qquad\qquad(12)\cap(10): xrx,\:(rXx,xXr),\\
&(12)\cap(11)&: xry,\:(rXy,xYr),\qquad \qquad(12)\cap(16): xrW_{[X,Y]}r,\:(rXW_{[X,Y]}r,xW_{[x,y]}),\\
&(13)\cap(3)&: yr^{2},\:(rYr,y),\qquad \qquad\qquad(13)\cap(10): yrx,\:(rYx,yXr),\\
&(13)\cap(11)&: yry,\:(rYy,yYr),\qquad \qquad(13)\cap(16): yrW_{[X,Y]}r,\:(rYW_{[X,Y]}r,yW_{[x,y]}),\\
&(14)\cap(5)&: XrXx,\:(rx,Xr),\qquad \qquad(14)\cap(8^{*}): XrX^{k},\:(rX^{K-1},Xrx^{p-k}),\\
&(14)\cap(16)&: XrW_{[X,Y]}r,\:(r\overline{W}_{[X,Y]}r,XW_{[x,y]})\quad (\text{the word} \: W_{[X,Y]}\: \text{starts with} \: X),\\
&(14)\cap(14)&: XrXrX,\:(r^{2}X,Xr^{2}),\qquad \qquad(15)\cap(7): YrYy,\:(ry,Yr),\\
&(15)\cap(9^{*})&: YrY^{m},\:(rY^{m-1},Yry^{q-m}),\quad \quad(15)\cap(15): YrYrY,\:(r^{2}Y,Yr^{2}),\\
&(15)\cap(16)&: YrW_{[X,Y]}r,\:(r\overline{W}_{[X,Y]}r,YW_{[x,y]})\quad (\text{the word} \: W_{[X,Y]}\: \text{starts with} \: Y),\\
&(16)\cap(3)&: rW_{[X,Y]}r^{2},\:(rW_{[X,Y]}r,W_{[x,y]}r),\\
&(16)\cap(10)&: rW_{[X,Y]}rx,\:(rW_{[X,Y]}Xr,W_{[x,y]}x),\\
&(16)\cap(11)&: rW_{[X,Y]}ry,\:(rW_{[X,Y]}Yr,W_{[x,y]}y),\\
&(16)\cap(14)&: rW_{[X,Y]}rX,\:(r\underline{W}_{[X,Y]}r,W_{[x,y]}X)\quad (\text{the word} \: W_{[X,Y]}\: \text{ends with} \: X),\\
&(16)\cap(15)&: rW_{[X,Y]}rY,\:(r\underline{W}_{[X,Y]}r,W_{[x,y]}Y)\quad (\text{the word} \: W_{[X,Y]}\: \text{ends with} \: Y),\\
&(16)\cap(16)&: rW_{[X,Y]}rW^{'}_{[X,Y]}r,\:(W_{[x,y]}W^{'}_{[X,Y]}r,rW_{[X,Y]}W^{'}_{[x,y]})\\
&(17)\cap(3)&: xW^{*}_{[X,Y]}r^{2},\:(rXW^{*}_{[x,y]}r,xW^{*}_{[X,Y]}),\\
&(17)\cap(10)&: xW^{*}_{[X,Y]}rx,\:(rXW^{*}_{[x,y]}x,xW^{*}_{[X,Y]}Xr),\\
&(17)\cap(11)&: xW^{*}_{[X,Y]}ry,\:(rXW^{*}_{[x,y]}y,yW^{*}_{[X,Y]}Yr),\\
&(17)\cap(14)&: xW^{*}_{[X,Y]}rX,\:(rXW^{*}_{[x,y]}X,x\underline{W}^{*}_{[X,Y]}r)\quad (\text{the word} \: W^{*}_{[X,Y]}\: \text{ends with} \: X)\\
&(17)\cap(15)&: xW^{*}_{[X,Y]}rY,\:(rXW^{*}_{[x,y]}Y,x\underline{W}^{*}_{[X,Y]}r)\quad (\text{the word} \: W^{*}_{[X,Y]}\: \text{ends with} \: Y)\\
&(17)\cap(16)&: xW^{*}_{[X,Y]}rW_{[X,Y]}r,\:(rXW^{*}_{[x,y]}W_{[X,Y]}r,xW^{*}_{[X,Y]}W_{[x,y]})\\
&(18)\cap(3)&: yW^{**}_{[X,Y]}r^{2},\:(rYW^{**}_{[x,y]}r,yW^{**}_{[X,Y]}),\\
&(18)\cap(10)&: yW^{**}_{[X,Y]}rx,\:(rYW^{**}_{[x,y]}x,yW^{**}_{[X,Y]}Xr),\\
&(18)\cap(11)&: yW^{**}_{[X,Y]}ry,\:(rYW^{**}_{[x,y]}y,yW^{**}_{[X,Y]}Yr),\\
&(18)\cap(14)&: yW^{**}_{[X,Y]}rX,\:(rYW^{**}_{[x,y]}X,y\underline{W}^{**}_{[X,Y]}r)\quad (\text{the word} \: W^{*}_{[X,Y]}\: \text{ends with} \: X),\\
&(18)\cap(15)&: yW^{**}_{[X,Y]}rY,\:(rYW^{**}_{[x,y]}Y,y\underline{W}^{**}_{[X,Y]}r)\quad (\text{the word} \: W^{*}_{[X,Y]}\: \text{ends with} \: Y),\\
&(18)\cap(16)&: yW^{**}_{[X,Y]}rW_{[X,Y]}r,\:(rYW^{**}_{[x,y]}W_{[X,Y]}r,yW^{**}_{[X,Y]}W_{[x,y]}),
\end{eqnarray*}

In fact, all these above critical pairs are resolved by reduction steps. We show some of them as follows:
\begin{eqnarray*}
&(1)\cap(17):& x^{p}W^{*}_{[X,Y]}r,(W^{*}_{[X,Y]}r,x^{p-1}rXW^{*}_{[x,y]}),\\
& &x^{p}W^{*}_{[X,Y]}r\longrightarrow \left\{ \begin{array}{ll}
W^{*}_{[X,Y]}r \\
x^{p-1}rXW^{*}_{[x,y]}\rightarrow XrXW^{*}_{[x,y]}\rightarrow rW^{*}_{[x,y]}\rightarrow W^{*}_{[X,Y]}r
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(4)\cap(14):& xXrX,(rX,xr),\\
& &xXrX \longrightarrow \left\{ \begin{array}{ll}
rX \\
xr\rightarrow rX
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(7)\cap(18):& YyW^{**}_{[X,Y]}r,(W^{**}_{[X,Y]}r,YrYW^{**}_{[x,y]}),\\
& &YyW^{**}_{[X,Y]}r\longrightarrow \left\{ \begin{array}{ll}
W^{**}_{[X,Y]}r \\
YrYW^{**}_{[x,y]}\rightarrow rW^{**}_{[x,y]}\rightarrow W^{**}_{[X,Y]}r
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(10)\cap(17):& rxW^{*}_{[X,Y]}r,\:(XrW^{*}_{[X,Y]}r,r^{2}XW^{*}_{[x,y]}),\\
& &rxW^{*}_{[X,Y]}r\longrightarrow \left\{ \begin{array}{ll}
XrW^{*}_{[X,Y]}r \rightarrow XW^{*}_{[x,y]}\\
r^{2}XW^{*}_{[x,y]}\rightarrow XW^{*}_{[x,y]}
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(12)\cap(16):& xrW_{[X,Y]}r,\:(rXW_{[X,Y]}r,xW_{[x,y]}),\\
& &xrW_{[X,Y]}r\longrightarrow \left\{ \begin{array}{ll}
rXW_{[X,Y]}r \rightarrow xW_{[x,y]}\\
xW_{[x,y]}
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(14)\cap(16):& XrW_{[X,Y]}r,\:(r\overline{W}_{[X,Y]}r,XW_{[x,y]})\:\:(\text{the word} \: W_{[X,Y]}\: \text{starts with} \: X),\\
& &XrW_{[X,Y]}r\longrightarrow \left\{ \begin{array}{ll}
r\overline{W}_{[X,Y]}r\rightarrow \overline{W}_{[x,y]}\\
XW_{[x,y]}\rightarrow \overline{W}_{[x,y]}
\end{array} \right.
\end{eqnarray*}

\begin{eqnarray*}
&(18)\cap(14):& yW^{**}_{[X,Y]}rX,\:(rYW^{**}_{[x,y]}X,y\underline{W}^{**}_{[X,Y]}r)\:\:(\text{the word} \: W_{[X,Y]}\: \text{ends with} \: X),\\
& &yW^{**}_{[X,Y]}rX\longrightarrow \left\{ \begin{array}{ll}
rYW^{**}_{[x,y]}X \rightarrow rY \underline{W}^{**}_{[x,y]}\\
y\underline{W}^{**}_{[X,Y]}r\rightarrow rY \underline{W}^{**}_{[x,y]}
\end{array} \right.
\end{eqnarray*}

\par
After all these above processes, since the rewriting system is Noetherian and confluent it is complete.
\par
Hence the result.
\end{proof}

\vskip 0.3cm  
By considering Theorem \ref{T1}, we have the following other result of this subsection.

\begin{corollary}\label{C1}
Let $R$ be the set of relations $(1)-(18)$ given in Theorem \ref{T1}. Let us consider the word $u\in \overline{H}_{p,q}$. Then the normal form $C(u)$ has a form
\begin{eqnarray*}
W_{[X,Y]}rW^{1}_{[X,Y]}W^{1'}_{[x,y]}W^{2}_{[X,Y]}W^{2'}_{[x,y]}\cdots W^{t}_{[X,Y]}W^{t'}_{[x,y]},
\end{eqnarray*}
where $W_{[X,Y]}$, $W^{i}_{[X,Y]}$ and $W^{i'}_{[x,y]}$ ($1\leq i\leq t$) are $R$-reduced words. In addition $W^{i}_{[X,Y]}W^{i'}_{[x,y]}$ ($1\leq i\leq t$) and $W^{j'}_{[x,y]}W^{j+1}_{[X,Y]}$ ($1\leq j\leq t-1$) are also $R$-reduced words.
\end{corollary}

\par
By considering Corollary \ref{C1}, we can give the following result.
\begin{theorem}\label{Tword}
The word problem for extended generalized Hecke group $\overline{H}_{p,q}$ given by monoid presentation in (\ref{p1}) is solvable.
\end{theorem}

\par
We note that in \cite{KC}, the authors obtained normal form of elements of extended Hecke group ${\overline{H}(\lambda_q)}$ by using Gr\"{o}bner-Shirshov basis theory. Thus they showed the solvability of the word problem for that group. Here, by Theorem \ref{Tword}, we generalized the result given in \cite{KC}. 

\subsection{Growth Series for Extended Generalized Hecke Group $\overline{H}_{p,q}$}
\hspace{0.5cm}
In this subsection, we study growth series, which is other main subject of this paper, on extended generalized Hecke group $\overline{H}_{p,q}$. So we have the following result.
\begin{theorem}\label{s1}
The growth series for extended generalized Hecke group $\overline{H}_{p,q}$ is
\begin{eqnarray*}
\overline{H}_{p,q}(z)=\frac{(1+(p-1)z)(1+(q-1)z)(1+z)}{1-(p-1)(q-1)z^{2}}.
\end{eqnarray*}
\end{theorem}

\begin{proof} 
Since $\overline{H}_{p,q}\cong D_p*_{\mathbb Z_2}D_q$, to obtain growth series of $\overline{H}_{p,q}$, we take into consideration growth series of $D_p*_{\mathbb Z_2}D_q$. Firstly, we consider the presentation of $D_{p}=\left\langle x, y ;\: x^{p}, y^{2}, (xy)^{2} \right\rangle$ and we take the word $w_{1}\in D_{p}$. Then the normal form $C(w_{1})$ of the word $w_{1}$ has a form $x^{k}y^{l}$, where $0\leq k\leq p-1$ and $0\leq l\leq 1$. Growth series $D_{p}(z)$ of this normal form is computed as a separate product of the growth series of every word (see, e.g. \cite{har}). That is, $D_{p}(z)$ is equal to product of the growth series of words of the forms $x^{k}\:(0\leq k\leq p-1)$  and  $y^{l}\:(0\leq l\leq 1)$. Growth series of words of the forms $x^{k}\:(0\leq k\leq p-1)$ and $y^{l}\:(0\leq l\leq 1)$ with respect to generating sets $S_{1}=\left\{x,x^{2},\cdots, x^{p}\right\}$ and $S_{2}=\left\{y,y^{2}\right\}$ are $1+(p-1)z$ and $1+z$, respectively. So, we obtain $D_{p}(z)=(1+(p-1)z)(1+z)$ with respect to the generating set $S_{1}\cup S_{2}$. Similarly, the growth series of the dihedral group $D_{q}$ of order $2q$ is $D_{q}(z)=(1+(q-1)z)(1+z)$.
\par
Hence, by \cite{Alonso}, we have 
\begin{eqnarray*}
\frac{1}{\overline{H}_{p,q}(z)}=\frac{1}{(D_{p}*_{\mathbb{Z}_{2}}D_{q})(z)}&=&\frac{1}{D_{p}(z)}+\frac{1}{D_{q}(z)}-\frac{1}{\mathbb{Z}_{2}(z)}\\
&=&\frac{1}{(1+(p-1)z)(1+z)}+\frac{1}{(1+(q-1)z)(1+z)}-\frac{1}{(1+z)}\\
&=&\frac{1-(p-1)(q-1)z^{2}}{(1+(p-1)z)(1+(q-1)z)(1+z)}.
\end{eqnarray*}
\end{proof}

%\textbf{Acknowledgement.} 
 
\begin{thebibliography}{10}

\bibitem{AD} S. I. Adian, V.G. Durnev, Decision problems for groups and semigroups, \textit{Russian Math. Surveys} \textbf{55}(2) (2000) 207-296.

\bibitem{Alonso} J. M. Alonso, Growth functions of amalgams, \textit{in Arboreal Group Theory}, Proceedings of a Workshop Held September 13–16, 1988, editors in Roger C. Alperin, Springer.

\bibitem{BO} R. V. Book, F. Otto, \textit{String-Rewriting Systems}, Springer-Verlag, New York, 1993.

\bibitem{CSIK}  I. N. Cang\"{u}l, R. \c{S}ahin, S. Ikikarde\c{s}, \"{O}. Koruoglu, Power subgroups of some Hecke groups II, \textit{Houston J. Math.} \textbf{33}(1) (2007) 33–-42.

\bibitem{can2} J. Cannon, The growth of the closed surface groups and the compact hyperbolic Coxeter groups, preprint (1980).

\bibitem{can} J. Cannon, The combinatorial structure of compact discrete hyperbolic groups, \textit{Geometriae Dedicata} \textbf{16} (1984) 123-148.

\bibitem{COS} A. S. \c{C}evik, N. Y. \"{O}zg\"{u}r, R. \c{S}ahin, The extended Hecke groups as semi-direct products and related results, \textit{Int. J. Appl. Math. Stat.} \textbf{13}(08) (2008) 63-72.  

\bibitem{DKR1} B. Demir, \"{O}. Koruoglu, R. \c{S}ahin, Conjugacy classes of extended generalized Hecke groups, \textit{Revista De La Union Mat.Argentina} \textbf{57}(1) (2016) 49-56.

\bibitem{DKR2} B. Demir, \"{O}. Koruoglu, R. \c{S}ahin, Some normal subgroups of extended generalized Hecke groups, \textit{Hacettepe Journal of Math. and Sta.} \textbf{45}(4) (2016) 1023-1032.

\bibitem{edj} M. Edjvet, D. L. Johnson, The growth of certain amalgamated free products and HNN-extensions, \textit{J. Austral. Math. Soc.(Series A)} \textbf{52} (1992) 285-298.

\bibitem{flo} W. Floyd, S. Plotnik, Growth functions on Fuchsian groups and the Euler characteristic, \textit{Invent. Math.}, \textbf{88} (1987) 1-29.

\bibitem{har} P. de la Harpe, \textit{Topics in Geometric Group Theory}, Chicago Lectures in Mathematics, 2000.

\bibitem{Hecke} E. Hecke, \"{U}ber die bestimmung dirichletscher reihen durch ihre funktionalgleichungen, \textit{Math. Ann.} \textbf{112} (1936) 664-699.

\bibitem{Huang} S. Huang, Generalized Hecke groups and Hecke polygons, \textit{Ann. Acad. Sci. Fenn. Math.} \textbf{24}(1) (1999) 187-214.

\bibitem{IKS} S. Ikikarde\c{s}, \"{O}. Koruoglu, R. \c{S}ahin, Power subgroups of some Hecke groups, \textit{Rocky Mountain J. Math.} \textbf{36}(2) (2006), 497–-508.

\bibitem{JT} G. A. Jones, J.S. Thornton, Automorphisms and congruence subgroups of the Extended Modular group, \textit{J. London Math. Soc.} \textbf{34}(2) (1986) 26-40.

\bibitem{john} D. L. Johnson, Rational growth of wreath products, \textit{Cambridge University Press}, \textbf{160} (1991) 309-315.

\bibitem{KCe} E. G. Karpuz and E. K. \c{C}etinalp, Growth series of crossed and two-sided crossed products of cyclic groups, \textit{Mathematica Slovaca} accepted for publication.

\bibitem{KC} E. G. Karpuz, A. S. \c{C}evik, Gr\"{o}bner–-Shirshov bases for extended modular, extended Hecke, and picard groups, \textit{Mathematical Notes} \textbf{92}(5) (2012) 636-642.

\bibitem{KSÝ} \"{O}. Koruoglu, R. \c{S}ahin, S. Ikikarde\c{s}, The normal subgroup structure of the Extended Hecke groups, \textit{Bull. Braz. Math. Soc. (N.S.)} \textbf{38}(1) (2007) 51-65.

\bibitem{KSIC} \"{O}. Koruoglu, R. \c{S}ahin, S. Ikikarde\c{s}, I.N. Cang\"{u}l, Normal subgroups of Hecke groups $H(\lambda)$, \textit{Algebras and Representation Theory} \textbf{13}(2) (2010) 219-230.

\bibitem{KR} M. Kreuzer, G. Rosenberger, Growth in Hecke groups, \textit{Contemporary Mathematics} \textbf{629} (2014) 49-56.

\bibitem{Mann} A. Mann, The growth of free products, \textit{Journal of Algebra} \textbf{326} (2011) 208-217.

\bibitem{SÝ} R. \c{S}ahin, S. Ikikarde\c{s}, \"{O}. Koruoglu, On the power subgroups of the Extended Modular group $\overline{\Gamma}$, \textit{Turkish J. Math.} \textbf{28}(2) (2004) 143-151.

\bibitem{SIK} R. \c{S}ahin, S. Ikikarde\c{s}, \"{O}. Koruoglu, Some normal subgroups of the extended Hecke groups ${\overline{H}(\lambda_p)}$, \textit{Rocky Mountain J. Math.} \textbf{36}(3) (2006) 1033-–1048. 

\bibitem{SIKC} R. \c{S}ahin, S. Ikikarde\c{s}, \"{O}. Koruoglu, I. N. Cang\"{u}l, The connections between continued fraction representations of units and certain Hecke groups, \textit{Bull. Malays. Math. Sci. Soc.} \textbf{33}(2) (2010) 205-–210.

\bibitem{SIS} Z. Sarýgedik, S. Ikikarde\c{s}, R. \c{S}ahin, Power subgroups of the extended Hecke groups, \textit{ Miskolc Math. Notes} \textbf{16}(1) (2015) 483-–490.

\bibitem{sha} M. Shapiro, A geometric approach to growth and almost convexity in some nilpotent groups, \textit{Mathematische Annalen} \textbf{285} (1989) 601-624.

\bibitem{Sims} C. C. Sims, \textit{Computation for Finitely Presented Groups}, Cambridge University Press, 1994.



\end{thebibliography}

\end{document}

1) 
2) 
3) 
4) 
5)