# Gröbner-Shirshov bases and linear bases for free differential type algebras
over algebras

Zihao Qi, Yufei Qin and Guodong Zhou  Zihao Qi, School of Mathematical
Sciences, Fudan University, Shanghai 200433, China<EMAIL_ADDRESS>Yufei
Qin and Guodong Zhou, School of Mathematical Sciences, Shanghai Key Laboratory
of PMMP, East China Normal University, Shanghai 200241, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We study a question which can be roughly stated as follows: Given a (unital or
nonunital) algebra $A$ together with a Gröbner-Shirshov basis $G$, consider
the free operated algebra $B$ over $A$, such that the operator satisfies some
polynomial identities $\Phi$ which are Gröbner-Shirshov in the sense of Guo et
al., when does the union $\Phi\cup G$ will be an operated Gröbner-Shirshov
basis for $B$? We answer this question in the affirmative under a mild
condition in our previous work with Wang. When this condition is satisfied,
$\Phi\cup G$ is an operated Gröbner-Shirshov basis for $B$ and as a
consequence, we also get a linear basis of $B$. However, the condition could
not be applied directly to differential type algebras introduced by Guo, Sit
and Zhang, including usual differential algebras.

This paper solves completely this problem for differential type algebras. Some
new monomial orders are introduced which, together with some known ones,
permit the application of the previous result to most of differential type
algebras, thus providing new operated GS bases and linear bases for these
differential type algebras. Versions are presented both for unital and
nonunital algebras. However, a class of examples are also presented, for which
the natural expectation in the question is wrong and these examples are dealt
with by direct inspection.

###### Key words and phrases:

Differential type OPIs; Gröbner-Shirshov bases; operated algebras; free
operated algebras over algebras; operated polynomial identities

###### 2000 Mathematics Subject Classification:

13P10 03C05 08B20 12H05 16S10

###### Contents

  1. 0.1 From usual GS bases to operated GS bases
  2. 0.2 Free operated algebras over algebras
  3. 0.3 Differential type algebras over algebras
  4. 0.4 Outline of the paper
  5. 1 New monomial orders on free operated semigroups and monoids
    1. 1.1 Free operated semigroups and monoids
    2. 1.2 Monomial orders
  6. 2 Operator polynomial identities and operated GS bases
    1. 2.1 Free operated algebras and operator polynomial identities
    2. 2.2 Operated GS bases for free $\Phi$-algebras
    3. 2.3 Remainder on rewriting systems
  7. 3 Differential type OPIs
    1. 3.1 Unital differential type OPIs
    2. 3.2 Nonunital differential type OPIs
  8. 4 Operated GS bases of free nounital differential type algebras
    1. 4.1 Nonunital GS OPIs of differential type
    2. 4.2 Operated GS bases of free nonunital differential type algebras over algebras
  9. 5 Operated GS bases of free unital differential type algebras
    1. 5.1 Unital GS OPIs of differential type
    2. 5.2 Operated GS bases of free unital differential type algebras over algebras

## Introduction

In our previous work with Wang [25], we studied operated Gröbner-Shirshov (aka
GS) bases for free operated algebras over associative algebras whose operator
satisfies some polynomial identities. This paper continues the work of [25]
and concentrates into differential type algebras.

###  0.1. From usual GS bases to operated GS bases

Gröbner-Shirshov basis theory was invented by Shirshov [30] and Buchberger [6]
in the sixties of last century. It becomes one of the main tools of
computational algebra since then; see for instance [13, 2, 4]. In order to
deal with algebras endowed with operators, Guo et al. introduced a GS basis
theory in operated contexts in a series of papers [14, 38, 16, 11] (see also
[3]) with the goal to attack Rota’s program [28] to classify “interesting”
operators on algebras. For a global view about the state of art, we refer the
reader to the survey paper [12] and for recent development, see [33, 35, 7,
34, 15, 25, 36, 37].

Guo et al. considered operators satisfying some polynomial identities, hence
called operated polynomial identities (aka. OPIs). Via GS basis theory and the
somewhat equivalent theory: rewriting systems, they could define when OPIs are
GS. They are mainly interested into two classes of OPIs: differential type
OPIs and Rota-Baxter type OPIs, which are carefully studied in [16, 38, 11].

In this paper we are interested into differential type OPIs and differential
type algebras.

###  0.2. Free operated algebras over algebras

Recently, there is a need to develop free operated algebras satisfying some
OPIs over a fixed algebras and construct GS bases and linear bases for these
free algebras as long as a GS basis is known for the given algebra. Ebrahimi-
Fard and Guo [10] used rooted trees and forests to give explicit constructions
of free noncommutative Rota-Baxter algebras on modules and sets; Lei and Guo
[18] constructed the linear basis of free Nijenhuis algebras over associative
algebras; Guo and Li [15] gave a linear basis of the free differential algebra
over associative algebras by introducing the notion of differential GS bases.

As in [25], we want to consider a question which can be roughly stated as
follows:

######  Question 0.1.

Given a (unital or nonunital) algebra $A$ with a GS basis $G$ and a set $\Phi$
of OPIs, assume that these OPIs $\Phi$ are GS in the sense of [3, 16, 38, 11].
Let $B$ be the free operated algebra satisfying $\Phi$ over $A$. Under what
conditions, $\Phi\cup G$ will be a GS basis for $B$?

We answer this question in the affirmative under a mild condition in [25,
Theorem 5.9]. When this condition is satisfied, $\Phi\cup G$ is a GS basis for
$B$ and as a consequence, we also get a linear basis of $B$. This result has
been applied to all Rota-Baxter type OPIs, a class of differential type OPIs,
averaging OPIs and Reynolds OPI in [25].

However, this result can NOT be applied directly to all differential type
OPIs. The main reason is that under the chosen monomial order for differential
type OPIs, the condition of [25, Theorem 5.9] is not satisfied.

The goal of this paper is to introduce some new monomial orders which permit
to deal with nearly all free differential type algebras over algebras.

Moreover, we provide a class of counter-examples for which the expectation in
Question 0.1 is wrong; see Theorems 4.12 and 4.13.

###  0.3. Differential type algebras over algebras

A commutative algebra equipped with an operator satisfying the Leibniz rule,
is called a differential algebra. The notion is originated by Ritt [27, 26] in
the algebraic study of differential equations in the 1930s. This mathematical
subject has been developed into a broad realm such as differential Galois
theory [20, 32], differential algebraic geometry and differential algebraic
groups [17]. In recent years, researchers began to investigate noncommutative
differential algebras in order to broaden the scope of the theory to include
path algebras, for instance, and to have a more meaningful differential Lie
algebra theory [23, 24] and also from an operadic point of view [19, 9]. There
are also some recent work dealing with other algebraic structures endowed with
derivations [29, 8, 31].

As mentioned above, [25, Theorem 5.9] can NOT be applied directly to all
differential type OPIs in order to obtain GS bases and linear bases for free
differential type algebras over algebras. In this paper, we introduce some new
monomial orders and solve completely this question.

Our method is as follows: We change a differential type OPI to an equivalent
one in the sense of Definition 2.5; by choosing convenient monomial orders, we
can apply [25, Theorem 5.9] to obtain a GS basis; as a consequence, we get a
linear basis. We also deal with the problem in the nonunital case; see Theorem
2.15. Quite interestingly, there are some exceptional cases for which our
method could not apply and we treat these cases directly.

We would like to mention that Guo and Li introduced the notion of differential
GS bases to deal with the above problem in [15] and their method is completely
different from ours; see Remark 5.12.

###  0.4. Outline of the paper

This paper is organized as follows. In Section 1 some basic definitions and
constructions of free objects in operated contexts are recalled and some new
monomial orders are introduced. Section 2 contains an account of the theory of
operated GS bases, which serve as a main tool in this paper; the main result
of [25] is recalled and a nonunital version is presented; a remainder about
the basic theory of rewriting systems. In Section 3, we consider differential
type OPIs and they are replaced by some equivalent ones. Section 4 is devoted
to operated GS bases and linear bases for free nonunital differential type
algebras over an algebra, while the last section considers unital ones.

Notation: Throughout this paper, ${\mathbf{k}}$ denotes a base field. All the
vector spaces and algebras are over ${\mathbf{k}}$.

##  1\. New monomial orders on free operated semigroups and monoids

In this section, we recall the construction of free operated semigroups and
monoids due to Guo [14]. We will define a new monomial order
$\leq_{{\mathrm{dl}}}$ on free operated semigroups by combining several well
orders and extend it to a monomial order $\leq_{{\mathrm{udl}}}$ on free
operated monoids via Remark 1.2. The main results of this paper will highly
depend on these two new monomial orders.

###  1.1. Free operated semigroups and monoids

######  Definition 1.1 ([14, 38, 16, 11]).

An operated semigroup is a semigroup $S$ with a map $P:S\rightarrow S$ (which
is not necessarily a homomorphism of semigroups). Operated monoids can be
defined similarly. For operated ${\mathbf{k}}$-algebra (resp. unital operated
${\mathbf{k}}$-algebra), we ask additionally that the operator should be a
${\mathbf{k}}$-linear map.

We use $\mathfrak{OpAlg}$ (resp. $\mathfrak{uOpAlg}$) to denote the category
of operated ${\mathbf{k}}$-algebras (resp. unital operated
${\mathbf{k}}$-algebras) with obvious morphisms.

Throughout this section, $X$ denotes a set. Denote by ${\mathbf{k}}X$ (resp.
${\mathcal{S}}(X)$, ${\mathcal{M}}(X)$) the free ${\mathbf{k}}$-space (resp.
free semigroup, free monoid) generated by $X$.

We recall the construction of the free operated semigroup over a given set $X$
due to Guo [14].

For a set $X$, denote by $\lfloor X\rfloor$ the set of the formal elements
$\lfloor x\rfloor,x\in X$. The inclusion $X\hookrightarrow X\sqcup\left\lfloor
X\right\rfloor$, which identifies $X$ with the first component, induces an
injective semigroup homomorphism

$i_{0,1}:{\mathfrak{S}}_{0}(X):={\mathcal{S}}(X)\hookrightarrow{\mathfrak{S}}_{1}(X):={\mathcal{S}}(X\sqcup\left\lfloor
X\right\rfloor).$

For $n\geq 2$, assume that we have constructed ${\mathfrak{S}}_{n-2}(X)$ and
${\mathfrak{S}}_{n-1}(X)={\mathcal{S}}(X\sqcup\left\lfloor{\mathfrak{S}}_{n-2}(X)\right\rfloor)$
endowed with an injective homomorphism of semigroups
$i_{n-2,n-1}:{\mathfrak{S}}_{n-2}(X)\hookrightarrow{\mathfrak{S}}_{n-1}(X).$
We define the semigroup

${\mathfrak{S}}_{n}(X):={\mathcal{S}}(X\sqcup\left\lfloor{\mathfrak{S}}_{n-1}(X)\right\rfloor)$

and the natural injection

${\rm Id}_{X}\sqcup\left\lfloor
i_{n-2,n-1}\right\rfloor:X\sqcup\left\lfloor{\mathfrak{S}}_{n-2}(X)\right\rfloor\hookrightarrow
X\sqcup\left\lfloor{\mathfrak{S}}_{n-1}(X)\right\rfloor$

induces an injective semigroup homomorphism

$i_{n-1,n}:{\mathfrak{S}}_{n-1}(X)={\mathcal{S}}(X\sqcup\left\lfloor{\mathfrak{S}}_{n-2}(X)\right\rfloor)\hookrightarrow{\mathfrak{S}}_{n}(X)={\mathcal{S}}(X\sqcup\left\lfloor{\mathfrak{S}}_{n-1}(X)\right\rfloor).$

Define ${\mathfrak{S}}(X)=\varinjlim{\mathfrak{S}}_{n}(X)$ and the map sending
$u\in{\mathfrak{S}}_{n}(X)$ to $\left\lfloor
u\right\rfloor\in{\mathfrak{S}}_{n+1}(X)$ induces an operator
$P_{{\mathfrak{S}}(X)}$ on ${\mathfrak{S}}(X)$.

The construction of the free operated monoid ${\mathfrak{M}}(X)$ over a set
$X$ is similar, by just replacing ${\mathcal{S}}$ by ${\mathcal{M}}$
everywhere in the construction.

######  Remark 1.2.

We will use another construction of ${\mathfrak{M}}(X)$. In fact, add a symbol
$\lfloor 1\rfloor$ to $X$ and form ${\mathfrak{S}}(X\bigsqcup\lfloor
1\rfloor)$, then ${\mathfrak{M}}(X)$ can be obtained from
${\mathfrak{S}}(X\bigsqcup\lfloor 1\rfloor)$ by just adding the empty word
$1$.

It is easy to see that ${\mathbf{k}}{\mathfrak{S}}(X)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(X)$) is the free nonunital (resp, unital) operated
algebra generated by $X$. More constructions of free objects in operated
contexts can be found in [25].

###  1.2. Monomial orders

We need some preliminaries about orders.

######  Definition 1.3.

Let $X$ be a nonempty set.

  * (a)

A preorder $\leq$ is a binary relation on $X$ that is reflexive and
transitive, that is, for all $x,y,z\in X$, we have

    * (i)

$x\leq x$; and

    * (ii)

if $x\leq y,y\leq z$, then $x\leq z$. We denote $x=_{X}y$ if $x\leq y$ and
$x\geq y$. If $x\leq y$ but $x\neq y$, we write $x<y$ or $y>x$.

  * (b)

A pre-linear order $\leq$ on $X$ is a preorder $\leq$ such that either $x\leq
y$ or $x\geq y$ for all $x,y\in X$.

  * (c)

A linear order or a total order $\leq$ on $X$ is a pre-linear order $\leq$
such that $\leq$ is symmetric, that is, $x\leq y$ and $y\leq x$ imply
$x=_{X}y$.

  * (d)

A preorder $\leq$ on $X$ satisfies the descending chain condition, if
$x_{1}\geq x_{2}\geq x_{3}\geq\cdots$, then there exists $N\geq 1$ such that
$x_{N}=_{X}x_{N+1}=_{X}\cdots$. A linear order satisfying the descending chain
condition is called a well order.

Before giving the definition of monomial orders, we need to introduce the
following notions.

######  Definition 1.4 ([3, 16, 38, 11]).

Let $Z$ be a set and $\star$ a symbol not in $Z$.

  * (a)

Define ${\mathfrak{M}}^{\star}(Z)$ to be the subset of
${\mathfrak{M}}(Z\cup\star)$ consisting of elements with $\star$ occurring
only once.

  * (b)

For $q\in{\mathfrak{M}}^{\star}(Z)$ and $u\in{\mathfrak{M}}(Z)$, we define
$q|_{u}\in{\mathfrak{M}}(Z)$ obtained by replacing the symbol $\star$ in $q$
by $u$. In this case, we say $u$ is a subword of $q|_{u}$.

  * (c)

For $q\in{\mathfrak{M}}^{\star}(Z)$ and
$s=\sum_{i}c_{i}u_{i}\in{\mathbf{k}}{\mathfrak{M}}(Z)$ with
$c_{i}\in{\mathbf{k}}$ and $u_{i}\in{\mathfrak{M}}(Z)$, we define

$q|_{s}:=\sum_{i}c_{i}q|_{u_{i}}.$

  * (d)

Define ${\mathfrak{S}}^{\star}(Z)$ to be the subset of
${\mathfrak{S}}(Z\cup\star)$ consisting of elements with $\star$ occurring
only once. It is easy to see ${\mathfrak{S}}^{\star}(Z)$ is a subset of
${\mathfrak{M}}^{\star}(Z)$, so we also have the above definitions for
${\mathfrak{S}}^{\star}(Z)$ by restriction.

######  Definition 1.5 ([3, 16, 38, 11]).

Let $Z$ be a set. We deonte $u<v$ if $u\leq v$ but $u\neq v$ for an order
$\leq$.

  * (a)

A monomial order on ${\mathcal{S}}(Z)$ is a well-order $\leq$ on
${\mathcal{S}}(Z)$ such that

$u<v\Rightarrow uz<vz\text{ and }wu<wv\text{ for any
}u,v,w,z\in{\mathcal{S}}(Z);$

a monomial order on ${\mathcal{M}}(Z)$ is a well-order $\leq$ on
${\mathcal{M}}(Z)$ such that

$u<v\Rightarrow wuz<wvz\text{ for any }u,v,w,z\in{\mathcal{M}}(Z).$

  * (b)

A monomial order on ${\mathfrak{S}}(Z)$ is a well-order $\leq$ on
${\mathfrak{S}}(Z)$ such that

$u<v\Rightarrow q|_{u}<q|_{v}\quad\text{for all }u,v\in{\mathfrak{S}}(Z)\text{
and }q\in{\mathfrak{S}}^{\star}(Z);$

a monomial order on ${\mathfrak{M}}(Z)$ is a well-order $\leq$ on
${\mathfrak{M}}(Z)$ such that

$u<v\Rightarrow q|_{u}<q|_{v}\quad\text{for all }u,v\in{\mathfrak{M}}(Z)\text{
and }q\in{\mathfrak{M}}^{\star}(Z).$

######  Definition 1.6.

  * (a)

Given some preorders $\leq_{\alpha_{1}},\dots,\leq_{\alpha_{k}}$ on a set $X$
with $k\geq 2$, introduce another preorder
$\leq_{\alpha_{1},\dots,\alpha_{k}}$ by imposing recursively

$u\leq_{\alpha_{1},\dots,\alpha_{k}}v\Leftrightarrow\left\\{\begin{array}[]{l}u<_{\alpha_{1}}v,\text{
or }\\\ u=_{\alpha_{1}}v\text{ and
}u\leq_{\alpha_{2},\dots,\alpha_{k}}v.\end{array}\right.$

  * (b)

Let $k\geq 2$ and let $\leq_{\alpha_{i}}$ be a pre-linear order on
$X_{i},~{}1\leq i\leq k$. Define the lexicographical product order
$\leq_{\text{clex}}$ on the cartesian product $X_{1}\times
X_{2}\times\cdots\times X_{k}$ by recursively defining

$(x_{1},\cdots,x_{k})\leq_{\text{clex}}(y_{1},\cdots,y_{k})\Leftrightarrow\left\\{\begin{array}[]{l}x_{1}<_{\alpha_{1}}y_{1},\text{or
}\\\ x_{1}=_{X_{1}}y_{1}\text{ and
}\left(x_{2},\cdots,x_{k}\right)\leq_{\rm{clex}}\left(y_{2},\cdots,y_{k}\right),\end{array}\right.$

where
$\left(x_{2},\cdots,x_{k}\right)\leq_{\rm{clex}}\left(y_{2},\cdots,y_{k}\right)$
is defined by induction, with the convention that $\leq_{\rm{clex}}$ is the
trivial relation when $k=1$.

By the proof of [38, Lemma 5.4(a)], we have the following result:

######  Lemma 1.7.

  * (a)

Let $k\geq 2.$ Let $\leq_{\alpha_{1}},\dots,\leq_{\alpha_{k-1}}$ be pre-linear
orders on $X$, and $\leq_{\alpha_{k}}$ a linear order on $X$. Then
$\leq_{\alpha_{1},\dots,\alpha_{k}}$ is a linear order on $X$.

  * (b)

Let $\leq_{\alpha_{i}}$ be a well order on $X_{i}$, $1\leq i\leq k$. Then the
lexicographical product order $\leq_{\rm{clex}}$ is a well order on the
cartesian product $X_{1}\times X_{2}\times\cdots\times X_{k}$.

Let us first recall the well known degree lexicographical order.

######  Definition 1.8.

Let $X$ be a set endowed with a well order $\leq_{X}$. For $u=u_{1}\cdots
u_{r}\in{\mathcal{S}}(X)$ with $u_{1},\dots,u_{r}\in X,$ define
$\operatorname{deg}_{X}(u)=r$.

Introduce the degree lexicographical order $\leq_{\rm{dlex}}$ on
${\mathcal{S}}(X)$ by imposing, for any $u\neq v\in{\mathcal{S}}(X)$,
$u<_{\rm{dlex}}v$ if

  * (a)

either $\operatorname{deg}_{X}(u)<\operatorname{deg}_{X}(v)$, or

  * (b)

$\operatorname{deg}_{X}(u)=\operatorname{deg}_{X}(v)$, and $u=mu_{i}n$,
$v=mv_{i}n^{\prime}$ for some $m,n,n^{\prime}\in{\mathcal{S}}(X)$ and
$u_{i},v_{i}\in X$ with $u_{i}<_{X}v_{i}$.

It is obvious that the degree lexicographic order $\leq_{\mathrm{dlex}}$ on
${\mathcal{S}}(X)$ is a well order and $\leq_{\mathrm{dlex}}$ can be extended
to ${\mathcal{M}}(X)$ by setting $1$ to be the least element.

For two well ordered sets $X$ and $Y$, one obtains an extended well order on
the disjoint union $X\sqcup Y$ by defining $a<b$ for all $a\in X$ and $b\in
Y$.

We now define a linear order on ${\mathfrak{S}}(X)$, by the following
recursion:

  * (a)

Let $u,v\in{\mathfrak{S}}_{\operatorname{Dlex}_{0}}(X)={\mathcal{S}}(X)$. We
define

$u\leq_{\operatorname{Dlex}_{0}}v\Leftrightarrow u\leq_{\mathrm{dlex}}v.$

  * (b)

Assume that we have constructed a well order $\leq_{\operatorname{Dlex}_{n}}$
on ${\mathfrak{S}}_{n}(X)$ for $n\geq 0$ extending all
$\leq_{\operatorname{Dlex}_{i}}$ for any $0\leq i\leq n-1$. The well order
$\leq_{\operatorname{Dlex}_{n}}$ induces a well order on
$\lfloor{\mathfrak{S}}_{n}(X)\rfloor$ and by imposing $a>b$ for all
$a\in\lfloor{\mathfrak{S}}_{n}(X)\rfloor$ and $b\in X$, we obtain an extended
well order on $X\sqcup\lfloor{\mathfrak{S}}_{n}(X)\rfloor$. Denote by
$\leq_{\operatorname{Dlex}_{n+1}}$ the induced degree lexicographic order on
${\mathfrak{S}}_{n+1}(X)={\mathcal{S}}(X\sqcup\lfloor{\mathfrak{S}}_{n}(X)\rfloor)$.

Obviously $\leq_{\operatorname{Dlex}_{n+1}}$ extends
$\leq_{\operatorname{Dlex}_{n}}$. By a limit process, we get a preorder on
${\mathfrak{S}}(X)$ which will be denoted by $\leq_{\operatorname{Dlex}}$.

It is easy to see that this is a linear order, but it is NOT a well order. An
example is given by

$u\lfloor v\rfloor>\lfloor u\lfloor v\rfloor\rfloor>\lfloor\lfloor u\lfloor
v\rfloor\rfloor\rfloor>\cdots$

for $u,v\in X$.

Recall that an arbitrary element of ${\mathfrak{S}}(X)$ has a unique
expression $u=u_{0}\lfloor u_{1}^{*}\rfloor u_{1}\lfloor
u_{2}^{*}\rfloor\cdots\lfloor u_{r}^{*}\rfloor u_{r}$, where
$u_{0},u_{1},\dots,u_{r}\in{\mathcal{M}}(X)$ and
$u_{1}^{*},u_{2}^{*},\dots,u_{r}^{*}\in{\mathfrak{S}}(X).$ Notice that
$u_{0},u_{1},\dots,u_{r}$ could be the empty word. Define the $P$-breath
$|u|_{P}$ of $u=u_{0}\lfloor u_{1}^{*}\rfloor u_{1}\lfloor
u_{2}^{*}\rfloor\cdots\lfloor u_{r}^{*}\rfloor u_{r}$ to be $r$.

######  Definition 1.9 ([38, Definition 5.3] ).

For two elements $u,v\in{\mathfrak{S}}(X)$,

  * (a)

define

$u\leq_{\operatorname{dgp}}v\Leftrightarrow\operatorname{deg}_{P}(u)\leq\operatorname{deg}_{P}(v),$

where the $P$-degree $\operatorname{deg}_{p}(u)$ of $u$ is the number of
occurrence of $P=\lfloor~{}\rfloor$ in $u$;

  * (b)

define

$u\leq_{\operatorname{dgx}}v\Leftrightarrow\operatorname{deg}_{X}(u)\leq\operatorname{deg}_{X}(v),$

where the $X$-degree $\operatorname{deg}_{X}(u)$ is the number of elements of
$X$ occurring in $u$ (including the repetitive ones);

  * (c)

define

$u\leq_{\operatorname{brp}}v\Leftrightarrow|u|_{P}\leq|v|_{P}.$

######  Definition 1.10.

For any $u\in{\mathfrak{S}}(X)$, let $u_{1},\dots,u_{n}\in X$ be all the
elements occurring in $u$ from left to right. If a half bracket $\lfloor$
(resp. $\rfloor$) is between $u_{i}$ and $u_{i+1}$, where $1\leq i<n$, the
G-degree of this half bracket is defined to be $i$; if there is a half bracket
$\lfloor$ (resp. $\rfloor$) appearing on the left of $u_{1}$ (resp. on the
right of $u_{n}$), we define the G-degree of this half bracket to be $0$
(resp. $n$). We denote $\deg_{G}(u)$ by the sum of the G-degree of all the
half brackets in $u$.

For $u,v\in{\mathfrak{S}}(X)$, define the G-degree order $\leq_{\mathrm{dgg}}$
by

$u\leq_{\mathrm{dgg}}v\Leftrightarrow\deg_{G}(u)\leq\deg_{G}(v).$

It is easy to obtain the following lemma whose proof is thus omitted.

######  Lemma 1.11.

The orders $\leq_{\mathrm{dgp}}$, $\leq_{\mathrm{dgx}}$,
$\leq_{\operatorname{brp}}$ and $\leq_{\mathrm{dgg}}$ are pre-linear orders
satisfying the descending chain condition.

By Lemma 1.7, we can define a linear order $\leq_{\mathrm{dl}}$ on
${\mathfrak{S}}(X)$,

$u\leq_{\mathrm{dl}}v\Leftrightarrow
u\leq_{\mathrm{dgp,dgx,dgg},\operatorname{Dlex}}v\Leftrightarrow\left\\{\begin{array}[]{lcl}u<_{\mathrm{dgp}}v,\text{or
}\\\ u=_{\mathrm{dgp}}v\text{ and }u<_{{\rm dgx}}v,\text{or }\\\
u=_{\mathrm{dgp}}v,u=_{\mathrm{dgx}}v\text{ and }u<_{{\rm dgg}}v,\text{or }\\\
u=_{\mathrm{dgp}}v,u=_{\mathrm{dgx}}v,u=_{\mathrm{dgg}}v\text{ and
}u\leq_{\operatorname{Dlex}}v.\end{array}\right.$

######  Lemma 1.12.

The order $\leq_{\mathrm{dl}}$ is a well order on ${\mathfrak{S}}(X)$.

###### Proof.

Since $\leq_{\mathrm{dl}}$ is a linear order, we only need to verify that
$\leq_{\mathrm{dl}}$ satisfies the descending chain condition. Let
$v_{1}\geq_{\mathrm{dl}}v_{2}\geq_{\mathrm{dl}}v_{3}\geq_{\mathrm{dl}}\cdots\in{\mathfrak{S}}(X)$.
Since the pre-linear order $\leq_{\mathrm{dgp}}$, $\leq_{\mathrm{dgx}}$ and
$\leq_{\mathrm{dgg}}$ satisfy the descending chain condition, there exist
$N\geq 1$ and $k\geq 0$ such that

$\deg_{P}(v_{N})=\deg_{P}(v_{N+1})=\deg_{P}(v_{N+2})=\cdots=k,$
$\deg_{X}(v_{N})=\deg_{X}(v_{N+1})=\deg_{X}(v_{N+2})=\cdots$

and

$\deg_{G}(v_{N})=\deg_{G}(v_{N+1})=\deg_{G}(v_{N+2})=\cdots.$

Thus all $v_{i}$ with $i\geq N$ belong to ${\mathfrak{S}}_{k}(X)$. The
restriction of the order $\leq_{\mathrm{Dlex}}$ to ${\mathfrak{S}}_{k}(X)$
equals to the well order $\leq_{\operatorname{Dlex}_{k}}$, which by defintion
satisfies the descending chain condition, so the chain
$v_{1}\geq_{\mathrm{dl}}v_{2}\geq_{\mathrm{dl}}v_{3}\geq_{\mathrm{dl}}\cdots$
stabilizes after finite steps. ∎

######  Definition 1.13 ([38, Definition 5.6]).

A preorder $\leq_{\alpha}$ on ${\mathfrak{M}}(X)$ (resp. ${\mathfrak{S}}(X)$)
is called bracket compatible (resp. left compatible, right compatible) if

$u\leq_{\alpha}v\Rightarrow\lfloor u\rfloor\leq_{\alpha}\lfloor
v\rfloor,\text{ (resp. }wu\leq_{\alpha}wv,\text{ resp. }uw\leq_{\alpha}vw),\
\text{ for all }w\in{\mathfrak{M}}(X)\ (resp.\ {\mathfrak{S}}(X))$

######  Lemma 1.14 ([38, Lemma 5.7]).

A well order $\leq$ is a monomial order on ${\mathfrak{M}}(X)$ (resp.
${\mathfrak{S}}(X)$) if and only if $\leq$ is bracket compatible, left
compatible and right compatible.

######  Theorem 1.15.

The well order $\leq_{\mathrm{dl}}$ is a monomial order on
${\mathfrak{S}}(X)$.

###### Proof.

Let $u\leq_{{\mathrm{dl}}}v$. It is obvious that preorders
$\leq_{\mathrm{dgp}}$ and $\leq_{\mathrm{dgx}}$ are bracket compatible, left
compatible and right compatible. This solves the case $u<_{{\rm dgp}}v$ and
that of $u=_{{\rm dgp}}v$ and $u<_{{\rm dgx}}v$. If $u=_{{\rm
dgp}}v,u=_{\mathrm{dgx}}v$ and $u<_{\mathrm{dgg}}v$, for
$w\in{\mathfrak{S}}(X)$, obviously $\lfloor u\rfloor<_{\mathrm{dgg}}\lfloor
v\rfloor$, $uw<_{\mathrm{dgg}}vw$ and $wu<_{\mathrm{dgg}}wv$.

Now we only need to consider the case that $u=_{\mathrm{dgp}}v$,
$u=_{\mathrm{dgx}}v$, $u=_{\mathrm{dgg}}v$ and $u\leq_{\mathrm{Dlex}}v$. Let
$\deg_{P}(u)=\deg_{P}(v)=n$. Since $u,v\in{\mathfrak{S}}_{n}(X)$, thus
$u\leq_{\operatorname{Dlex}_{n}}v$. By the fact that the restriction of
$\leq_{\operatorname{Dlex}_{n+1}}$ to $\lfloor{\mathfrak{S}}_{n}(X)\rfloor$ is
equal to $\lfloor\leq_{\operatorname{Dlex}_{n}}\rfloor$, we have $\lfloor
u\rfloor\leq_{\operatorname{Dlex}_{n+1}}\lfloor v\rfloor$ and $\lfloor
u\rfloor\leq_{{\mathrm{dl}}}\lfloor v\rfloor$. Let
$w\in{\mathfrak{S}}_{m}(X)$. One can obtain
$uw\leq_{\operatorname{Dlex}_{r}}vw$ and $wu\leq_{\operatorname{Dlex}_{r}}wv$
for $r=\max\left\\{m,n\right\\}$, so $uw\leq_{{\mathrm{dl}}}vw$ and
$wu\leq_{{\mathrm{dl}}}wv$.

We are done. ∎

######  Remark 1.16.

In fact, we can define another monomial order $\leq_{\mathrm{dl^{\prime}}}$
instead of $\leq_{\mathrm{dl}}$ on ${\mathfrak{S}}(Z)$, which keeps $\lfloor
u\rfloor v>\lfloor uv\rfloor$ for any $u,v\in{\mathfrak{S}}(Z)$. To this end,
we only need to modify the definition of G-degree in $\leq_{\mathrm{dl}}$ as
follows:

We modify the definition of G-degree in $\leq_{\mathrm{dl}}$ as follows: for
any $u\in{\mathfrak{S}}(Z)$, let $u_{1},\dots,u_{n}\in Z$ be all the elements
occuring in $u$ from left to right. If the half bracket $\lfloor$ (resp.
$\rfloor$) is between $u_{i}$ and $u_{i+1}$ ($1\leq i<n$), define the G-degree
of this half bracket to be $n-i$; if there is a half bracket $\lfloor$ (resp.
$\rfloor$) appearing on the left of $u_{1}$ (resp. on the right of $u_{n}$),
we define the G-degree of this half bracket to be $n$ (resp. $0$). Denote
$\deg_{G}(u)$ by the sum of the G-degree of all the half brackets in $u$.

Now we extend $\leq_{{\mathrm{dl}}}$ from ${\mathfrak{S}}(X)$ to
${\mathfrak{M}}(X)$.

######  Definition 1.17.

Let $X$ be a set with a well order. Let $\dagger$ be a symbol which is
understood to be $\lfloor 1\rfloor$ and write
$X^{\prime}=X\sqcup\\{\dagger\\}$. Consider the free operated semigroup
${\mathfrak{S}}(X^{\prime})$ over the set $X^{\prime}$. The well order on $X$
extends to a well order $\leq$ on $X^{\prime}$ by setting $z>\dagger$, for any
$z\in X$. Then the monomial order $\leq_{\mathrm{dl}}$ on
${\mathfrak{S}}(X^{\prime})$ induces a well order $\leq_{\mathrm{udl}}$ on
${\mathfrak{M}}(X)={\mathfrak{S}}(X^{\prime})\sqcup\\{1\\}$ (in which $\lfloor
1\rfloor$ is identified with $\dagger$), by setting $u>1$ for any
$u\in{\mathfrak{S}}(X^{\prime})$.

######  Remark 1.18.

Notice that by writing $\dagger$ instead of $\lfloor 1\rfloor$, we avoid
counting the brackets of $\lfloor 1\rfloor$ when computing $P$-degrees and
$G$-degrees.

######  Theorem 1.19.

The well order $\leq_{\mathrm{udl}}$ is a monomial order on
${\mathfrak{M}}(X)$ and $\leq_{\mathrm{udl}}$ restricts on ${\mathfrak{S}}(X)$
is the momomial order $\leq_{\mathrm{dl}}$.

###### Proof.

For any $x\in{\mathfrak{M}}(X)\backslash\\{1\\}$, $x>_{\mathrm{udl}}1$. We
have $\lfloor x\rfloor>_{\mathrm{udl}}x\geq_{\mathrm{udl}}\dagger$. Thus
$\leq_{\mathrm{udl}}$ is bracket compatible. Clearly, $\leq_{\mathrm{udl}}$ is
left and right compatible. ∎

We record an important technical result.

######  Proposition 1.20.

For any $u,v\in{\mathfrak{M}}(X)\backslash\\{1\\}$, we have

  * (a)

$\lfloor u\rfloor v<_{\mathrm{udl}}\lfloor uv\rfloor<_{\mathrm{udl}}u\lfloor
v\rfloor<_{\mathrm{udl}}\lfloor u\rfloor\lfloor v\rfloor;$

  * (b)

$u\lfloor 1\rfloor v<_{\mathrm{udl}}\lfloor u\rfloor v;$

  * (c)

$\lfloor 1\rfloor uv<_{\mathrm{udl}}\lfloor u\rfloor v;$

  * (d)

$u<_{\mathrm{udl}}\lfloor 1\rfloor u;$

  * (e)

$u<_{\mathrm{udl}}u\lfloor 1\rfloor.$

###### Proof.

Let $u,v\in{\mathfrak{M}}(X)\backslash\\{1\\}={\mathfrak{S}}(X^{\prime})$.

  * (a)

$\lfloor u\rfloor v<_{\mathrm{udl}}\lfloor uv\rfloor$ holds because

$\deg_{G}(\lfloor uv\rfloor)-\deg_{G}(\lfloor u\rfloor
v)=\deg_{X^{\prime}}(v)>0,$

$u\lfloor v\rfloor<_{\mathrm{udl}}\lfloor u\rfloor\lfloor v\rfloor$ follows
from $u\lfloor v\rfloor<_{\mathrm{dgp}}\lfloor u\rfloor\lfloor v\rfloor$ and
$\lfloor uv\rfloor<_{\mathrm{udl}}u\lfloor v\rfloor$ is obtained from
$\deg_{G}(u\lfloor v\rfloor)-\deg_{G}(\lfloor
uv\rfloor)=\deg_{X^{\prime}}(u)>0$.

  * (b)

The inequality is valid as $u\lfloor 1\rfloor v=u\dagger
v<_{\mathrm{dgp}}u\lfloor v\rfloor$.

  * (c)

The statement can be deduced from $\lfloor 1\rfloor uv=\dagger
uv<_{\mathrm{dgp}}u\lfloor v\rfloor$.

  * (d)

The assertion follows from $\deg_{X^{\prime}}(u)<\deg_{X^{\prime}}(\dagger
u)=\deg_{X^{\prime}}(\lfloor 1\rfloor u)$.

  * (e)

We infer the result from
$\deg_{X^{\prime}}(u)<\deg_{X^{\prime}}(u\dagger)=\deg_{X^{\prime}}(u\lfloor
1\rfloor)$.

∎

Next, we recall an another monomial order $\leq_{{\rm db}}$ on
${\mathfrak{M}}(X)$ constructed by Gao, Guo, Sit and Zheng [38].

  * (a)

Let $u,v\in{\mathfrak{M}}_{0}(X)$, define

$u\leq_{{\rm db}_{0}}v\Leftrightarrow u\leq_{\mathrm{dlex}}v.$

  * (b)

Suppose that for each $1\leq i\leq n$, we are given a well order $\leq_{{\rm
db}_{i}}$ on ${\mathfrak{M}}_{i}(X)$ such that $\leq_{{\rm db}_{i}}$ extends
$\leq_{{\rm db}_{i-1}}$. For $r\geq 0$, denote
${\mathfrak{M}}_{n+1,r}(X)=\left\\{u\in{\mathfrak{M}}_{n+1}(X)~{}|~{}|u|_{P}=r\right\\}$.
Let $u,v\in{\mathfrak{M}}_{n+1,r}(X)$, so they can be written as

$u=u_{0}\lfloor u_{1}^{*}\rfloor u_{1}\lfloor u_{2}^{*}\rfloor\cdots\lfloor
u_{r}^{*}\rfloor u_{r},v=v_{0}\lfloor v_{1}^{*}\rfloor v_{1}\lfloor
v_{2}^{*}\rfloor\cdots\lfloor v_{r}^{*}\rfloor v_{r},$

where $u_{0},u_{1},\dots,u_{r},$ $v_{0},v_{1},\dots,v_{r}\in{\mathcal{M}}(X)$
and
$u_{1}^{*},u_{2}^{*},\dots,u_{r}^{*},v_{1}^{*},v_{2}^{*},\dots,v_{r}^{*}\in{\mathfrak{M}}_{n}(X).$
Then impose

$u\leq_{\mathrm{lex}_{n+1}}v\Leftrightarrow(u_{1}^{*},u_{2}^{*},\dots,u_{r}^{*},u_{0},u_{1},\dots,u_{r})\leq_{\mathrm{clex}}(v_{1}^{*},v_{2}^{*},\dots,v_{r}^{*},v_{0},v_{1},\dots,v_{r}),$

where $\leq_{\mathrm{clex}}$ is the lexicographical order on
${\mathfrak{M}}_{n}(X)^{r}\times{\mathcal{M}}(X)^{r+1}$ induced by $\leq_{{\rm
db}_{n}}$. Now the well order $\leq_{\mathrm{db}_{n+1}}$ on
${\mathfrak{M}}_{n+1}(X)$ is given by

$u\leq_{\mathrm{db}_{n+1}}v\Leftrightarrow
u\leq_{\mathrm{dgp,brp},\mathrm{lex}_{n+1}}v\Leftrightarrow\left\\{\begin{array}[]{lcl}u<_{\mathrm{dgp}}v,\text{or
}\\\ u=_{\mathrm{dgp}}v\text{ and }u<_{\mathrm{brp}}v,\text{or }\\\
u=_{\mathrm{dgp}}v,u=_{\mathrm{brp}}v\text{ and
}u<_{\mathrm{lex}_{n+1}}v.\end{array}\right.$

By a limit process, one can get a monomial order $\leq_{{\rm db}}$ on
${\mathfrak{M}}(X)$; for details, see [38, Theorem 5.8].

##  2\. Operator polynomial identities and operated GS bases

In this section, we recall basic facts about free operated algebras whose
operator satisfies some polynomial identities and the GS basis theory in this
setup. We will also recall differential type algebras which are the main
objects in this paper.

###  2.1. Free operated algebras and operator polynomial identities

In this subsection, we recall some basic notions and facts related to free
operated algebras and operator polynomial identities.

Let $X$ be a set.

######  Definition 2.1 ([16, 38, 11]).

We call an element $\phi(x_{1},\dots,x_{n})\in{\mathbf{k}}{\mathfrak{S}}(X)$
(resp. ${\mathbf{k}}{\mathfrak{M}}(X)$) with $n\geq 1,x_{1},\dots,x_{n}\in X$
an operated polynomial identity (aka OPI).

From now on, we always assume that OPIs are multilinear, that is, they are
linear in each $x_{i}$.

######  Definition 2.2 ([16, 38, 11]).

Let $\phi(x_{1},\dots,x_{n})$ be an OPI. A (unital) operated algebra $(A,P)$
is said to satisfy the OPI $\phi(x_{1},\dots,x_{n})$ if
$\phi(r_{1},\dots,r_{n})=0,$ for all $r_{1},\dots,r_{n}\in A.$ In this case,
$(A,P)$ is called a (unital) $\phi$-algebra and $P$ is called a
$\phi$-operator.

Generally, for a family of OPIs $\Phi$, we call a (unital) operated algebra
$(A,P)$ a (unital) $\Phi$-algebra if it is a (unital) $\phi$-algebra for any
$\phi\in\Phi$. Denote the category of $\Phi$-algebras (resp. unital
$\Phi$-algebras) by $\Phi\text{-}\mathfrak{Alg}$ (resp.
$\Phi\text{-}\mathfrak{uAlg}$).

######  Definition 2.3 ([16, 38, 11]).

An operated ideal of an operated algebra is an ideal of the associative
algebra closed under the action of the operator. The operated ideal generated
by a subset $S$ is denoted by $\left\langle S\right\rangle_{\mathfrak{OpAlg}}$
(resp. $\left\langle S\right\rangle_{\mathfrak{uOpAlg}}$).

Obviously the quotient of an operated algebra (resp. unital operated algebra)
by an operated ideal is naturally an operated algebra (resp. unital operated
algebra).

From now on, $\Phi$ denotes a family of OPIs in
${\mathbf{k}}{\mathfrak{S}}(X)$ or ${\mathbf{k}}{\mathfrak{M}}(X)$. For a set
$Z$ and a subset $Y$ of ${\mathfrak{M}}(Z)$, introduce the subset
$S_{\Phi}(Y)\subseteq{\mathbf{k}}{\mathfrak{M}}(Z)$ to be

$S_{\Phi}(Y):=\\{\phi(u_{1},\dots,u_{k})\ |\ u_{1},\dots,u_{k}\in
Y,~{}\phi(x_{1},\dots,x_{k})\in\Phi\\}.$

We will consider free (unital) $\Phi$-algebra over an associative algebra
which is defined via the usual universal property; see for example [25,
Proposition 4.7]. The following result gives a construction of free (unital)
$\Phi$-algebra over an associative algebra.

######  Proposition 2.4 ([25, Proposition 4.8]).

  * (a)

Let $\Phi\subset{\mathbf{k}}{\mathfrak{S}}(X)$ and
$A={\mathbf{k}}{\mathcal{S}}(Z)/I_{A}$ an algebra. Then

${\mathcal{F}}_{\mathfrak{Alg}}^{\Phi\text{-}\mathfrak{Alg}}(A):={\mathbf{k}}{\mathfrak{S}}(Z)/\left\langle
S_{\Phi}({\mathfrak{S}}(Z))\cup I_{A}\right\rangle_{\mathfrak{OpAlg}}$

is the free $\Phi$-algebra generated by $A$.

  * (b)

Let $\Phi\subset{\mathbf{k}}{\mathfrak{M}}(X)$ and
$A={\mathbf{k}}{\mathcal{M}}(Z)/I_{A}$ a unital algebra. Then

${\mathcal{F}}_{\mathfrak{uAlg}}^{\Phi\text{-}\mathfrak{uAlg}}(A):={\mathbf{k}}{\mathfrak{M}}(Z)/\left\langle
S_{\Phi}({\mathfrak{M}}(Z))\cup I_{A}\right\rangle_{\mathfrak{uOpAlg}}$

is the free unital $\Phi$-algebra over $A$.

We introduce a notion of equivalences between families of OPIs.

######  Definition 2.5.

We say two families of OPIs
$\Phi_{1},\Phi_{2}\subset{\mathbf{k}}{\mathfrak{S}}(X)$ are equivalent in
${\mathbf{k}}{\mathfrak{S}}(X)$ if

$\left\langle
S_{\Phi_{1}}({\mathfrak{S}}(Z))\right\rangle_{\mathfrak{OpAlg}}=\left\langle
S_{\Phi_{2}}({\mathfrak{S}}(Z))\right\rangle_{\mathfrak{OpAlg}}$

for any set $Z$; we say two families of OPIs
$\Phi_{1},\Phi_{2}\subset{\mathbf{k}}{\mathfrak{M}}(X)$ are equivalent in
${\mathbf{k}}{\mathfrak{M}}(X)$ if

$\left\langle
S_{\Phi_{1}}({\mathfrak{M}}(Z))\right\rangle_{\mathfrak{uOpAlg}}=\left\langle
S_{\Phi_{2}}({\mathfrak{M}}(Z))\right\rangle_{\mathfrak{uOpAlg}}$

for any set $Z$.

###  2.2. Operated GS bases for free $\Phi$-algebras

######  Definition 2.6 ([3, 16, 38, 11]).

Let $Z$ be a set, $\leq$ a linear order on ${\mathfrak{M}}(Z)$ and
$f\in{\mathbf{k}}{\mathfrak{M}}(Z)$.

  * (a)

Let $f\notin{\mathbf{k}}$. The leading monomial of $f$ , denoted by $\bar{f}$,
is the largest monomial appearing in $f$. The leading coefficient of $f$ ,
denoted by $c_{f}$, is the coefficient of $\bar{f}$ in $f$. We call $f$ monic
with respect to $\leq$ if $c_{f}=1$.

  * (b)

Let $f\in{\mathbf{k}}$ (including the case $f=0$). We define the leading
monomial of $f$ to be $1$ and the leading coefficient of $f$ to be $c_{f}=f$.

  * (c)

A subset $S\subseteq{\mathbf{k}}{\mathfrak{M}}(Z)$ is called monicized with
respect to $\leq$, if each nonzero element of $S$ has leading coefficient $1$.
Obviously, each subset $S\subseteq{\mathfrak{M}}(Z)$ can be made monicized if
we divide each nonzero element by its leading coefficient.

We need another notation. Let $Z$ be a set. For $u\in{\mathfrak{M}}(Z)$ with
$u\neq 1$, as $u$ can be uniquely written as a product $u_{1}\cdots u_{n}$
with $u_{i}\in Z\cup\left\lfloor{\mathfrak{M}}(Z)\right\rfloor$ for $1\leq
i\leq n$, call $n$ the breadth of $u$, denoted by $|u|$; for $u=1$, we define
$|u|=0$.

######  Definition 2.7 ([3, 16, 38, 11]).

Let $\leq$ be a monomial order on ${\mathfrak{S}}(Z)$ (resp.
${\mathfrak{M}}(Z)$) and $f,g\in{\mathbf{k}}{\mathfrak{S}}(Z)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(Z)$) be monic.

  * (a)

If there are $w,u,v\in{\mathfrak{S}}(Z)$ (resp. ${\mathfrak{M}}(Z)$) such that
$w=\bar{f}u=v\bar{g}$ with
max$\left\\{|\bar{f}|,|\bar{g}|\right\\}<\left|w\right|<|\bar{f}|+|\bar{g}|$,
we call

$\left(f,g\right)^{u,v}_{w}:=fu-vg$

the intersection composition of $f$ and $g$ with respect to $w$.

  * (b)

If there are $w\in{\mathfrak{S}}(Z)$ (resp. ${\mathfrak{M}}(Z)$) and
$q\in{\mathfrak{S}}^{\star}(Z)$ (resp. ${\mathfrak{M}}^{\star}(Z)$) such that
$w=\bar{f}=q|_{\bar{g}}$, we call

$\left(f,g\right)^{q}_{w}:=f-q|_{g}$

the inclusion composition of $f$ and $g$ with respect to $w$.

######  Definition 2.8 ([3, 16, 38, 11]).

Let $Z$ be a set and $\leq$ a monomial order on ${\mathfrak{S}}(Z)$ (resp.
${\mathfrak{M}}(Z)$). Let
${\mathcal{G}}\subseteq{\mathbf{k}}{\mathfrak{S}}(Z)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(Z)$).

  * (a)

An element $f\in{\mathbf{k}}{\mathfrak{S}}(Z)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(Z)$) is called trivial modulo $({\mathcal{G}},w)$
for $w\in{\mathfrak{S}}(Z)$ (${\mathfrak{M}}(Z)$) if

$f=\underset{i}{\sum}c_{i}q_{i}|_{s_{i}}\text{ with
}q_{i}|_{\bar{s}_{i}}<w\text{, where }c_{i}\in{\mathbf{k}},\
q_{i}\in{\mathfrak{S}}^{\star}(Z)~{}(\text{resp.}~{}{\mathfrak{M}}^{\star}(Z))\
\mathrm{and}\ s_{i}\in{\mathcal{G}}.$

  * (b)

The subset ${\mathcal{G}}$ is called a GS basis in
${\mathbf{k}}{\mathfrak{S}}(Z)$ (resp. ${\mathbf{k}}{\mathfrak{M}}(Z)$) with
respect to $\leq$ if, for all pairs $f,g\in{\mathcal{G}}$ monicized with
respect to $\leq$, every intersection composition of the form
$\left(f,g\right)^{u,v}_{w}$ is trivial modulo $({\mathcal{G}},w)$, and every
inclusion composition of the form $\left(f,g\right)^{q}_{w}$ is trivial modulo
$({\mathcal{G}},w)$.

To distinguish from usual GS bases for associative algebras, from now on, we
shall rename GS bases in operated contexts by operated GS bases.

######  Proposition 2.9.

Let $Z$ be a set and $\leq$ a monomial order on ${\mathfrak{M}}(X)$. Then its
restriction to ${\mathfrak{S}}(X)$ is also a monomial order. Moreover,
${\mathcal{G}}\subseteq{\mathbf{k}}{\mathfrak{S}}(Z)$ is an operated GS basis
in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to the restriction of $\leq$
is equivalent to that ${\mathcal{G}}$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq$.

######  Theorem 2.10 ([3, 16, 38, 11]).

(Composition-Diamond Lemma) Let $Z$ be a set, $\leq$ a monomial order on
${\mathfrak{M}}(Z)$ and ${\mathcal{G}}\subseteq{\mathbf{k}}{\mathfrak{M}}(Z)$.
Then the following conditions are equivalent:

  * (a)

${\mathcal{G}}$ is an operated GS basis in ${\mathbf{k}}{\mathfrak{M}}(Z)$.

  * (b)

Denote

${\rm
Irr}({\mathcal{G}}):={\mathfrak{M}}(Z)\backslash\left\\{q|_{\overline{s}}~{}|~{}s\in{\mathcal{G}},\
\ q\in{\mathfrak{M}}^{\star}(Z)\right\\}.$

As a ${\mathbf{k}}$-space, ${\mathbf{k}}{\mathfrak{M}}(Z)={\mathbf{k}}{\rm
Irr}({\mathcal{G}})\oplus\left\langle{\mathcal{G}}\right\rangle_{\mathfrak{uOpAlg}}$
and ${\rm Irr}({\mathcal{G}})$ is a ${\mathbf{k}}$-basis of
${\mathbf{k}}{\mathfrak{M}}(Z)/\left\langle{\mathcal{G}}\right\rangle_{\mathfrak{uOpAlg}}$.

######  Theorem 2.11 ([3, 16, 38, 11]).

(Composition-Diamond Lemma) Let $Z$ be a set, $\leq$ a monomial order on
${\mathfrak{S}}(Z)$ and ${\mathcal{G}}\subseteq{\mathbf{k}}{\mathfrak{S}}(Z)$.
Then the following conditions are equivalent:

  * (a)

${\mathcal{G}}$ is an operated GS basis in ${\mathbf{k}}{\mathfrak{S}}(Z)$.

  * (b)

Denote

${\rm
Irr}({\mathcal{G}}):={\mathfrak{S}}(Z)\backslash\left\\{q|_{\overline{s}}~{}|~{}s\in{\mathcal{G}},\
\ q\in{\mathfrak{S}}^{\star}(Z)\right\\}.$

As a ${\mathbf{k}}$-space, ${\mathbf{k}}{\mathfrak{S}}(Z)={\mathbf{k}}{\rm
Irr}({\mathcal{G}})\oplus\left\langle{\mathcal{G}}\right\rangle_{\mathfrak{OpAlg}}$
and ${\rm Irr}({\mathcal{G}})$ is a ${\mathbf{k}}$-basis of
${\mathbf{k}}{\mathfrak{S}}(Z)/\left\langle{\mathcal{G}}\right\rangle_{\mathfrak{OpAlg}}$.

The following result refines slightly [25, Proposition 6.7].

######  Proposition 2.12.

Let $Z$ be a set and $\leq$ a monomial order on ${\mathfrak{S}}(Z)$ (resp.
${\mathfrak{M}}(Z)$). Clearly when restricted to ${\mathcal{S}}(Z)$ (resp.
${\mathcal{M}}(Z)$), it is still a monomial order. Then a GS basis
$G\subseteq{\mathbf{k}}{\mathcal{S}}(Z)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(Z)$) with respect to the restriction of $\leq$ is
also an operated GS basis in ${\mathbf{k}}{\mathfrak{S}}(Z)$ (resp.
${\mathbf{k}}{\mathfrak{M}}(Z)$) with respect to $\leq$.

######  Definition 2.13 ([11]).

  * (a)

Let $\Phi\subseteq{\mathbf{k}}{\mathfrak{S}}(X)$ be a family of OPIs. Let $Z$
be a set and $\leq$ a monomial order on ${\mathfrak{S}}(Z)$. We call $\Phi$ GS
on ${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq$ if
$S_{\Phi}({\mathfrak{S}}(Z))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq$.

  * (b)

Let $\Phi\subseteq{\mathbf{k}}{\mathfrak{M}}(X)$ be a family of OPIs. Let $Z$
be a set and $\leq$ a monomial order on ${\mathfrak{M}}(Z)$. We call $\Phi$ GS
on ${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq$ if
$S_{\Phi}({\mathfrak{M}}(Z))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq$.

For a given unital algebra $A$ and a GS family of OPIs $\Phi$ under some
monomial order, one can give an operated GS basis of the free unital
$\Phi\text{-}$algebra over $A$ by [25, Theorem 5.9].

######  Theorem 2.14 ([25, Theorem 5.9]).

Let $X$ be a set and $\Phi\subseteq{\mathbf{k}}{\mathfrak{M}}(X)$ a system of
OPIs. Let $A={\mathbf{k}}{\mathcal{M}}(Z)/I_{A}$ be a unital algebra with
generating set $Z$. Assume that $\Phi$ is operated GS on $Z$ with respect to a
monomial order $\leq$ in ${\mathfrak{M}}(Z)$ and that $G$ is a GS basis of
$I_{A}$ in ${\mathbf{k}}{\mathcal{M}}(Z)$ with respect to the restriction of
$\leq$ to ${\mathcal{M}}(Z)$.

Suppose that the leading monomial of any OPI $\phi(x_{1},\dots,x_{n})\in\Phi$
has no subword in ${\mathcal{M}}(X)\backslash X$, and that for all
$u_{1},\dots,u_{n}\in{\mathfrak{M}}(Z)$, $\phi(u_{1},\dots,u_{n})$ vanishes or
its leading monomial is still $\overline{\phi}(u_{1},\dots,u_{n})$. Then
$S_{\Phi}({\mathfrak{M}}(Z))\cup G$ is an operated GS basis of $\left\langle
S_{\Phi}({\mathfrak{M}}(Z))\cup I_{A}\right\rangle_{\mathfrak{uOpAlg}}$ in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq$.

We also have a nonunital version of this result, whose proof is similar to
that of Theorem 2.14, so we omit it.

######  Theorem 2.15.

Let $X$ be a set and $\Phi\subseteq{\mathbf{k}}{\mathfrak{S}}(X)$ a system of
OPIs. Let $A={\mathbf{k}}{\mathcal{S}}(Z)/I_{A}$ be an algebra with generating
set $Z$. Assume that $\Phi$ is operated GS on $Z$ with respect to a monomial
order $\leq$ in ${\mathfrak{S}}(Z)$ and that $G$ is a GS basis of $I_{A}$ in
${\mathbf{k}}{\mathcal{S}}(Z)$ with respect to the restriction of $\leq$ to
${\mathcal{S}}(Z)$.

Suppose that the leading monomial of any OPI $\phi(x_{1},\dots,x_{n})\in\Phi$
has no subword in ${\mathcal{S}}(X)\backslash X$, and that for all
$u_{1},\dots,u_{n}\in{\mathfrak{S}}(Z)$, $\phi(u_{1},\dots,u_{n})$ vanishes or
its leading monomial is still $\overline{\phi}(u_{1},\dots,u_{n})$. Then
$S_{\Phi}({\mathfrak{S}}(Z))\cup G$ is an operated GS basis of $\left\langle
S_{\Phi}({\mathfrak{S}}(Z))\cup I_{A}\right\rangle_{\mathfrak{OpAlg}}$ in
${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq$.

###  2.3. Remainder on rewriting systems

We need some basic notions about rewriting systems in order to introduce OPIs
of differential type. The basic references about rewriting systems are, for
instance, [1] and the recent lecture notes [21].

######  Definition 2.16.

Let $V$ be a $\bf{k}$-space with a $\bf{k}$-basis $Z$.

  * (a)

For $f=\sum_{w\in Z}c_{w}w\in V$ with $c_{w}\in\mathbf{k},$ the support
$\operatorname{Supp}(f)$ of $f$ is the set $\\{w\in Z\mid c_{w}\neq 0\\}.$ By
convention, we take $\operatorname{Supp}(0)=\emptyset$.

  * (b)

Let $f,g\in V$. We use $f\dot{+}g$ to indicate the property that
$\operatorname{Supp}(f)\cap\operatorname{Supp}(g)=\emptyset.$ If this is the
case, we say $f+g$ is a direct sum of $f$ and $g,$ and use $f\dot{+}g$ also
for the sum $f+g$.

  * (c)

For $f\in V$ and $w\in\operatorname{Supp}(f)$ with the coefficient $c_{w}$,
write $R_{w}(f):=c_{w}w-f\in V$. So $f=c_{w}w-R_{w}(f)$.

######  Definition 2.17.

Let $V$ be a $\bf{k}$-space with a $\bf{k}$-basis $Z$.

  * (a)

A term-rewriting system $\Pi$ on $V$ with respect to $Z$ is a binary relation
$\Pi\subseteq Z\times V$. An element $(t,v)\in\Pi$ is called a
(term-)rewriting rule of $\Pi,$ denoted by $t\rightarrow v$.

  * (b)

The term-rewriting system $\Pi$ is called simple with respect to $Z$ if
$t\dot{+}v$ for all $t\rightarrow v\in\Pi$

  * (c)

If $f=c_{t}t-R_{t}(f)\in V,$ using the rewriting rule $t\rightarrow v,$ we get
a new element $g:=c_{t}v-R_{t}(f)\in V,$ called a one-step rewriting of $f$
and denoted by $f\rightarrow_{\Pi}g$.

  * (d)

The reflexive-transitive closure of $\rightarrow_{\Pi}$ (as a binary relation
on $V$ ) is denoted by $\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi}$
and, if $f\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi}g,$ we say $f$
rewrites to $g$ with respect to $\Pi$.

  * (e)

Two elements $f,g\in V$ are joinable if there exists $h\in V$ such that
$f\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi}h$ and
$g\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi}h$; we denote this by
$f\downarrow_{\Pi}g$.

  * (f)

A term-rewriting system $\Pi$ on $V$ is called terminating if there is no
infinite chain of one-step rewriting

$f_{0}\rightarrow_{\Pi}f_{1}\rightarrow_{\Pi}f_{2}\cdots.$

  * (g)

A term-rewriting system $\Pi$ is called compatible with a linear order $\geq$
on $Z$, if $t>\bar{v}$ for each $t\rightarrow v\in\Pi$.

The following theorem supplies a method to show that a single OPI $\phi$ is GS
by rewriting system. For convenience, we will use the notation
$\mathfrak{u}=(u_{1},\dots,u_{k})\in{\mathfrak{M}}(Z)^{k}$ (similar for
$\mathfrak{u}\in{\mathfrak{S}}(Z)^{k}$), and $\phi(\mathfrak{u})$ for
$\phi(u_{1},\dots,u_{k})$ in the following. We say that an element
$f\in{\mathbf{k}}{\mathfrak{M}}(Z)$ is in $\phi$-normal form if no monomial of
$f$ contains any subword of the form $\overline{\phi(\mathfrak{u})}$ with
$\mathfrak{u}\in{\mathfrak{M}}(Z)^{k}$.

######  Theorem 2.18 ([11, Theorem 4.1]).

Let $\phi(x_{1},\dots,x_{k})\in\mathbf{k}\mathfrak{M}(X)$ be a multilinear OPI
such that $\phi=\overline{\phi}-R(\phi)$, where $R(\phi)$ is in $\phi$-normal
form. Suppose that, for any set $Z,$ there is a monomial order $\leq$ on
$\mathfrak{M}(Z),$ such that the following two conditions hold:

  * (a)

if $\phi(\mathfrak{u}),\phi(\mathfrak{v})\in S_{\phi}({{\mathfrak{M}}(Z)})$
are such that $\overline{\phi(\mathfrak{u})}=\alpha\beta$ and
$\overline{\phi(\mathfrak{v})}=\beta\gamma$ for some
$\alpha,\beta,\gamma\in\mathfrak{M}(Z)$ and
$\mathfrak{u},\mathfrak{v}\in\mathfrak{M}(Z)^{k},$ then
$R(\phi(\mathfrak{u}))\gamma\downarrow_{\Pi_{\phi}(Z)}\alpha
R(\phi(\mathfrak{v})),$ where the term-rewriting system

$\Pi_{\phi}(Z):=\left\\{~{}q|_{\overline{{\phi}(\mathfrak{u})}}\rightarrow
q|_{R(\phi(\mathfrak{u}))}~{}\big{|}~{}\mathfrak{u}\in{\mathfrak{M}}(Z)^{k},~{}q\in{\mathfrak{M}}^{\star}(Z)~{}\right\\}$

is compatible with $\leq$;

  * (b)

if $\overline{\phi(\mathfrak{u})}=q|_{\overline{\phi(\mathfrak{v})}}$ for some
$\star\neq q\in\mathfrak{M}^{\star}(Z)$ and
$\mathfrak{u},\mathfrak{v}\in\mathfrak{M}(Z)^{k}$, then
$\overline{\phi(\mathfrak{v})}$ is a subword of some $u_{i},1\leq i\leq k$.

Then the OPI $\phi$ is GS with respect to the order $\leq$.

######  Lemma 2.19.

Assume that $X=\\{x_{1},\dots,x_{n}\\}$. Let
$\Phi\subset{\mathbf{k}}{\mathfrak{S}}(X)$ be a system of OPIs, $Z$ a set and
$\leq$ a monomial order on ${\mathfrak{S}}(Z)$. Consider the rewriting system
defined as follows

$\Pi_{\Phi}(Z):=\left\\{~{}q|_{\overline{\phi(\mathfrak{u})}}\rightarrow
q|_{\overline{\phi(\mathfrak{u})}-\phi(\mathfrak{u})}~{}|~{}\phi\in\Phi,~{}\mathfrak{u}\in{\mathfrak{S}}(Z)^{k},~{}q\in{\mathfrak{S}}^{\star}(Z)~{}\right\\}.$

If $f,g\in{\mathbf{k}}{\mathfrak{S}}(Z)$ are joinable, then for any
$w\in{\mathfrak{S}}(Z)$ such that $w>\overline{f}$ and $w>\overline{g}$, we
have $f-g$ is trivial modulo $(S_{\Phi}({\mathfrak{S}}(Z)),w)$.

###### Proof.

By the assumption, there exists $h\in{\mathfrak{S}}(Z)$ such that
$f\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi_{\Phi}(Z)}h$ and
$g\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi_{\Phi}(Z)}h$. By the
definition of rewriting, there exist
$l_{1},\dots,l_{s},l_{1}^{\prime},\dots,l_{t}^{\prime}\in
S_{\Phi}({\mathfrak{S}}(Z))$ and
$q_{1},\dots,q_{s},q^{\prime}_{1},\dots,q^{\prime}_{t}\in{\mathfrak{S}}^{\star}(Z)$
such that $f-h=\sum_{i=1}^{s}q_{i}|_{l_{i}}$ and
$g-h=\sum_{j=1}^{t}q^{\prime}_{j}|_{l_{j}^{\prime}}$, where
$q_{i}|_{\bar{l_{i}}}\leq\overline{f},~{}1\leq i\leq s$ and
$q^{\prime}_{j}|_{\bar{l_{j}^{\prime}}}\leq\overline{g},~{}1\leq j\leq t$.
Thus,

$f-g=f-h+h-g=\sum_{i=1}^{s}q_{i}|_{l_{i}}-\sum_{j=1}^{t}q^{\prime}_{j}|_{l_{j}^{\prime}}$

is trivial modulo $(S_{\Phi}({\mathfrak{S}}(Z)),w)$. ∎

##  3\. Differential type OPIs

In this section, we recall differential OPIs due to Guo et al. [16, 11] and we
will show that differential type OPIs appearing in their classification are
equivalent to some new OPIs to which one can apply Theorem 2.15 and Theorem
2.14.

From now on $X=\\{x,y\\}$ is a set with two elements.

###  3.1. Unital differential type OPIs

######  Definition 3.1 ([16, 11]).

An OPI $\phi\in{\mathbf{k}}{\mathfrak{M}}(X)$ is said to be of unital
differential type if $\phi$ is of the form $\lfloor xy\rfloor-N(x,y)$, where
$N(x,y)$ satisfies the following conditions:

  * (a)

$N(x,y)$ is linear in $x$ and $y$;

  * (b)

no monomial of $N(x,y)$ contains any subword of the form $\lfloor uv\rfloor$
for any $u,v\in{\mathfrak{M}}(\left\\{x,y\right\\})\backslash\\{1\\}$;

  * (c)

for any set $Z$ and $u,v,w\in{\mathfrak{M}}(Z)\backslash\\{1\\}$,

$N(uv,w)-N(u,vw)\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi_{\phi}(Z)}0,$

where $\Pi_{\phi}(Z):=\left\\{q|_{\lfloor uv\rfloor}\rightarrow
q|_{N(u,v)}~{}|~{}u,v\in{\mathfrak{M}}(Z)\backslash\\{1\\},~{}q\in{\mathfrak{M}}^{\star}(Z)\right\\}$.

It is showed in [16, Theorem 5.7] that for an OPI $\phi$ of differential type,
$S_{\phi}({\mathfrak{M}}(Z))$ is an operated GS basis of $\langle
S_{\phi}({\mathfrak{M}}(Z))\rangle_{\mathfrak{uOpAlg}}$ with respect to some
monomial order, under which the leading monomial of $\phi$ is $\lfloor
xy\rfloor$.

Guo, Sit and Zheng gave a list of OPIs of differential type and they
conjectured that these are all possible OPIs of differential type [16].

######  Conjecture 3.2 ([16, Conjecture 4.7]).

The OPIs appearing in the list below are all the OPIs of differential type:

  * (${\mathcal{U}}$1)

$\lfloor xy\rfloor-a(x\lfloor y\rfloor+\lfloor x\rfloor y)-b\lfloor
x\rfloor\lfloor y\rfloor-cxy$ with $a^{2}=a+bc$,

  * (${\mathcal{U}}$2)

$\lfloor xy\rfloor-ab^{2}yx-bxy-a\lfloor y\rfloor\lfloor x\rfloor+ab(y\lfloor
x\rfloor+\lfloor y\rfloor x)$,

  * (${\mathcal{U}}$3)

$\lfloor xy\rfloor-x\lfloor y\rfloor-a(x\lfloor 1\rfloor y-\lfloor 1\rfloor
xy)$,

  * (${\mathcal{U}}$4)

$\lfloor xy\rfloor-\lfloor x\rfloor y-a(x\lfloor 1\rfloor y-xy\lfloor
1\rfloor)$,

  * (${\mathcal{U}}$5)

$\lfloor xy\rfloor-x\lfloor y\rfloor-\lfloor x\rfloor y-ax\lfloor 1\rfloor
y-bxy$,

  * (${\mathcal{U}}$6)

$\lfloor xy\rfloor-\sum_{i,j\geq 0}\lambda_{ij}\lfloor 1\rfloor^{i}xy\lfloor
1\rfloor^{j}$ with the convention that $\lfloor 1\rfloor^{0}=1$,

where $a,b,c,\lambda_{ij}\in{\mathbf{k}},~{}i,j\geq 0$.

Guo, Sit and Zheng proved this conjecture under the condition
$N(x,y)\in{\mathfrak{M}}_{2}(X)$ in [16].

In the following result, we will replace each OPI (except possibly Type
$\left({\mathcal{U}}6\right)$) defined in Conjecture 3.2 by an equivalent one
in the sense of Definition 2.5. Notice that we only consider
$\left({\mathcal{U}}6\right)$ type in the case $\lambda_{ij}=0$ unless
$i+j\leq 1$.

######  Theorem 3.3.

In the following statements, $\lambda,\mu,\nu\in{\mathbf{k}}$ are scalars:

  * (a)

The OPI (${\mathcal{U}}$1) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{U}}1^{\prime}_{a})&\lfloor x\rfloor\lfloor
y\rfloor-\lambda(x\lfloor y\rfloor+\lfloor x\rfloor y)+\mu\lfloor
xy\rfloor+\nu xy,\ \mathrm{where}\ \lambda^{2}=\lambda\mu+\nu,\\\
({\mathcal{U}}1^{\prime}_{b})&x\lfloor y\rfloor-\lfloor xy\rfloor+\lfloor
x\rfloor y-\lambda xy,\\\ ({\mathcal{U}}1^{\prime}_{c})&\lfloor
x\rfloor-\lambda x;\end{array}$

  * (b)

the OPI (${\mathcal{U}}$2) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{U}}2^{\prime}_{a})&\lfloor x\rfloor\lfloor
y\rfloor-\lambda(x\lfloor y\rfloor+\lfloor x\rfloor y)+\mu\lfloor
yx\rfloor+\lambda^{2}xy-\lambda\mu yx,\\\
({\mathcal{U}}2^{\prime}_{b})&\lfloor x\rfloor-\lambda x;\end{array}$

  * (c)

the OPIs (${\mathcal{U}}$3) and (${\mathcal{U}}$4) are equivalent to

$\begin{array}[]{ll}({\mathcal{U}}3^{\prime})=({\mathcal{U}}4^{\prime})&\lfloor
x\rfloor+\lambda x\lfloor 1\rfloor-(\lambda+1)\lfloor 1\rfloor
x;\par\end{array}$

  * (d)

the OPI (${\mathcal{U}}$5) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{U}}5^{\prime}_{a})&x\lfloor y\rfloor-\lfloor
xy\rfloor+\lfloor x\rfloor y-\lambda xy,\\\
({\mathcal{U}}5^{\prime}_{b})&x\lfloor y\rfloor-\lfloor xy\rfloor+\lfloor
x\rfloor y-x\lfloor 1\rfloor y,\\\
({\mathcal{U}}5^{\prime}_{c})&x;\end{array}$

  * (e)

the OPI (${\mathcal{U}}$6) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{U}}6^{\prime}_{a})&\lfloor x\rfloor+\lambda
x\lfloor 1\rfloor-(\lambda+1)\lfloor 1\rfloor x,\\\
({\mathcal{U}}6^{\prime}_{b})&\lfloor x\rfloor-\lambda x,\\\
({\mathcal{U}}6^{\prime}_{c})&x.\end{array}$

###### Proof.

(a) For OPI (${\mathcal{U}}$1), if $b=0$, we have $a^{2}=a$. If $a=0$, we get
(${\mathcal{U}}1^{\prime}_{c}$) with $\lambda=c$; if $a=1$, we get
(${\mathcal{U}}1^{\prime}_{b}$) still with $\lambda=c$.

Now we assume $b\neq 0$. Then (${\mathcal{U}}1$) is equivalent to

$\lfloor x\rfloor\lfloor y\rfloor+\frac{a}{b}(\lfloor x\rfloor y+x\lfloor
y\rfloor)-\frac{1}{b}\lfloor xy\rfloor+\frac{c}{b}xy,$

with $a^{2}=a+bc$. Replacing $\frac{a}{b},\frac{1}{b}$ and $\frac{c}{b}$ by
$-\lambda,-\mu$ and $\nu$ respectively, we get
(${\mathcal{U}}1^{\prime}_{a}$).

(b) For OPI (${\mathcal{U}}2$), if $a=0$, we get
(${\mathcal{U}}2^{\prime}_{b}$) by replacing $b$ with $\lambda$, which is the
same as (${\mathcal{U}}1^{\prime}_{c}$). If $a\neq 0$, then (${\mathcal{U}}2$)
is equivalent to

$\lfloor x\rfloor\lfloor y\rfloor-b(x\lfloor y\rfloor+\lfloor x\rfloor
y)-\frac{1}{a}\lfloor yx\rfloor+b^{2}xy+\frac{b}{a}yx.$

Replace $b$ and $-\frac{1}{a}$ by $\lambda$ and $\mu$ respectively, then we
get (${\mathcal{U}}2^{\prime}_{a}$).

(c) For OPI (${\mathcal{U}}4$), take $x=1$ and replace $y$ by $x$, we get the
OPI (${\mathcal{U}}4^{\prime}$):

$\lfloor x\rfloor+ax\lfloor 1\rfloor-(a+1)\lfloor 1\rfloor x.$

Conversely, given (${\mathcal{U}}4^{\prime}$), by replacing $x$ by $xy$, we
get

$\lfloor xy\rfloor+axy\lfloor 1\rfloor-(a+1)\lfloor 1\rfloor xy,$

and by multiplying (${\mathcal{U}}4^{\prime}$) by $y$ on the right, we get

$\lfloor x\rfloor y+ax\lfloor 1\rfloor y-(a+1)\lfloor 1\rfloor xy;$

the difference of the above two formulae is just the OPI (${\mathcal{U}}4$):

$\lfloor xy\rfloor-\lfloor x\rfloor y-a(x\lfloor 1\rfloor y-xy\lfloor
1\rfloor).$

So (${\mathcal{U}}$4) and (${\mathcal{U}}$4′) are equivalent.

Similarly, the OPI (${\mathcal{U}}$3) is equivalent to the OPI
(${\mathcal{U}}4^{\prime}$).

(d) For the OPI (${\mathcal{U}}$5), take $y=1$, then we get

(R1) $\displaystyle(a+1)x\lfloor 1\rfloor+bx.$

If $a=-1$ and $b\neq 0$, the OPI (R1) is reduced to $x$ which is the OPI
(${\mathcal{U}}5^{\prime}_{c}$) . It is obvious that the OPI
(${\mathcal{U}}5^{\prime}_{c}$) induces (${\mathcal{U}}5$).

If $a=-1$ and $b=0$, the original OPI becomes

$\lfloor xy\rfloor-x\lfloor y\rfloor-\lfloor x\rfloor y+x\lfloor 1\rfloor y,$

which is exactly (${\mathcal{U}}5^{\prime}_{b}$).

Now we assume $a\neq-1$, then

$({\mathcal{U}}5)+\frac{a}{a+1}\eqref{tilde5}\cdot y=\lfloor
xy\rfloor-x\lfloor y\rfloor-\lfloor x\rfloor y+\lambda xy,$

where $\lambda=-\frac{b}{a+1}$, which gives (${\mathcal{U}}5^{\prime}_{a}$).
The other direction follows from the fact that by imposing $y=1$,
(${\mathcal{U}}5^{\prime}_{a}$) becomes $x\lfloor 1\rfloor-\lambda x$, which
is exactly (R1). We have shown that for $a\neq-1$, (${\mathcal{U}}5$) is
equivalent to (${\mathcal{U}}5^{\prime}_{a}$).

(e) For the OPI $({\mathcal{U}}6)$, we only consider the case $\lambda_{ij}=0$
unless $i+j\leq 1$.

Now the OPI $({\mathcal{U}}6)$

$\lfloor xy\rfloor-\lambda_{10}\lfloor 1\rfloor xy-\lambda_{01}xy\lfloor
1\rfloor-\lambda_{00}xy$

is equivalent to

$\lfloor x\rfloor-\lambda_{10}\lfloor 1\rfloor x-\lambda_{01}x\lfloor
1\rfloor-\lambda_{00}x.$

Take $x=1$, then we get

(R2) $\displaystyle(1-\lambda_{10}-\lambda_{01})\lfloor
1\rfloor-\lambda_{00}.$

If $\lambda_{10}+\lambda_{01}\neq 1$, by taking
$\lambda=\frac{\lambda_{00}}{1-\lambda_{01}-\lambda_{10}}$, (R2) is equivalent
to $\lfloor 1\rfloor-\lambda$. Now it is easy to see $({\mathcal{U}}6)$ is
equivalent to $\lfloor x\rfloor-\lambda x$, which is the OPI
(${\mathcal{U}}6^{\prime}_{b}$).

If $\lambda_{10}+\lambda_{01}=1$ and $\lambda_{00}=0$, by taking
$\lambda_{10}=-\lambda$, we have $\lambda_{01}=\lambda+1$ and

$\lfloor x\rfloor-\lambda_{10}\lfloor 1\rfloor x-\lambda_{01}x\lfloor
1\rfloor-\lambda_{00}x=\lfloor x\rfloor+\lambda\lfloor 1\rfloor
x-(\lambda+1)x\lfloor 1\rfloor,$

which is the OPI (${\mathcal{U}}6^{\prime}_{a}$).

If $\lambda_{10}+\lambda_{01}=1$ and $\lambda_{00}\neq 0$, the OPI
$({\mathcal{U}}6)$ is equivalent to $x$ which is
(${\mathcal{U}}6^{\prime}_{c}$) . ∎

###  3.2. Nonunital differential type OPIs

We will also consider the nonunital version of differential OPIs and the
corresponding classification problem.

######  Definition 3.4.

An OPI $\phi\in{\mathbf{k}}{\mathfrak{S}}(X)$ is said to be of nonunital
differential type if $\phi$ is of the form $\lfloor xy\rfloor-N(x,y)$, where
$N(x,y)$ satisfies the following conditions:

  * (a)

$N(x,y)$ is linear in $x$ and $y$;

  * (b)

no monomial of $N(x,y)$ contains any subword of the form $\lfloor uv\rfloor$
for any $u,v\in{\mathfrak{S}}(X)$;

  * (c)

for any set $Z$ and $u,v,w\in{\mathfrak{S}}(Z)$,

$N(uv,w)-N(u,vw)\stackrel{{\scriptstyle\ast}}{{\rightarrow}}_{\Pi_{\phi}(Z)}0,$

where $\Pi_{\phi}(Z):=\left\\{q|_{\lfloor uv\rfloor}\rightarrow
q|_{N(u,v)}~{}|~{}u,v\in{\mathfrak{S}}(Z),~{}q\in{\mathfrak{S}}^{\star}(Z)\right\\}$.

Since any nonunital differential type OPI can be seen as a unital differential
type OPI, we can also propose the following conjecture:

######  Conjecture 3.5.

Each nonunital differential type OPI $\phi$ is one of the OPIs in the
following list:

  * (${\mathcal{N}}$1)

$\lfloor xy\rfloor-a(x\lfloor y\rfloor+\lfloor x\rfloor y)-b\lfloor
x\rfloor\lfloor y\rfloor-cxy$ where $a^{2}=a+bc$,

  * (${\mathcal{N}}$2)

$\lfloor xy\rfloor-ab^{2}yx-bxy-a\lfloor y\rfloor\lfloor x\rfloor+ab(y\lfloor
x\rfloor+\lfloor y\rfloor x)$,

  * (${\mathcal{N}}$3)

$\lfloor xy\rfloor-x\lfloor y\rfloor$,

  * (${\mathcal{N}}$4)

$\lfloor xy\rfloor-\lfloor x\rfloor y$,

where $a,b,c,\lambda_{ij}\in{\mathbf{k}},~{}i,j\geq 0$.

######  Remark 3.6.

Notice that the cases (${\mathcal{N}}$1) (resp. (${\mathcal{N}}$2)) are
exactly (${\mathcal{U}}$1) (resp. (${\mathcal{U}}$2)). The cases
(${\mathcal{N}}$3) (resp. (${\mathcal{N}}$4)) are obtained from
(${\mathcal{U}}$3) (resp. (${\mathcal{U}}$4)) by deleting monomials containing
$\lfloor 1\rfloor$. However, when all $\lfloor 1\rfloor$ disappear, the cases
(${\mathcal{N}}$5) and (${\mathcal{N}}$6) become special cases of
(${\mathcal{N}}$1).

We also have a nonunital version of Theorem 3.3, whose proof is similar and
omitted. Notice that there is some difference in each case, since we can not
take $x$ or $y$ to be $1$.

######  Theorem 3.7.

We have the following statements:

  * (a)

The OPI (${\mathcal{N}}$1) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{N}}1^{\prime}_{a})&\lfloor x\rfloor\lfloor
y\rfloor-\lambda(x\lfloor y\rfloor+\lfloor x\rfloor y)+\mu\lfloor
xy\rfloor+\nu xy,\ \mathrm{where}\ \lambda^{2}=\lambda\mu+\nu,\\\
({\mathcal{N}}1^{\prime}_{b})&x\lfloor y\rfloor-\lfloor xy\rfloor+\lfloor
x\rfloor y-\lambda xy,\\\ ({\mathcal{N}}1^{\prime}_{c})&\lfloor
xy\rfloor-\lambda xy;\end{array}$

  * (b)

the OPI (${\mathcal{N}}$2) is equivalent to one of

$\begin{array}[]{ll}({\mathcal{N}}2^{\prime}_{a})&\lfloor x\rfloor\lfloor
y\rfloor-\lambda(x\lfloor y\rfloor+\lfloor x\rfloor y)+\mu\lfloor
yx\rfloor+\lambda^{2}xy-\lambda\mu yx,\\\
({\mathcal{N}}2^{\prime}_{b})&\lfloor xy\rfloor-\lambda xy;\end{array}$

  * (c)

the OPI (${\mathcal{N}}$3) is equivalent to

$\begin{array}[]{ll}({\mathcal{N}}3^{\prime})&x\lfloor y\rfloor-\lfloor
xy\rfloor;\end{array}$

  * (d)

the OPI (${\mathcal{N}}$4) is equivalent to

$\begin{array}[]{ll}({\mathcal{N}}4^{\prime})&\lfloor x\rfloor y-\lfloor
xy\rfloor.\end{array}$

##  4\. Operated GS bases of free nounital differential type algebras

In this section, we apply Theorem 2.15 to OPIs displayed in Theorem 3.7, under
the monomial order $\leq_{{\mathrm{dl}}}$, $\leq_{{\mathrm{dl}}^{\prime}}$ or
$\leq_{{\rm db}}$, we obtain an operated GS basis as well as a linear basis
for the free nonunital differential type algebra over a nonunital
$\bf{k}$-algebra. However, this method can not be applied to OPIs of type
$({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$ in Theorem 3.7,
so we deal with this case directly; see Theorem 4.12 and Corollary 4.13.

###  4.1. Nonunital GS OPIs of differential type

We first deal with the types $({\mathcal{N}}1^{\prime}_{b})$ and
$({\mathcal{N}}3^{\prime})$. Our result reads as follows:

######  Proposition 4.1.

Let $\phi\in{\mathbf{k}}{\mathfrak{S}}(X)$ be a nonunital differential OPI of
type $({\mathcal{N}}1^{\prime}_{b})$ or $({\mathcal{N}}3^{\prime})$ in Theorem
3.7. Let $Z$ be a set. Then $S_{\phi}({\mathfrak{S}}(Z))$ is an operated GS
basis in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq_{\mathrm{dl}}$.

We deduce this result from Proposition 4.2 and Lemma 4.3.

For an OPI $\phi$ of type $({\mathcal{N}}1^{\prime}_{b})$ or
$({\mathcal{N}}3^{\prime})$ appearing in Theorem 3.7, we may write

$\phi(x,y)=x\lfloor y\rfloor-R(x,y).$

By Theorem 1.19 and Proposition 1.20, for each set $Z$ and for all
$u,v\in{\mathfrak{S}}(Z)$, $\phi(u,v)$ vanishes or its leading monomial is
$u\lfloor v\rfloor$ with respect to the monomial order $\leq_{\mathrm{dl}}$ on
${\mathfrak{S}}(Z)$.

######  Proposition 4.2.

Let $\phi=x\lfloor y\rfloor-R(x,y)\in{\mathbf{k}}{\mathfrak{S}}(X)$ be an OPI.
Let $Z$ be a set such that ${\mathfrak{S}}(Z)$ is endowed with a monomial
order. Assume that for all $u,v\in{\mathfrak{S}}(Z)$, $\phi(u,v)$ vanishes or
its leading monomial is $u\lfloor v\rfloor$. Denote the rewriting system

$\Pi_{\phi}(Z):=\\{q|_{u\lfloor v\rfloor}\rightarrow
q|_{R(u,v)}~{}|~{}u,v\in{\mathfrak{S}}(Z),~{}q\in{\mathfrak{S}}^{\star}(Z)\\}.$

If $R(uv,w)\downarrow_{\Pi_{\phi}(Z)}uR(v,w)$, for any
$u,v,w\in{\mathfrak{S}}(Z)$, then $S_{\phi}({\mathfrak{S}}(Z))$ is an operated
GS basis in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to the monomial
order.

###### Proof.

We prove the statement by checking all inclusion compositions and intersection
compositions are trivial modulo $(S_{\phi}({\mathfrak{S}}(Z)),w)$.

We firstly consider inclusion compositions. Let $f=\phi(u,v),g\in
S_{\phi}({\mathfrak{S}}(Z))$ for $u,v\in{\mathfrak{S}}(Z)$, such that
$w=\bar{f}=q|_{\bar{g}}$ for some $w\in{\mathfrak{S}}(Z)$ and
$q\in{\mathfrak{S}}^{\star}(Z)$. We have the following three cases:

  * (a)

If $q$ has a right factor $\lfloor v^{\prime}\rfloor$ with
$v^{\prime}\in{\mathfrak{S}}(Z)$. Since $\bar{f}=u\lfloor v\rfloor$, we have
$v=v^{\prime}$ and thus there exists $q^{\prime}\in{\mathfrak{S}}^{\star}(Z)$
such that $q=q^{\prime}\lfloor v\rfloor$ and $u=q^{\prime}|_{\bar{g}}$. So we
have

$\displaystyle\left(f,g\right)^{q}_{w}$ $\displaystyle=f-q|_{g}$
$\displaystyle=\phi(u,v)-\phi(q^{\prime}|_{g},v)+\phi(q^{\prime}|_{g},v)-q|_{g}$
$\displaystyle=\phi(q^{\prime}|_{\bar{g}},v)-\phi(q^{\prime}|_{g},v)+q^{\prime}|_{g}\lfloor
v\rfloor-R(q^{\prime}|_{g},v)-q|_{g}$
$\displaystyle=\phi(q^{\prime}|_{\bar{g}-g},v)-R(q^{\prime}|_{g},v).$

By the monomial order, we have
$\overline{\phi(q^{\prime}|_{\bar{g}-g},v)}<\overline{\phi(q^{\prime}|_{\bar{g}},v)}=w$
and $\overline{R(q^{\prime}|_{g},v)}<\overline{\phi(q^{\prime}|_{g},v)}=w$.
Then since $\phi(q^{\prime}|_{\bar{g}-g},v)$ is trivial modulo
$(S_{\phi}({\mathfrak{S}}(Z)),w)$ and $g\in S_{\phi}({\mathfrak{S}}(Z))$, the
inclusion composition $\left(f,g\right)^{q}_{w}$ is trivial modulo
$(S_{\phi}({\mathfrak{S}}(Z)),w)$.

  * (b)

If $q$ has a right factor $\lfloor v^{\prime}\rfloor$ with
$v^{\prime}\in{\mathfrak{S}}^{\star}(Z)$. Since $\bar{f}=u\lfloor v\rfloor$,
we have $v=v^{\prime}|_{\bar{g}}$ and $q=u\lfloor v^{\prime}\rfloor$, thus

$\displaystyle\left(f,g\right)^{q}_{w}$ $\displaystyle=f-q|_{g}$
$\displaystyle=\phi(u,v^{\prime}|_{\bar{g}})-u\lfloor v^{\prime}|_{g}\rfloor$
$\displaystyle=\phi(u,v^{\prime}|_{\bar{g}})-\left(u\lfloor
v^{\prime}|_{g}\rfloor-R(u,v^{\prime}|_{g})\right)-R(u,v^{\prime}|_{g})$
$\displaystyle=\phi(u,v^{\prime}|_{\bar{g}})-\phi(u,v^{\prime}|_{g})-R(u,v^{\prime}|_{g})$
$\displaystyle=\phi(u,v^{\prime}|_{\bar{g}-g})-R(u,v^{\prime}|_{g}),$

which is trivial modulo $(S_{\phi}({\mathfrak{S}}(Z)),w)$.

  * (c)

If $q$ has no right factor of the form $\lfloor v^{\prime}\rfloor$, then
$\star$ is a right factor of $q$ and $\overline{g}$ has the right factor
$\lfloor v\rfloor$, i.e., $q=t\star$ and $\overline{g}=s\lfloor v\rfloor$ for
some $t,s\in{\mathfrak{S}}(Z)$. So we have $t\overline{g}=\overline{f}$ and
$g=\phi(s,v)$. By assumption, we have
$R(ts,v)\downarrow_{\Pi_{\phi}(Z)}tR(s,v)$ and by Lemma 2.19 the inclusion
composition $\left(f,g\right)^{q}_{w}$ is trivial modulo
$(S_{\phi}({\mathfrak{S}}(Z)),w)$.

Next we consider the intersection compositions. Given $f=\phi(u_{1},u_{2})$
and $g=\phi(v_{1},v_{2})$ with $u_{1},u_{2},v_{1},v_{2}\in{\mathfrak{S}}(Z)$,
assume there exist $a,b,w\in{\mathfrak{S}}(Z)$ such that
$w=\overline{f}a=b\overline{g}$, i.e., $w=u_{1}\lfloor u_{2}\rfloor
a=bv_{1}\lfloor v_{2}\rfloor$ and
max$\left\\{|\bar{f}|,|\bar{g}|\right\\}<\left|w\right|<|\bar{f}|+|\bar{g}|$.
We will write the intersection composition $\left(f,g\right)^{a,b}_{w}$ into
two inclusion compositions. Consider the polynomial $h=\phi(bv_{1},v_{2})$. We
have $w=\bar{h}=q_{1}|_{\bar{f}}=q_{2}|_{\bar{g}}$, where $q_{1}=\star a$ and
$q_{2}=b\star$. As we have shown above, the inclusion compositions
$\left(h,f\right)^{\star a}_{w}$ and $\left(h,g\right)^{b\star}_{w}$ are
trivial modulo $(S_{\phi}({\mathfrak{S}}(Z)),w)$. And since

$\left(f,g\right)^{a,b}_{w}=fa-bg=-(h-fa)+(h-bg)=-\left(h,f\right)^{\star
a}_{w}+\left(h,g\right)^{b\star}_{w},$

the intersection composition $\left(f,g\right)^{a,b}_{w}$ is trivial modulo
$(S_{\phi}({\mathfrak{S}}(Z)),w)$. ∎

We need a technical lemma which enables us to apply Proposition 4.2.

######  Lemma 4.3.

Let $\phi(x,y)=x\lfloor y\rfloor-R(x,y)$ be a nonunital differential OPI of
type $({\mathcal{N}}1^{\prime}_{b})$ or $({\mathcal{N}}3^{\prime})$ given in
Theorem 3.7. Let $Z$ be a set. Consider the rewriting system

$\Pi_{\phi}(Z):=\\{q|_{u\lfloor v\rfloor}\rightarrow
q|_{R(u,v)}~{}|~{}u,v\in{\mathfrak{S}}(Z),~{}q\in{\mathfrak{S}}^{\star}(Z)\\}.$

Then $R(uv,w)\downarrow_{\Pi_{\phi}(Z)}uR(v,w)$, for any
$u,v,w\in{\mathfrak{S}}(Z)$.

###### Proof.

For $\phi$ of type $({\mathcal{N}}1^{\prime}_{b})$, the OPI $\phi$ can be
written as $x\lfloor y\rfloor-R(x,y)$, where $R(x,y)=\lfloor xy\rfloor-\lfloor
x\rfloor y+cxy$. We have

$\displaystyle uR(v,w)$ $\displaystyle=~{}u\lfloor vw\rfloor-u\lfloor v\rfloor
w+cuvw$ $\displaystyle\rightarrow\lfloor uvw\rfloor-\lfloor u\rfloor
vw+cuvw-(\lfloor uv\rfloor-\lfloor u\rfloor v+cuv)w+cuvw$
$\displaystyle=~{}\lfloor uvw\rfloor-\lfloor uv\rfloor w+cuvw$
$\displaystyle=~{}R(uv,w).$

For the type $({\mathcal{N}}3^{\prime})$ in Theorem 3.7, $\phi(x,y)=x\lfloor
y\rfloor-\lfloor xy\rfloor$ with $R(x,y)=\lfloor xy\rfloor$. We have

$uR(v,w)=u\lfloor vw\rfloor\rightarrow\lfloor uvw\rfloor=R(uv,w).$

So in either case, $R(uv,w)\downarrow_{\Pi_{\phi}(Z)}uR(v,w)$, for any
$u,v,w\in{\mathfrak{S}}(Z)$. ∎

Proposition 4.2 and Lemma 4.3 implies immediately Proposition 4.1. This
finishes our discussion for the types $({\mathcal{N}}1^{\prime}_{b})$ and
$({\mathcal{N}}3^{\prime})$.

With a proof similar to that of Type $({\mathcal{N}}3^{\prime})$ under the
order $\leq_{\mathrm{dl^{\prime}}}$ given in Remark 1.16, one can treat the
case $({\mathcal{N}}4^{\prime})$.

######  Lemma 4.4.

For the OPI $\phi(x,y)=\lfloor x\rfloor y-\lfloor xy\rfloor$ of type
$({\mathcal{N}}4^{\prime})$ in Theorem 3.7, $S_{\phi}({\mathfrak{S}}(Z))$ is
an operated GS basis in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to the
monomial order $\leq_{\mathrm{dl^{\prime}}}$ for any set $Z$.

######  Proposition 4.5.

Consider an OPI $\phi$ of type $({\mathcal{N}}1^{\prime}_{a})$ (resp.
$({\mathcal{N}}2^{\prime}_{a})$,
$({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$). For each set
$Z$, $S_{\phi}({\mathfrak{S}}(Z))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq_{\mathrm{db}}$

###### Proof.

The case $({\mathcal{N}}1^{\prime}_{a})$ (resp.
$({\mathcal{N}}2^{\prime}_{a})$) follows from Lemma 5.1 (resp. Lemma 5.2) and
the case $({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$ can be
obtained by direct inspection. ∎

We have proved the following result:

######  Theorem 4.6.

Each OPI in Theorem 3.7 is nonunital GS with respect to either
$\leq_{\rm{dl}}$, $\leq_{\rm{dl^{\prime}}}$ or $\leq_{\rm{db}}$.

###  4.2. Operated GS bases of free nonunital differential type algebras over
algebras

By Theorem 4.6, Theorem 2.15 can be applied directly to all differential type
OPIs in Theorem 3.7 (except Type
$({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$) to obtain
operated GS bases for free nonunital differential algebras over algebras.

######  Theorem 4.7.

Let $Z$ be a set, $A={\mathbf{k}}{\mathcal{S}}(Z)/I_{A}$ an algebra with a GS
basis $G$ with respect to $\leq_{\rm{dlex}}$.

  * (a)

Let $\phi_{1}$ be an OPI of type $({\mathcal{N}}1^{\prime}_{a})$ or
$({\mathcal{N}}2^{\prime}_{a})$. Then $S_{\phi_{1}}({\mathfrak{S}}(Z))\cup G$
is an operated GS basis of $\langle S_{\phi_{1}}({\mathfrak{S}}(Z))\cup
I_{A}\rangle_{\mathfrak{OpAlg}}$ in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with
respect to $\leq_{\rm{db}}$.

  * (b)

Let $\phi_{2}$ be an OPI of type $({\mathcal{N}}1^{\prime}_{b})$ or
$({\mathcal{N}}3^{\prime})$. Then $S_{\phi_{2}}({\mathfrak{S}}(Z))\cup G$ is
an operated GS basis of $\langle S_{\phi_{2}}({\mathfrak{S}}(Z))\cup
I_{A}\rangle_{\mathfrak{OpAlg}}$ in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with
respect to $\leq_{\rm{dl}}$.

  * (c)

Let $\phi_{3}$ be an OPI of type $({\mathcal{N}}4^{\prime})$. Then
$S_{\phi_{3}}({\mathfrak{S}}(Z))\cup G$ is an operated GS basis of $\langle
S_{\phi_{3}}({\mathfrak{S}}(Z))\cup I_{A}\rangle_{\mathfrak{OpAlg}}$ in
${\mathbf{k}}{\mathfrak{S}}(Z)$ with respect to $\leq_{\rm{dl^{\prime}}}$.

Then by Theorem 2.11, we obtain linear bases for these algebras. In the
statement of the following result, write $\lfloor u\rfloor^{(1)}=\lfloor
u\rfloor$ and $\lfloor u\rfloor^{(k+1)}=\lfloor\lfloor u\rfloor^{(k)}\rfloor$
for $k\geq 1$. For a subset $G\subset{\mathcal{S}}(Z)$, we also introduce two
notations

${\rm
Irr}_{{\mathcal{S}}}(G):={\mathcal{S}}(Z)\backslash\\{u\bar{g}v~{}|~{}g\in
G,u,v\in{\mathcal{M}}(Z)\\}$

and

${\rm
Irr}_{{\mathcal{M}}}(G):={\mathcal{M}}(Z)\backslash\\{u\bar{g}v~{}|~{}g\in
G,u,v\in{\mathcal{M}}(Z)\\}.$

Note that ${\rm Irr}_{{\mathcal{M}}}(G)={\rm
Irr}_{{\mathcal{S}}}(G)\cup\\{1\\}$. In the case that $G$ is a GS basis of
${\mathcal{S}}(Z)$ (resp.${\mathcal{M}}(Z)$), ${\rm Irr}_{{\mathcal{S}}}(G)$
(resp. ${\rm Irr}_{{\mathcal{M}}}(G)$) is a linear basis of
$A={\mathbf{k}}{\mathcal{S}}(Z)/(G)$ (resp.
$A={\mathbf{k}}{\mathcal{M}}(Z)/(G)$).

######  Theorem 4.8.

With the same setup as in Theorem 4.7, we have the following statements:

  * (a)

Let $B_{0}={\rm Irr}(G)$ and for $n\geq 1$, define the set $B_{n}$ inductively
as

$B_{0}\bigcup\bigcup_{r\geq 1}\Big{\\{}u_{0}\lfloor v_{1}\rfloor
u_{1}\cdots\lfloor v_{r}\rfloor u_{r}~{}\big{|}~{}u_{0},u_{r}\in{\rm
Irr}_{{\mathcal{M}}}(G),u_{i}\in{\rm Irr}_{{\mathcal{S}}}(G),1\leq i\leq
r-1,v_{j}\in B_{n-1},1\leq j\leq r\Big{\\}}.$

Then the set $B=\bigcup_{n\geq 0}B_{n}$ is a linear basis of the free
$\phi_{1}$-algebra
${\mathcal{F}}^{\phi_{1}\text{-}\mathfrak{Alg}}_{\mathfrak{Alg}}(A)$ over $A$.

  * (b)

The union of ${\rm Irr}(G)$ with

$\bigcup_{r\geq 1}\left\\{{\lfloor\lfloor\cdots\lfloor\lfloor
u_{r}\rfloor^{(k_{r})}u_{r-1}\rfloor^{(k_{r-1})}\cdots
u_{1}\rfloor^{(k_{1})}u_{0}~{}\big{|}~{}u_{0}\in{\rm
Irr}_{{\mathcal{M}}}(G),u_{i}\in{\rm Irr}_{{\mathcal{S}}}(G),k_{i}\geq 1,1\leq
i\leq r}\right\\}$

is a linear basis of the free $\phi_{2}$-algebra
${\mathcal{F}}^{\phi_{2}\text{-}\mathfrak{Alg}}_{\mathfrak{Alg}}(A)$ over $A$.

  * (c)

The union of ${\rm Irr}(G)$ with

$\bigcup_{r\geq 1}\left\\{{u_{0}\lfloor u_{1}\cdots\lfloor u_{r-1}\lfloor
u_{r}\rfloor^{k_{r}}\rfloor^{k_{r-1}}\cdots\rfloor^{k_{1}}~{}\big{|}~{}u_{0}\in{\rm
Irr}_{{\mathcal{M}}}(G),u_{i}\in{\rm Irr}_{{\mathcal{S}}}(G),k_{i}\geq 1,1\leq
i\leq r}\right\\}$

is a linear basis of the free $\phi_{3}$-algebra
${\mathcal{F}}^{\phi_{3}\text{-}\mathfrak{Alg}}_{\mathfrak{Alg}}(A)$ over $A$.

The proof is straightforward and is left to the reader.

######  Remark 4.9.

Notice that the linear basis of a free nonunital differential type algebra
over a nonunital algebra given in Theorem 4.8 (a) has the same form as that of
free nonunital Rota-Baxter type algebras over algebras, because the
corresponding GS bases share the same set of leading monomials, consisting of
all $\lfloor u\rfloor\lfloor v\rfloor$ and $\bar{g}$ with
$u,v\in{\mathfrak{S}}(Z),g\in G$. The phenomenon also occurs for the unital
case; see Theorem 5.10 (a) and [25, Theorem 6.7].

As a special case of Rota-Baxter type, the same construction of linear bases
for the free nonunital Nijenhuis algebras over algebras appeared in [18].

Notice that one cannot apply Theorem 2.15 to $\lfloor xy\rfloor-\lambda xy$
which is of type $({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$
in Theorem 3.7, as each term has a subword $xy$. Nevertheless, we could deal
with this case directly.

We need to introduce the notions of linearly self-reduced sets and bases.

######  Definition 4.10 ([5, Definition 1.2.1.2]).

Let $V$ be a vector space with a chosen well ordered basis. Each nonzero
element of $V$, expressed as a linear combination of basis elements, has a
leading basis element which is maximal among all basis elements having nonzero
coefficients in this linear combination.

Let $S$ be a subset of $V$. A basis element is said to be linearly reduced
with respect to $S$ if it is not a leading basis element of any element of
$S$. More generally, an element $f\in V$ is said to be linearly reduced with
respect to $S$, if all basis monomials having nonzero coefficients in $f$ are
linearly reduced with respect to $S$.

A subset $S\subset V$ is said to be linearly self-reduced if each element
$s\in S$ has its leading basis element with coefficient $1$ and is linearly
reduced with respect to $S\backslash\\{s\\}$.

######  Proposition 4.11 ([5, Proposition 1.2.1.6]).

Let $V$ be a vector space with a chosen well ordered basis. Every finite
dimensional subspace $S\subset V$ has a unique linearly self-reduced basis.

Now we can consider OPIs of the type
$({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$.

######  Theorem 4.12.

Let $Z$ be a set and $A={\mathbf{k}}{\mathcal{S}}(Z)/I_{A}$ an algebra with a
finite GS basis $G$ with respect to $\leq_{\rm{dlex}}$. Let $\phi_{4}=\lfloor
xy\rfloor-\lambda xy$ be an OPI of type
$({\mathcal{N}}1^{\prime}_{c})=({\mathcal{N}}2^{\prime}_{b})$ in Theorem 3.7.
Denote by
$\pi:{\mathbf{k}}{\mathcal{S}}(Z)\twoheadrightarrow{\mathbf{k}}Z\hookrightarrow{\mathbf{k}}{\mathcal{S}}(Z)$
the canonical projection. Then $\pi(G)$ is just the set of linear parts of
elements of $G$. Let ${\mathbf{k}}\pi(G)$ be the subspace of ${\mathbf{k}}Z$
spanned by $\pi(G)$.

Let $G^{(1)}$ be the unique linearly self-reduced basis of
${\mathbf{k}}\pi(G)$ and define

${\mathcal{G}}^{\prime}=\\{\lfloor g\rfloor-\lambda g~{}\big{|}~{}g\in
G^{(1)}\\}.$

Then $S_{\phi_{4}}({\mathfrak{S}}(Z))\cup G\cup{\mathcal{G}}^{\prime}$ is an
operated GS basis of $\langle S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
I_{A}\rangle_{\mathfrak{OpAlg}}$ in ${\mathbf{k}}{\mathfrak{S}}(Z)$ with
respect to $\leq_{\rm{db}}$.

###### Proof.

We first prove that $S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime}$ is a subset of $\langle
S_{\phi_{4}}({\mathfrak{S}}(Z))\cup I_{A}\rangle_{\mathfrak{OpAlg}}$. Since
$G^{(1)}\subset{\mathbf{k}}\pi(G)$, any element in
${\mathcal{G}}^{\prime}=\\{\lfloor g\rfloor-\lambda g~{}\big{|}~{}g\in
G^{(1)}\\}$ can be written as a linear combination of the elements in the set
$\left\\{\lfloor\pi(g)\rfloor-\lambda\pi(g)~{}|~{}g\in G\right\\}$. And for
any $g\in G$,

$\lfloor\pi(g)\rfloor-\lambda\pi(g)=\left(\lfloor\pi(g)-g\rfloor-\lambda(\pi(g)-g)\right)+\lfloor
g\rfloor-\lambda g\in\langle S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
I_{A}\rangle_{\mathfrak{OpAlg}},$

since $\lfloor\pi(g)-g\rfloor-\lambda(\pi(g)-g)\in
S_{\phi_{4}}({\mathfrak{S}}(Z))$ and $\lfloor g\rfloor,g\in\langle
I_{A}\rangle_{\mathfrak{OpAlg}}$. It follows that
${\mathcal{G}}^{\prime}\subset\langle S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
I_{A}\rangle_{\mathfrak{OpAlg}}.$

Now we show $S_{\phi_{4}}({\mathfrak{S}}(Z))\cup G\cup{\mathcal{G}}^{\prime}$
is an operated GS basis. Notice that for any $u,v\in{\mathfrak{S}}(Z)$, the
leading monomial of $\phi_{4}(u,v)=\lfloor uv\rfloor-\lambda uv$ is $\lfloor
uv\rfloor$ with respect to $\leq_{\rm{db}}$. For any elements $a_{1}\in
S_{\phi_{4}}({\mathfrak{S}}(Z))$, $a_{2}\in G$ and
$a_{3}\in{\mathcal{G}}^{\prime}$, the leading monomials are of the forms
$\overline{a}_{1}=\lfloor uv\rfloor$, $\overline{a}_{2}=w$ and
$\overline{a}_{3}=\lfloor z\rfloor$, where $u,v\in{\mathfrak{S}}(Z),~{}w\in
G\subset{\mathcal{S}}(Z)$ and $z\in{\mathcal{G}}^{\prime}\subset Z$. Hence,
these three leading monomials have no overlap with each other. And since each
of the sets $S_{\phi_{4}}({\mathfrak{S}}(Z))$, $G$ and
${\mathcal{G}}^{\prime}$ is an operated GS basis, we only need to check the
triviality of any inclusion composition $\left(f,g\right)^{q}_{w}$ modulo
$(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup G\cup{\mathcal{G}}^{\prime},w)$, for the
cases $(f\in S_{\phi_{4}}({\mathfrak{S}}(Z)),~{}g\in G)$, $(f\in
S_{\phi_{4}}({\mathfrak{S}}(Z)),~{}g\in{\mathcal{G}}^{\prime})$ and
$(f\in{\mathcal{G}}^{\prime},~{}g\in G)$.

(a) For the case $w=\overline{f}=q|_{\overline{g}}$ with $f\in
S_{\phi_{4}}({\mathfrak{S}}(Z)),~{}g\in G$. There exists
$q^{\prime}\in{\mathfrak{S}}^{\star}(Z)$ such that $q=\lfloor
q^{\prime}\rfloor$ and $f=\lfloor q^{\prime}|_{\overline{g}}\rfloor-\lambda
q^{\prime}|_{\overline{g}}$.

If $g\in{\mathbf{k}}Z$, there exists a factor of $q^{\prime}$ in
${\mathcal{S}}(Z)$. Then we have

$\left(f,g\right)^{q}_{w}=f-q|_{g}=\lfloor
q^{\prime}|_{\overline{g}}\rfloor-\lambda q^{\prime}|_{\overline{g}}-\lfloor
q^{\prime}|_{g}\rfloor=(\lfloor q^{\prime}|_{\overline{g}-g}\rfloor-\lambda
q^{\prime}|_{\overline{g}-g})-\lambda q^{\prime}|_{g}.$

It is trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime},w)$ since $\lfloor
q^{\prime}|_{\overline{g}-g}\rfloor-\lambda q^{\prime}|_{\overline{g}-g}$ is
trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z)),w)$ and $g\in G$.

If $g\in G\backslash{\mathbf{k}}Z$, it can be written as
$g=g_{1}+\pi(g)\in{\mathbf{k}}({\mathcal{S}}(Z)\backslash
Z)\oplus{\mathbf{k}}Z$ and we have $\overline{g}=\overline{g}_{1}$. The
inclusion composition $\left(f,g\right)^{q}_{w}$ can be written as

$\displaystyle\left(f,g\right)^{q}_{w}$ $\displaystyle=f-q|_{g}$
$\displaystyle=\lfloor q^{\prime}|_{\overline{g}}\rfloor-\lambda
q^{\prime}|_{\overline{g}}-\lfloor q^{\prime}|_{g_{1}+\pi(g)}\rfloor$
$\displaystyle=\lfloor q^{\prime}|_{\overline{g}}\rfloor-(\lambda
q^{\prime}|_{\overline{g}}+\lambda q^{\prime}|_{g-\overline{g}})+\lambda
q^{\prime}|_{g-\overline{g}}-(\lfloor q^{\prime}|_{g_{1}}\rfloor+\lfloor
q^{\prime}|_{\pi(g)}\rfloor)$ $\displaystyle=(\lfloor
q^{\prime}|_{\overline{g}}\rfloor-\lfloor q^{\prime}|_{g_{1}}\rfloor)-(\lambda
q^{\prime}|_{\overline{g}}+\lambda q^{\prime}|_{g-\overline{g}})+\lambda
q^{\prime}|_{g-g_{1}}+\lambda q^{\prime}|_{g_{1}-\overline{g}}-\lfloor
q^{\prime}|_{\pi(g)}\rfloor$ $\displaystyle=-(\lfloor
q^{\prime}|_{g_{1}-\overline{g}}\rfloor-\lambda
q^{\prime}|_{g_{1}-\overline{g}})-\lambda q^{\prime}|_{g}-(\lfloor
q^{\prime}|_{\pi(g)}\rfloor-\lambda q^{\prime}|_{\pi(g)}).$

Since $\lfloor q^{\prime}|_{g_{1}-\bar{g}}\rfloor-\lambda
q^{\prime}|_{g_{1}-\bar{g}}$ is trivial modulo
$(S_{\phi_{4}}({\mathfrak{S}}(Z)),w)$ and $g\in G$, the first two terms are
trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime},w)$. Now we only need to consider the third term.
Since $G^{(1)}$ is the linearly self-reduced basis of ${\mathbf{k}}\pi(G)$, we
have $\pi(g)=\sum_{i=1}^{n}k_{i}g_{i}$ where $g_{i}\in G^{(1)}$. Notice that
we have $\bar{g}_{i}\leq\overline{\pi(g)}$ for $1\leq i\leq n$. Otherwise,
there exist $g_{i},g_{j}\in G^{(1)}$ such that
$\overline{g}_{i}=\overline{g}_{j}$, which contradicts to that $G^{(1)}$ is
linearly self-reduced. If $q^{\prime}$ has a factor in ${\mathcal{S}}(Z)$, we
have $\lfloor q^{\prime}|_{\pi(g)}\rfloor-\lambda q^{\prime}|_{\pi(g)}$ is
trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z)),w)$; otherwise,
$q^{\prime}=\star$ and thus $\lfloor q^{\prime}|_{\pi(g)}\rfloor-\lambda
q^{\prime}|_{\pi(g)}=\sum_{i=1}^{n}k_{i}(\lfloor g_{i}\rfloor-\lambda g_{i})$
is trivial modulo $({\mathcal{G}}^{\prime},w)$. So we have shown that the
inclusion composition $\left(f,g\right)^{q}_{w}$ is trivial modulo
$(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup G\cup{\mathcal{G}}^{\prime},w)$.

(b) For the case $w=\overline{f}=q|_{\overline{g}}$ with $f\in
S_{\phi_{4}}({\mathfrak{S}}(Z)),~{}g\in{\mathcal{G}}^{\prime}$. There exists
$q^{\prime}\in{\mathfrak{S}}^{\star}(Z)$ such that $q=\lfloor
q^{\prime}\rfloor$ and $f=\lfloor q^{\prime}|_{\overline{g}}\rfloor-\lambda
q^{\prime}|_{\overline{g}}$. Since $\overline{g}\in\lfloor Z\rfloor$, there
exists a factor of $q^{\prime}$ in ${\mathcal{S}}(Z)$. Thus we have

$\left(f,g\right)^{q}_{w}=f-q|_{g}=\lfloor
q^{\prime}|_{\overline{g}}\rfloor-\lambda q^{\prime}|_{\overline{g}}-\lfloor
q^{\prime}|_{g}\rfloor=(\lfloor q^{\prime}|_{\overline{g}-g}\rfloor-\lambda
q^{\prime}|_{\overline{g}-g})-\lambda q^{\prime}|_{g},$

which is trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime},w)$ since $\lfloor
q^{\prime}|_{\overline{g}-g}\rfloor-\lambda q^{\prime}|_{\overline{g}-g}$ is
trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z)),w)$ and
$g\in{\mathcal{G}}^{\prime}$.

(c) For the case $w=\overline{f}=q|_{\overline{g}}$ with
$f\in{\mathcal{G}}^{\prime},~{}g\in G$. Write $f=\lfloor f_{1}\rfloor-\lambda
f_{1}$, where $f_{1}\in G^{(1)}$. Since
$\overline{f}=q|_{\overline{g}}\in\lfloor Z\rfloor$, we have
$q=\lfloor\star\rfloor$, $\bar{f}_{1}=\bar{g}$ and $g=\pi(g)\in\pi(G)$. Since
$G^{(1)}$ is the linearly self-reduced basis of ${\mathbf{k}}\pi(G)$, we have
$f_{1}-g=\sum_{i=1}^{n}k_{i}g_{i}$, where $g_{i}\in G^{(1)}$ and
$\bar{g}_{i}<\bar{f}_{1}$ for $1\leq i\leq n$. So the inclusion composition

$\left(f,g\right)^{q}_{w}=\lfloor f_{1}\rfloor-\lambda f_{1}-\lfloor
g\rfloor=\left(\lfloor f_{1}-g\rfloor-\lambda(f_{1}-g)\right)-\lambda g$

is trivial modulo $(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime},w)$, since $\lfloor
f_{1}-g\rfloor-\lambda(f_{1}-g)=\sum_{i=1}^{n}k_{i}(\lfloor
g_{i}\rfloor-\lambda g_{i})$ is trivial modulo $({\mathcal{G}}^{\prime},w)$
and $g\in G$.

This finishes the proof. ∎

By Theorem 2.11, we obtain a linear basis.

######  Theorem 4.13.

Within the same setup as in Theorem 4.12, the union of ${\rm Irr}(G)$ with

$\bigcup_{r\geq 1}\left\\{{u_{0}\lfloor
v_{1}\rfloor^{(k_{1})}u_{1}\cdots\lfloor
v_{r}\rfloor^{(k_{r})}u_{r}~{}|~{}u_{i}\in{\rm Irr}(G)\cup\\{1\\},0\leq i\leq
r,v_{j}\in Z\backslash\\{\bar{g}~{}|~{}g\in G^{(1)}\\},k_{j}\geq 1,1\leq j\leq
r}\right\\}$

is a linear basis of the free $\phi_{4}$-algebra
${\mathcal{F}}^{\phi_{4}\text{-}\mathfrak{Alg}}_{\mathfrak{Alg}}(A)$ over $A$.

###### Proof.

By Theorem 4.12, the set

${\rm Irr}(S_{\phi_{4}}({\mathfrak{S}}(Z))\cup
G\cup{\mathcal{G}}^{\prime})={\mathfrak{S}}(Z)\backslash\left\\{q|_{\bar{s}},q|_{\lfloor
uv\rfloor}~{}|~{}s\in
G\cup{\mathcal{G}}^{\prime},q\in{\mathfrak{S}}^{\star}(Z),u,v\in{\mathfrak{S}}(Z)\right\\}$

is a linear basis of
${\mathcal{F}}^{\phi_{4}\text{-}\mathfrak{Alg}}_{\mathfrak{Alg}}(A)$. Besides
elements of ${\rm Irr}(G)$, for a monomial $u_{0}\lfloor v_{1}^{\prime}\rfloor
u_{1}\lfloor v_{2}^{\prime}\rfloor\cdots\lfloor v_{r}^{\prime}\rfloor u_{r}$
with $r\geq 1,u_{i}\in{\rm Irr}(G)\cup\\{1\\},0\leq i\leq
r,v_{j}^{\prime}\in{\mathcal{S}}(Z),1\leq j\leq r$, we should avoid all
subwords of the form $\lfloor xy\rfloor,x,y\in{\mathcal{S}}(Z)$ and $\lfloor
z\rfloor$ for $z\in Z$ being the leading basis element of an element of
$G^{(1)}\subset{\mathbf{k}}Z$. The result can be deduced from this
observation. ∎

##  5\. Operated GS bases of free unital differential type algebras

In this section, we will show that under some monomial order, all unital
differential type OPIs in Theorem 3.3 are GS and satisfy the conditions in
Theorem 2.14. As a consequence, we can obtain an operated GS basis and a
linear basis for each free unital differential type algebra over a unital
algebra with a given GS basis.

###  5.1. Unital GS OPIs of differential type

######  Lemma 5.1.

The OPIs of type $({\mathcal{U}}1^{\prime}_{a})$ in Theorem 3.3 are unital GS
with respect to the monomial order $\leq_{\rm{db}}$.

###### Proof.

We will prove the lemma by checking such OPIs satisfy the conditions in
Theorem 2.18. According to the monomial order $\leq_{\rm{db}}$, the leading
monomial of such an OPI is $\lfloor x\rfloor\lfloor y\rfloor$. Consider the
rewriting system defined by

$\Pi_{\phi}(Z):=\left\\{~{}\lfloor u\rfloor\lfloor
v\rfloor\rightarrow\lambda\lfloor u\rfloor v+\lambda u\lfloor
v\rfloor-\mu\lfloor uv\rfloor-\nu
uv~{}|~{}u,v\in{\mathfrak{M}}(Z)~{}\right\\}.$

For the first condition in Theorem 2.18, assume there are
$u,v,v^{\prime},w,\alpha,\beta,\gamma\in\mathfrak{M}(Z)$, such that $\lfloor
u\rfloor\lfloor v\rfloor=\alpha\beta$ and $\lfloor v^{\prime}\rfloor\lfloor
w\rfloor=\beta\gamma$. Then we only need to consider the case $\alpha=\lfloor
u\rfloor$, $\beta=\lfloor v\rfloor=\lfloor v^{\prime}\rfloor$ and
$\gamma=\lfloor w\rfloor$.

On one hand, we have

$\begin{array}[]{lll}\vspace{1ex}&R(\phi(u,v))\gamma\\\
\vspace{1ex}=&\lambda\left\lfloor u\right\rfloor v\left\lfloor
w\right\rfloor+\lambda u\left\lfloor v\right\rfloor\left\lfloor
w\right\rfloor-\mu\left\lfloor uv\right\rfloor\left\lfloor w\right\rfloor-\nu
uv\left\lfloor w\right\rfloor\\\ \vspace{1ex}\rightarrow&\lambda\left\lfloor
u\right\rfloor v\left\lfloor w\right\rfloor+\lambda u(\lambda\left\lfloor
v\right\rfloor w+\lambda v\left\lfloor w\right\rfloor-\mu\left\lfloor
vw\right\rfloor-\nu vw)\\\ \vspace{1ex}&-b(\lambda\left\lfloor uv\right\rfloor
w+\lambda uv\left\lfloor w\right\rfloor-\mu\left\lfloor uvw\right\rfloor-\nu
uvw)-\nu uv\left\lfloor w\right\rfloor\\\ \vspace{1ex}=&\lambda\left\lfloor
u\right\rfloor v\left\lfloor w\right\rfloor+\lambda^{2}u\left\lfloor
v\right\rfloor w+\lambda^{2}uv\left\lfloor w\right\rfloor-\lambda\mu
u\left\lfloor vw\right\rfloor-\lambda\nu uvw\\\
\vspace{1ex}&-\lambda\mu\left\lfloor uv\right\rfloor w-\lambda\mu
uv\left\lfloor w\right\rfloor+\mu^{2}\left\lfloor uvw\right\rfloor+\mu\nu
uvw-\nu uv\left\lfloor w\right\rfloor\\\ \vspace{1ex}=&\lambda\left\lfloor
u\right\rfloor v\left\lfloor w\right\rfloor+\lambda^{2}u\left\lfloor
v\right\rfloor w-\lambda\mu u\left\lfloor vw\right\rfloor\\\
\vspace{1ex}&-\lambda\mu\left\lfloor uv\right\rfloor w+\mu^{2}\left\lfloor
uvw\right\rfloor-(\lambda-\mu)\nu uvw,\end{array}$

where the last equation holds since the coefficient of $uv\left\lfloor
w\right\rfloor$ is $\lambda^{2}-\lambda\mu-\nu$, which vanishes by definition.

On the other hand,

$\begin{array}[]{lll}\vspace{1ex}&\alpha R(\phi(v,x))\\\
\vspace{1ex}=&\lambda\left\lfloor u\right\rfloor\left\lfloor v\right\rfloor
w+\lambda\left\lfloor u\right\rfloor v\left\lfloor
w\right\rfloor-\mu\left\lfloor u\right\rfloor\left\lfloor
vw\right\rfloor-\nu\left\lfloor u\right\rfloor vw\\\
\vspace{1ex}\rightarrow&\lambda(\lambda\left\lfloor u\right\rfloor v+\lambda
u\left\lfloor v\right\rfloor-\mu\left\lfloor uv\right\rfloor-\nu
uv)w+\lambda\left\lfloor u\right\rfloor v\left\lfloor w\right\rfloor\\\
\vspace{1ex}&-\mu(\lambda\left\lfloor u\right\rfloor vw+\lambda u\left\lfloor
vw\right\rfloor-\mu\left\lfloor uvw\right\rfloor-\nu uvw)-\nu\left\lfloor
u\right\rfloor vw\\\ \vspace{1ex}=&\lambda^{2}\left\lfloor u\right\rfloor
vw+\lambda^{2}u\left\lfloor v\right\rfloor w-\lambda\mu\left\lfloor
uv\right\rfloor w-\lambda\nu uvw+\lambda\left\lfloor u\right\rfloor
v\left\lfloor w\right\rfloor\\\ \vspace{1ex}&-\lambda\mu\left\lfloor
u\right\rfloor vw-\lambda\mu u\left\lfloor vw\right\rfloor+\mu^{2}\left\lfloor
uvw\right\rfloor+\mu\nu uvw-\nu\left\lfloor u\right\rfloor vw\\\
\vspace{1ex}=&\lambda\left\lfloor u\right\rfloor v\left\lfloor
w\right\rfloor+\lambda^{2}u\left\lfloor v\right\rfloor w-\lambda\mu
u\left\lfloor vw\right\rfloor\\\ \vspace{1ex}&-\lambda\mu\left\lfloor
uv\right\rfloor w+\mu^{2}\left\lfloor uvw\right\rfloor-(\lambda-\mu)\nu
uvw\quad(\text{by~{}}\lambda^{2}=\lambda\mu+\nu).\end{array}$

We have shown that $R(\phi(u,v))\gamma\downarrow_{\Pi_{\phi}(Z)}\alpha
R(\phi(v,x))$. For the second condition in Theorem 2.18, assume that there are
$q\neq\star\in\mathfrak{M}^{\star}(Z)$ and
$u_{1},u_{2},v_{1},v_{2}\in\mathfrak{M}(Z)$, such that $\lfloor
u_{1}\rfloor\lfloor u_{2}\rfloor=q|_{\lfloor v_{1}\rfloor\lfloor
v_{2}\rfloor}$, then $\lfloor v_{1}\rfloor\lfloor v_{2}\rfloor$ is a subword
of $u_{1}$ or $u_{2}$.

We are done. ∎

With a similar proof, we have the following result:

######  Lemma 5.2.

The OPIs of type $({\mathcal{U}}2^{\prime}_{a})$ in Theorem 3.3 are unital
operated GS with respect to the monomial order $\leq_{\rm{db}}$.

Before dealing with OPI of type
$({\mathcal{U}}1^{\prime}_{b})=({\mathcal{U}}5^{\prime}_{a})$, we introduce
the following lemma.

######  Lemma 5.3.

Let $\phi\in{\mathbf{k}}{\mathfrak{S}}(X)$ be a differential OPI of type
$({\mathcal{U}}1^{\prime}_{b})$ in Theorem 3.3. Then
$S_{\phi}({\mathfrak{M}}(Z)\backslash\\{1\\})$ is an operated GS in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq_{\mathrm{udl}}$.

###### Proof.

Replacing $Z$ by $Z\sqcup\dagger$ in Theorem 4.1,
$S_{\phi}({\mathfrak{S}}(Z\sqcup\dagger))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{S}}(Z\sqcup\dagger)$ with respect to
$\leq_{\mathrm{dl}}$. Then by the definition of the order
$\leq_{\mathrm{udl}}$ on ${\mathfrak{M}}(Z)$, which is induced by
$\leq_{\mathrm{dl}}$ on
${\mathfrak{M}}(Z)\backslash\\{1\\}={\mathfrak{S}}(Z\sqcup\dagger)$, the
assertion follows. ∎

We will not distinguish $\dagger$ from $\lfloor 1\rfloor$ in the following
lemma.

######  Lemma 5.4.

The OPIs of type $({\mathcal{U}}1^{\prime}_{b})=({\mathcal{U}}5^{\prime}_{a})$
in Theorem 3.3 are unital operated GS with respect to the monomial order
$\leq_{\rm{udl}}$.

###### Proof.

Let $\phi(x,y)=x\lfloor y\rfloor-R(x,y)$ be the OPI of type
$({\mathcal{U}}1^{\prime}_{b})=({\mathcal{U}}5^{\prime}_{a})$ and denote
$Z^{\prime}=Z\cup\lfloor 1\rfloor$.

Firstly, we will show that $S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\}$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq_{\rm{udl}}$. By Lemma
5.3, $S_{\phi}({\mathfrak{S}}(Z^{\prime}))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$. So we only need to consider the inclusion
composition of $f\in S_{\phi}({\mathfrak{S}}(Z^{\prime}))$ and $g=\lfloor
1\rfloor-\lambda$. Let $w=\bar{f}=u\lfloor v\rfloor=q|_{\lfloor 1\rfloor}$
where $u,v\in{\mathfrak{S}}(Z^{\prime})$, then $q$ has a left factor $u$ or a
right factor $\lfloor v\rfloor$, i.e., $q=u\lfloor q^{\prime}\rfloor$ or
$q=q^{\prime}\lfloor v\rfloor$ with $q^{\prime}\in{\mathfrak{M}}^{\star}(Z)$.

For the first case, we have $v=q^{\prime}|_{\lfloor 1\rfloor}$, and the
inclusion composition

$\displaystyle\left(f,g\right)^{q}_{w}$ $\displaystyle=f-q|_{g}$
$\displaystyle=\phi(u,q^{\prime}|_{\lfloor 1\rfloor})-u\lfloor
q^{\prime}|_{\lfloor 1\rfloor}\rfloor+u\lfloor q^{\prime}|_{\lambda}\rfloor$
$\displaystyle=-R(u,q^{\prime}|_{\lfloor
1\rfloor-\lambda})+\lambda\left(u\lfloor
q^{\prime}|_{1}\rfloor-R(u,q^{\prime}|_{1})\right)$
$\displaystyle=-R(u,q^{\prime}|_{\lfloor
1\rfloor-\lambda})+\lambda\phi(u,q^{\prime}|_{1}).$

If $q^{\prime}$ has a factor in ${\mathcal{S}}(Z)$, then
$\phi(u,q^{\prime}|_{1})$ is trivial modulo
$(S_{\phi}({\mathfrak{S}}(Z^{\prime})),w)$; otherwise we have
$q^{\prime}=\star$, thus $\phi(u,q^{\prime}|_{1})=u\lfloor 1\rfloor-\lambda u$
is trivial modulo $(\\{\lfloor 1\rfloor-\lambda\\},w)$. And since
$R(u,q^{\prime}|_{\lfloor 1\rfloor-\lambda})$ is trivial modulo $(\\{\lfloor
1\rfloor-\lambda\\},w)$, it follows that $\left(f,g\right)^{q}_{w}$ is trivial
modulo $(S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\},w)$.

For the second case, we have $u=q^{\prime}|_{\lfloor 1\rfloor}$, and similar
to the first case, the inclusion composition

$\left(f,g\right)^{q}_{w}=-R(q^{\prime}|_{\lfloor
1\rfloor-\lambda},v)+\lambda\phi(q^{\prime}|_{1},v)$

is trivial modulo $(S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\},w)$. So we have shown that
$S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor 1\rfloor-\lambda\\}$ is an
operated GS basis in ${\mathbf{k}}{\mathfrak{M}}(Z)$.

Now we show that $S_{\phi}({\mathfrak{M}}(Z))$ is also an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$. Since
${\mathfrak{M}}(Z)={\mathfrak{S}}(Z^{\prime})\cup\\{1\\}$, one can write

$\displaystyle S_{\phi}({\mathfrak{M}}(Z))$ $\displaystyle=\\{\phi(u,v)\ |\
u,v\in{\mathfrak{M}}(Z)\\}$ $\displaystyle=\\{\phi(u,v)\ |\
u,v\in{\mathfrak{S}}(Z^{\prime})\\}\cup\\{\phi(u,1),\phi(1,u),\phi(1,1)\ |\
u\in{\mathfrak{S}}(Z^{\prime})\\}$
$\displaystyle=S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{u\lfloor
1\rfloor-\lambda u,\lfloor 1\rfloor u-\lambda u,\lfloor
1\rfloor-\lambda~{}|~{}u\in{\mathfrak{S}}(Z^{\prime})\\}.$

So it is easy to see $\langle
S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\}\rangle_{\mathfrak{uOpAlg}}=\langle
S_{\phi}({\mathfrak{M}}(Z))\rangle_{\mathfrak{uOpAlg}}$ and ${\rm
Irr}(S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\})={\rm Irr}(S_{\phi}({\mathfrak{M}}(Z)))$. By Theorem 2.10,
the set ${\rm Irr}(S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\})$ is a linear basis of the operated algebra
${\mathbf{k}}{\mathfrak{M}}(Z)/\langle
S_{\phi}({\mathfrak{S}}(Z^{\prime}))\cup\\{\lfloor
1\rfloor-\lambda\\}\rangle_{\mathfrak{uOpAlg}}$, i.e., ${\rm
Irr}(S_{\phi}({\mathfrak{M}}(Z)))$ is a linear basis of
${\mathbf{k}}{\mathfrak{M}}(Z)/\langle
S_{\phi}({\mathfrak{M}}(Z))\rangle_{\mathfrak{uOpAlg}}$. By Theorem 2.10
again, the set $S_{\phi}({\mathfrak{M}}(Z))$ is also an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq_{\rm{udl}}$. ∎

To deal with OPI of type $({\mathcal{U}}5^{\prime}_{b})$, we need a unital
version of Proposition 4.2, whose proof is similar, so we omit it.

######  Proposition 5.5.

Let $\phi=x\lfloor y\rfloor-R(x,y)\in{\mathbf{k}}{\mathfrak{M}}(X)$ be an OPI.
Let $Z$ be a set such that ${\mathfrak{M}}(Z)$ is endowed with a monomial
order. Assume that for all $u,v\in{\mathfrak{M}}(Z)$, $\phi(u,v)$ vanishes or
its leading monomial is still $u\lfloor v\rfloor$. Let

$\Pi_{\phi}(Z):=\\{q|_{u\lfloor v\rfloor}\rightarrow
q|_{R(u,v)}~{}|~{}u,v\in{\mathfrak{M}}(Z),~{}q\in{\mathfrak{M}}^{\star}(Z)\\}.$

If $R(uv,w)\downarrow_{\Pi_{\phi}(Z)}uR(v,w)$, for any
$u,v,w\in{\mathfrak{M}}(Z)$, then $S_{\phi}({\mathfrak{M}}(Z))$ is an operated
GS basis in ${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq$.

######  Lemma 5.6.

The OPI of type $({\mathcal{U}}5^{\prime}_{b})$ in Theorem 3.3 is unital
operated GS with respect to the monomial order $\leq_{\rm{udl}}$.

###### Proof.

For OPI $\phi=x\lfloor y\rfloor-(\lfloor xy\rfloor-\lfloor x\rfloor y+x\lfloor
1\rfloor y)$ of type $({\mathcal{U}}5^{\prime}_{b})$, let $R(x,y)=\lfloor
xy\rfloor-\lfloor x\rfloor y+x\lfloor 1\rfloor y$. Consider the rewriting
system

$\Pi_{\phi}(Z):=\\{q|_{u\lfloor v\rfloor}\rightarrow
q|_{R(u,v)}~{}|~{}u,v\in{\mathfrak{M}}(Z),~{}q\in{\mathfrak{M}}^{\star}(Z)\\}.$

Firstly we show $R(uv,w)\downarrow_{\Pi_{\phi}(Z)}uR(v,w)$. We have

$\begin{array}[]{lll}\vspace{1ex}&uR(v,w)\\\ \vspace{1ex}=&u\lfloor
vw\rfloor-u\lfloor v\rfloor w+uv\lfloor 1\rfloor w\\\
\vspace{1ex}\rightarrow&\lfloor uvw\rfloor-\lfloor u\rfloor vw+u\lfloor
1\rfloor vw-(\lfloor uv\rfloor w-\lfloor u\rfloor vw+u\lfloor 1\rfloor
vw)+uv\lfloor 1\rfloor w\\\ \vspace{1ex}=&\lfloor uvw\rfloor-\lfloor uv\rfloor
w+uv\lfloor 1\rfloor w\\\ \vspace{1ex}=&R(uv,w).\end{array}$

If $u=1$ or $v=1$, then $\phi(u,v)=0$, and for
$u,v\in{\mathfrak{M}}(Z)\backslash 1$, $u\lfloor v\rfloor$ is always the
leading monomial of $\phi(u,v)$ by Proposition 1.20. It follows from
Proposition 5.5 that $S_{\phi}({\mathfrak{M}}(Z))$ is an operated GS basis in
${\mathbf{k}}{\mathfrak{M}}(Z)$. ∎

Notice that we can not apply Proposition 5.5 to the proof of Lemma 5.4, since
for the OPI $\phi$ of type
$({\mathcal{U}}1^{\prime}_{b})=({\mathcal{U}}5^{\prime}_{a})$ in Theorem 3.3,
$\overline{\phi(u,v)}\neq u\lfloor v\rfloor$ if we take $u=1$ and $v\neq 1$.
In fact, $\overline{\phi(1,v)}=\lfloor 1\rfloor v\neq\lfloor v\rfloor$.

######  Lemma 5.7.

Each OPI of the types
$({\mathcal{U}}1^{\prime}_{c})=({\mathcal{U}}2^{\prime}_{b})=({\mathcal{U}}6^{\prime}_{b})$,
$({\mathcal{U}}3^{\prime})=({\mathcal{U}}4^{\prime})=({\mathcal{U}}6^{\prime}_{a})$
and $({\mathcal{U}}5^{\prime}_{c})=({\mathcal{U}}6^{\prime}_{c})$ in Theorem
3.3 is unital operated GS with respect to the monomial order $\leq_{\rm{db}}$.

###### Proof.

It is easy to see each of these OPIs satisfies the conditions in Theorem 2.18,
so the assertion follows. ∎

We have considered all OPI in Theorem 3.3.

######  Theorem 5.8.

Each OPI in Theorem 3.3 is unital operated GS with respect to either the
monomial order $\leq_{\rm{udl}}$ or $\leq_{\rm{db}}$.

###  5.2. Operated GS bases of free unital differential type algebras over
algebras

By Theorem 5.8, Theorem 2.14 implies immediately the following result.

######  Theorem 5.9.

Let $Z$ be a set and $A={\mathbf{k}}{\mathcal{M}}(Z)/I_{A}$ a unital algebra
with a GS basis $G$ with respect to $\leq_{\rm{dlex}}$.

  * (a)

Let $\phi_{1}$ be an OPI of type $({\mathcal{U}}1^{\prime}_{a})$ or
$({\mathcal{U}}2^{\prime}_{a})$. Then $S_{\phi_{1}}({\mathfrak{M}}(Z))\cup G$
is an operated GS basis of $\langle S_{\phi_{1}}({\mathfrak{M}}(Z))\cup
I_{A}\rangle_{\mathfrak{uOpAlg}}$ in ${\mathbf{k}}{\mathfrak{M}}(Z)$ with
respect to $\leq_{\rm{db}}$.

  * (b)

Let $\phi_{2}$ be an OPI of type
$({\mathcal{U}}1^{\prime}_{b})=({\mathcal{U}}5^{\prime}_{a})$ and
$({\mathcal{U}}5^{\prime}_{b})$. Then $S_{\phi_{2}}({\mathfrak{M}}(Z))\cup G$
is an operated GS basis of $\langle S_{\phi_{2}}({\mathfrak{M}}(Z))\cup
I_{A}\rangle_{\mathfrak{uOpAlg}}$ in ${\mathbf{k}}{\mathfrak{M}}(Z)$ with
respect to $\leq_{\rm{udl}}$.

  * (c)

Let $\phi_{3}$ be an OPI of type
$({\mathcal{U}}3^{\prime})=({\mathcal{U}}4^{\prime})=({\mathcal{U}}6^{\prime}_{a})$.
Then $S_{\phi_{3}}({\mathfrak{M}}(Z))\cup G$ is an operated GS basis of
$\langle S_{\phi_{3}}({\mathfrak{M}}(Z))\cup I_{A}\rangle_{\mathfrak{uOpAlg}}$
in ${\mathbf{k}}{\mathfrak{M}}(Z)$ with respect to $\leq_{\rm{db}}$.

  * (d)

Let $\phi_{4}$ be an OPI of type
$({\mathcal{U}}1^{\prime}_{c})=({\mathcal{U}}2^{\prime}_{b})=({\mathcal{U}}6^{\prime}_{b})$.
Then the free unital $\phi_{4}$-algebra
${\mathcal{F}}^{\phi_{4}\text{-}\mathfrak{uAlg}}_{\mathfrak{uAlg}}(A)$ is
isomorphic to $A$.

  * (e)

Let $\phi_{5}$ be an OPI of type
$({\mathcal{U}}5^{\prime}_{c})=({\mathcal{U}}6^{\prime}_{c})$. Then the free
unital $\phi_{5}$-algebra
${\mathcal{F}}^{\phi_{5}\text{-}\mathfrak{uAlg}}_{\mathfrak{uAlg}}(A)$
vanishes.

By Theorem 2.10, we obtain linear bases for these algebras with a simple
proof.

######  Theorem 5.10.

With the same setup as in Theorem 4.7 then we have the following statements:

  * (a)

Let $B_{0}={\rm Irr}_{{\mathcal{M}}}(G)$ and for any $n\geq 1$, define the set
$B_{n}$ inductively as follows

$\bigcup_{r\geq 0}\left\\{{u_{0}\lfloor v_{1}\rfloor u_{1}\cdots\lfloor
v_{r}\rfloor u_{r}~{}|~{}u_{0},u_{r}\in{\rm
Irr}_{{\mathcal{M}}}(G),u_{i}\in{\rm Irr}_{{\mathcal{S}}}(G),1\leq i\leq
r-1,v_{j}\in B_{n-1},1\leq j\leq r}\right\\}.$

Then the set $B=\bigcup_{n\geq 0}B_{n}$ is a linear basis of the free unital
$\phi_{1}$-algebra
${\mathcal{F}}^{\phi_{1}\text{-}\mathfrak{uAlg}}_{\mathfrak{uAlg}}(A)$ over
the unital algebra $A$.

  * (b)

The set

$\bigcup_{r\geq 0}\left\\{{\lfloor\cdots\lfloor\lfloor
u_{r}\rfloor^{(k_{r})}u_{r-1}\rfloor^{(k_{r-1})}\cdots
u_{1}\rfloor^{(k_{1})}u_{0}~{}\Big{|}~{}u_{0},u_{i}\in{\rm
Irr}_{{\mathcal{M}}}(G),k_{i}\geq 1,1\leq i\leq r}\right\\}$

is a linear basis of the free unital $\phi_{2}$-algebra
${\mathcal{F}}^{\phi_{2}\text{-}\mathfrak{uAlg}}_{\mathfrak{uAlg}}(A)$ over
$A$.

  * (c)

The set

$\bigcup_{r\geq 0}\left\\{{u_{0}\lfloor 1\rfloor^{k_{1}}u_{1}\lfloor
1\rfloor^{k_{2}}\cdots\lfloor
1\rfloor^{k_{r}}u_{r}~{}\Big{|}~{}u_{0},u_{r}\in{\rm
Irr}_{{\mathcal{M}}}(G),u_{i}\in{\rm Irr}_{{\mathcal{S}}}(G),1\leq i\leq
r-1,k_{j}\geq 1,1\leq j\leq r}\right\\}$

is a linear basis of the free unital $\phi_{3}$-algebra
${\mathcal{F}}^{\phi_{3}\text{-}\mathfrak{uAlg}}_{\mathfrak{uAlg}}(A)$ over
$A$.

######  Example 5.11.

By taking $a=1$ and $c=0$ in the type (${\mathcal{U}}$1) of Conjecture 3.2, we
get the OPI:

$\phi_{\rm Diff}(x,y)=\left\lfloor xy\right\rfloor-x\left\lfloor
y\right\rfloor-\left\lfloor x\right\rfloor y-b\left\lfloor
x\right\rfloor\left\lfloor y\right\rfloor.$

A $\phi_{\rm Diff}$-algebra is called a differential algebra of weight $b$.
Given a unital algebra $A$ with a GS basis $G$, then we get a linear basis for
the free unital differential algebra of nonzero weight over $A$ by Theorem
5.10 (a) and by Theorem 5.10 (b) in weight zero case.

######  Remark 5.12.

In [15], Guo and Li introduced the notion of differential GS bases in order to
study free differential algebras over algebras. They showed that the free
differential algebra ${\mathcal{F}}_{\mathfrak{uAlg}}^{\phi_{\rm
Diff}\text{-}\mathfrak{uAlg}}(A)$ over a unital ${\mathbf{k}}$-algebra
$A={\mathbf{k}}{\mathcal{M}}(X)/I_{A}$ is the same as the free differential
algebra over the set $X$ modulo the differential ideal generated by the ideal
$I_{A}$ [15, Proposition 2.7], which can be deduced from Proposition 2.4 as
well. They also gave a linear basis of
${\mathcal{F}}_{\mathfrak{uAlg}}^{\phi_{\rm Diff}\text{-}\mathfrak{uAlg}}(A)$
[15, Proposition 3.2].

Our method is completely different from theirs.

Acknowledgements: The authors were supported by NSFC (No. 12071137) and by
STCSM (No. 18dz2271000).

The authors would like to express their sincere gratitude to Xing Gao, Li Guo,
Yunnan Li, Shanghua Zheng for giving useful comments.

## References

  * [1] F. Baader, T. Nipkow, _Term Rewriting and All That_ , Cambridge U. P., Cambridge, 1998.
  * [2] L. A. Bokut and Y. Chen, _Gröbner-Shirshov bases and their calculations_ , Bull. Math. Sci. 4 (2014), 325-395.
  * [3] L. A. Bokut, Y. Chen and J. Qiu, _Gröbner-Shirshov bases for associative algebras with multiple operators and free Rota-Baxter algebras_ , J. Pure Appl. Algebra 214 (2010) 89-110.
  * [4] L. A. Bokut, Y. Chen, K. Kalorkoti, P. Kolesnikov and V. Lopatkin, _Gröbner-Shirshov Bases: Normal Forms, Combinatorial and Decision Problems in Algebra_ , World Scientific 2020.
  * [5] M.R. Bremner and V. Dotsenko, _Algebraic operads: an algorithmic companion_ , Chapman and Hall/CRC, 2016.
  * [6] B. Buchberger,_An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal_ , Ph.D. thesis, University of Innsbruck (1965) (in German).
  * [7] D. Chen, Y.-F. Luo, Y. Zhang, Y.-Y. Zhang, _Free $\Omega$-Rota-Baxter algebras and Gröbner-Shirshov bases_, Internat. J. Algebra Comput. 30 (2020), no. 7, 1359-1373.
  * [8] A. Das, _Leibniz algebras with derivations,_ J. Homotopy Relat. Struct. 16 (2021), no. 2, 245-274.
  * [9] M. Doubek and T. Lada, _Homotopy derivations_ , J. Homotopy Relat. Struct. 11 (2016), no. 3, 599-630.
  * [10] K. Ebrahimi-Fard and L. Guo, _Free Rota-Baxter algebras and rooted trees,_ J. Algebra Appl. 7 (2008), no. 2, 167-194.
  * [11] X. Gao and L. Guo, _Rota’s Classification Problem, rewriting systems and Gröbner-Shirshov bases_ , J. Algebra 470 (2017), 219-253.
  * [12] X. Gao, L. Guo and H. Zhang, _Rota’s program on algebraic operators, rewriting systems and Gröbner-Shirshov bases_ , arXiv:2108.11823.
  * [13] E. Green, _An introduction to noncommutative Groebner bases_ , Lect. Notes Pure Appl. Math., 151 (1993), 167-190.
  * [14] L. Guo, _Operated semigroups, Motzkin paths and rooted trees_ , J. Algebra Comb. 29 (2009), 35-62.
  * [15] L. Guo and Y. Li, _Construction of free differential algebras by extending Gröbner-Shirshov bases_ , J. Symbolic Comput. 107 (2021), 167-189.
  * [16] L. Guo, W. Y. Sit and R. Zhang, _Differential type operators and Gröbner-Shirshov bases_ , J. Symbolic Comput. 52 (2013), 97-123.
  * [17] E. R. Kolchin, _Differential Algebras and Algebraic Groups_ , Academic Press, New York, 1973.
  * [18] P. Lei and L. Guo, _Nijenhuis algebras, NS algebras, and N-dendriform algebras_ , Front. Math. China 7 (2012), no. 5, 827-846.
  * [19] J.-L. Loday, _On the operad of associative algebras with derivation_ , Georgian Math. J. 17 (2010), 347-372.
  * [20] A. R. Magid, _Lectures on differential Galois theory_ , University Lecture Series 7, American Mathematical Society, 1994.
  * [21] P. Malbos, _Lectures on Algebraic Rewriting_ , available at http://math.univ-lyon1.fr/ malbos/ens.html.
  * [22] A. I. Shirshov, _Some algorithmic problem for $\epsilon$-algebras_, Sibirsk. Mat. Z. 3 (1962), 132-137. (in Russian)
  * [23] L. Poinsot, _Differential (Lie) algebras from a functorial point of view_ , Adv. Appl. Math. 72 (2016), 38-76.
  * [24] L. Poinsot, _Differential (monoid) algebra and more_ , In: Post-Proceedings of Algebraic and Algorith-mic Differential and Integral Operators Session, AADIOS 2012, Lecture Notes in Comput. Sci. 8372, Springer, 2014, 164-189.
  * [25] Z. Qi, Y. Qin, K. Wang and G. Zhou, _Free objects and Gröbner-Shirshov bases in operated contexts_ , J. Algebra 584 (2021), 89-124.
  * [26] J. F. Ritt, _Differential Algebra_ , Amer. Math. Sco. Colloq. Pub. 33 (1950), Amer. Math. Soc., New York.
  * [27] J. F. Ritt, _Differential equations from the algebraic standpoint_ , Amer. Math. Sco. Colloq. Pub. 14 (1934), Amer. Math. Soc., New York.
  * [28] G. C. Rota, _Baxter algebras and combinatorial identities I, II_ , Bull. Amer. Math. Soc. 75 (1969) 325-329, pp. 330-334.
  * [29] R. Tang, Y. Frégier and Y. Sheng, _Cohomologies of a Lie algebra with a derivation and applications,_ J. Algebra 534 (2019), 65-99.
  * [30] A. I. Shirshov, _Some algorithmic problems for $\epsilon$-algebras_, Sibirsk. Mat. $\breve{Z}$. 3 (1962), 132-137.
  * [31] S. Xu, _Cohomology, derivations and abelian extensions of $3$-Lie algebras_, J. Algebra Appl. 18 (2019), no. 7, 1950130, 26 pp.
  * [32] M. van der Put and M. Singer, _Galois Theory of Linear Differential Equations_ , Grundlehren der Mathematischen Wissenschaften 328. Springer, Berlin, 2003.
  * [33] J. Zhang and X. Gao, _Free operated monoids and rewriting systems,_ Semigroup Forum  97 (2018), no. 3, 435-456.
  * [34] T. Zhang, X. Gao and L. Guo, _Reynolds algebras and their free objects from bracketed words and rooted trees_ , J. Pure Appl. Algebra 225 (2021), no. 12, Paper No. 106766, 28 pp.
  * [35] Y. Zhang and X. Gao, _Free Rota-Baxter family algebras and (tri)dendriform family algebras_ , Pacific J. Math. 301 (2019), no. 2, 741-766.
  * [36] Z. Zhu. H. Zhang and X. Gao, _Free weighted (modified) differential algebras, free (modified) Rota-Baxter algebras and Gröbner-Shirshov bases,_ arXiv:2108.03563.
  * [37] H. Zhang, X. Gao and L. Guo, _Rota’s program on algebraic operators for Lie algebras_ , in preparation.
  * [38] S. Zheng, X. Gao, L. Guo and W. Sit, _Rota-Baxter type operators, rewriting systems and Gröbner-Shirshov bases_ , J. Symb. Comput. (2021), in press, arXiv:1412.8055v1.