Citation: Dolores Esquivel, Pascal Van Der Voort, Francisco J. Romero-Salguero. Designing advanced functional periodic mesoporous organosilicas for biomedical applications[J]. AIMS Materials Science, 2014, 1(1): 70-86. doi: 10.3934/matersci.2014.1.70
| [1] | Xue Jiang, Yihe Gong . Algorithms for computing Gröbner bases of ideal interpolation. AIMS Mathematics, 2024, 9(7): 19459-19472. doi: 10.3934/math.2024948 |
| [2] | Hui Chen . Characterizations of normal cancellative monoids. AIMS Mathematics, 2024, 9(1): 302-318. doi: 10.3934/math.2024018 |
| [3] | Zaffar Iqbal, Xiujun Zhang, Mobeen Munir, Ghina Mubashar . Hilbert series of mixed braid monoid $ MB_{2, 2} $. AIMS Mathematics, 2022, 7(9): 17080-17090. doi: 10.3934/math.2022939 |
| [4] | Bao-Hua Xing, Nurten Urlu Ozalan, Jia-Bao Liu . The degree sequence on tensor and cartesian products of graphs and their omega index. AIMS Mathematics, 2023, 8(7): 16618-16632. doi: 10.3934/math.2023850 |
| [5] | Alessandro Linzi . Polygroup objects in regular categories. AIMS Mathematics, 2024, 9(5): 11247-11277. doi: 10.3934/math.2024552 |
| [6] | Haijun Cao, Fang Xiao . The category of affine algebraic regular monoids. AIMS Mathematics, 2022, 7(2): 2666-2679. doi: 10.3934/math.2022150 |
| [7] | F. Z. Geng . Piecewise reproducing kernel-based symmetric collocation approach for linear stationary singularly perturbed problems. AIMS Mathematics, 2020, 5(6): 6020-6029. doi: 10.3934/math.2020385 |
| [8] | Shoufeng Wang . Projection-primitive $ P $-Ehresmann semigroups. AIMS Mathematics, 2021, 6(7): 7044-7055. doi: 10.3934/math.2021413 |
| [9] | Mohamed Obeid, Mohamed A. Abd El Salam, Mohamed S. Mohamed . A novel generalized symmetric spectral Galerkin numerical approach for solving fractional differential equations with singular kernel. AIMS Mathematics, 2023, 8(7): 16724-16747. doi: 10.3934/math.2023855 |
| [10] | Ahmet Sinan Cevik, Ismail Naci Cangul, Yilun Shang . Matching some graph dimensions with special generating functions. AIMS Mathematics, 2025, 10(4): 8446-8467. doi: 10.3934/math.2025389 |
The Gröbner basis theory for commutative algebras was introduced by Buchberger [2] which provided a solution to the reduction problem for commutative algebras. In [3], Bergman generalized this theory to the associative algebras by proving the diamond lemma. On the other hand, the parallel theory of the Gröbner basis was developed for Lie algebras by Shirshov in [4]. In [5], Bokut noticed that Shirshov's method works for also associative algebras. Hence Shirshov's theory for Lie and their universal enveloping algebras is called the Gröbner-Shirshov basis theory. We may refer the papers [6,7,8,9,10,11,12,13] for some recent studies over Gröbner-Shirshov bases in terms of algebraic ways, the papers [14,15] related to Hilbert series and the paper [16] in terms of graph theoretic way. Furthermore citation [17] can be used to understand normal forms for the monoid of positive braids by using Gröbner-Shirshov basis.
The word, conjugacy and isomorphism problems (shortly decision problems) have played an important role in group theory since the work of M. Dehn in early 1900's. Among them, especially the word problem has been studied widely in groups (see [18]). It is well known that the word problem for finitely presented groups is not solvable in general; that is, given any two words obtained by generators of the group, there may not be an algorithm to decide whether these words represent the same element in this group.
The method Gröbner-Shirshov basis theory gives a new algorithm to obtain normal forms of elements of groups, monoids and semigroups, and hence a new algorithm to solve the word problem in these algebraic structures (see also [19], for relationship with word problem for semigroups and ideal membership problem for non-commutative polynomail rings). By considering this fact, our aim in this paper is to find a Gröbner-Shirshov basis of the symmetric inverse monoid in terms of the dex-leg ordering on the related words of symmetric inverse monoids.
Symmetric inverse monoids are partial bijections and they are very well known in combinatorics. Easdown et al. [20] studied a presentation for the symmetric inverse monoid $ I_n $. By adding relations $ \sigma _1^2 $ $ = \sigma _2^2 $ $ = \cdots $ $ = \sigma _{n-1}^2 = 1 $ into the presentation of the braid group described in terms of Artin's Theorem, it is obtained the well-known Moore presentation for the symmetric group as defined in [21]. Using this in the Popova's description [22] for the presentation of the symmetric inverse monoid $ I_n $ yields the following presentation:
|
$ In=⟨ε,σ1,σ2,⋯,σn−1;σiσj=σjσi(|i−j|>1),σiσi+1σi=σi+1σiσi+1(1≤i≤n−2),σ21=σ22=⋯=σ2n−1=1,ε2=ε,εσi=σiε(1≤i≤n−2),εσn−1ε=σn−1εσn−1ε=εσn−1εσn−1⟩. $
|
(1.1) |
In [23], the author has also studied presentations of symmetric inverse and singular part of the symmetric inverse monoids.
Let $ k $ be a field and $ k\langle X\rangle $ be the free associative algebra over $ k $ generated by $ X $. Denote by $ X^{\ast} $ the free monoid generated by $ X $, where the empty word is the identity which is denoted by $ 1 $. For a word $ w\in X^{\ast} $, let us denote the length of $ w $ by $ |w| $. Also assume that $ X^{\ast} $ is a well ordered monoid. A well-ordering $ \leq $ on $ X^{\ast } $ is called a monomial ordering if for $ u, v\in X^{\ast } $, we have $ u\leq v\Rightarrow w_{1}uw_{2} \leq w_{1}vw_{2} $, for all $ w_{1}, w_{2}\in X^* $. A standard example of monomial ordering on $ X^* $ is the deg-lex ordering, in which two words are compared first by the degree and then lexicographically, where $ X $ is a well-ordered set.
Every nonzero polynomial $ f\in k\left\langle X\right\rangle $ has the leading word $ \overline{f} $. If the coefficient of $ \overline{f} $ in $ f $ is equal to $ 1 $, then $ f $ is called monic. The following fundamental materials can be found in [3,5,6,7,8,10,11,12,24].
Let $ f $ and $ g $ be two monic polynomials in $ k\langle X\rangle $. Therefore we have two compositions between $ f $ and $ g $ as follows:
$ 1. $ If $ w $ is a word such that $ w = \overline{f}b = a\overline{g} $ for some $ a, b\in X^{\ast } $ with $ |\overline{f}|+|\overline{g}| > |w| $, then the polynomial $ (f, g)_{w} = fb-ag $ is called the intersection composition of $ f $ and $ g $ with respect to $ w $ (and denoted by $ f\wedge g $). In here, the word $ w $ is called an ambiguity of the intersection.
$ 2. $ If $ w = \overline{f} = a\overline{g}b $ for some $ a, b\in X^{\ast } $, then the polynomial $ (f, g)_{w} = f-agb $ is called the inclusion composition of $ f $ and $ g $ with respect to $ w $ (and denoted by $ f\vee g $). In this case, the word $ w $ is called an ambiguity of the inclusion.
If $ g $ is a monic polynomial, $ \overline{f} = a\overline{g}b $ and $ \alpha $ is the coefficient of the leading term $ \overline{f} $, then the transformation $ f\mapsto f-\alpha agb $ is called an elimination of the leading word (ELW) of $ g $ in $ f $.
Let $ S\subseteq k\left\langle X\right\rangle $ with each $ s\in S $ monic. Then the composition $ (f, g)_{w} $ is called trivial modulo $ (S, w) $ if $ (f, g)_{w} = \sum\alpha_{i}a_{i}s_{i}b_{i} $, where each $ \alpha _{i}\in k, \:a_{i}, b_{i}\in X^{\ast }, \:s_{i}\in S $ and $ a_{i}\overline{s_{i}}b_{i} < w $. If this is the case, then we write $ (f, g)_{w}\equiv 0\ mod(S, w) $. In general, for $ p, q\in k\langle X\rangle $, we write $ p\equiv q\ mod(S, w) $ which means that $ p-q = \sum\alpha_i a_{i}s_{i}b_{i} $, where each $ \alpha _{i}\in k, \:a_{i}, b_{i}\in X^{\ast }, \:s_{i}\in S $ and $ a_{i}\overline{s_{i}}b_{i} < w $.
A set $ S $ with the well ordering $ \leq $ is called a Gröbner-Shirshov basis for $ k\left\langle X\mid S\right\rangle $ if every composition $ (f, g)_{w} $ of polynomials in $ S $ is trivial modulo $ S $ and the corresponding $ w $.
The following lemma was proved by Shirshov [4] for free Lie algebras (with deg-lex ordering) in 1962 ([24]). In 1976, Bokut [5] specialized the Shirshov's approach to associative algebras (see also [3]). On the other hand, for commutative polynomials, this lemma is known as the Buchberger's Theorem (cf. [2,25]).
Lemma 1 (Composition-Diamond Lemma). Let $ k $ be a field,
| $ A = k\left\langle X\mid S\right\rangle = \ k\langle X\rangle / Id(S) $ |
and $ \leq $ a monomial order on $ X^{\ast } $, where $ Id(S) $ is the ideal of $ k\langle X\rangle $ generated by $ S $. Then the following statements are equivalent:
1. $ S $ is a Gröbner-Shirshov basis.
2. $ f\in Id(S)\Rightarrow \overline{f} = a\overline{s}b $ for some $ s\in S $ and $ a, b\in X^{\ast } $.
3. $ Irr(S) = \{u\in X^{\ast }\mid u\neq a\overline{s}b, s\in S, a, b\in X^{\ast }\} $ is a basis of the algebra $ A = k\left\langle X\mid S\right\rangle $.
If a subset $ S $ of $ k\langle X\rangle $ is not a Gröbner-Shirshov basis, then we can add to $ S $ all nontrivial compositions of polynomials of $ S $, and by continuing this process (maybe infinitely) many times, we eventually obtain a Gröbner-Shirshov basis $ S^{comp} $. Such a process is called the Shirshov algorithm.
If $ S $ is a set of "semigroup relations" (that is, the polynomials in $ S $ are of the form $ u-v $, where $ u, v\in X^* $), then a nontrivial composition will have the same form. As a result, the set $ S^{comp} $ also consists of semigroup relations.
Let $ M = sgp\left\langle X\mid S\right\rangle $ be a semigroup presentation. Then $ S $ is a subset of $ k\langle X\rangle $ and hence one can find a Gröbner-Shirshov basis $ S^{comp} $. The last set does not depend on $ k $, and as mentioned before, it consists of semigroup relations. We will call $ S^{comp} $ a Gröbner-Shirshov basis of $ M $. This is the same as a Gröbner-Shirshov basis of the semigroup algebra $ kM = k\left\langle X\mid S\right\rangle $. If $ S $ is a Gröbner-Shirshov basis of the semigroup $ M = sgp\left\langle X\mid S\right\rangle $, then $ Irr\left(S\right) $ is a normal form for $ M $ [9,26].
The target of this section is to obtain a Gröbner-Shirshov basis for the symmetric inverse monoid $ I_n $ by taking into account the presentation given in (1.1). After that we will indicate the solvability of the word problem over $ I_n $.
By ordering the generators as $ \varepsilon > {\sigma _{n - 1}} > {\sigma _{n - 2}} > {\sigma _{n - 3}} > \cdots > {\sigma _2} > {\sigma _1} $ in (1.1), we have the following main result of this paper.
Theorem 2. A Gröbner-Shirshov basis for the symmetric inverse monoid consists of the following relations:
|
$ (1)σ2i=1(1≤i≤n−1),(2)σiσj=σjσi(|i−j|>1),(3)ε2=ε,(4)εσi=σiε(1≤i≤n−2),(5)σi+1σiσMi−1i−1⋯σM11σi+1=σiσi+1σiσMi−1i−1⋯σM11(1≤i≤n−2,Mk={0,1}(1≤k≤i−1)),(6)σn−1εσn−1σPn−2n−2⋯σP11ε=εσn−1σPn−2n−2⋯σP11ε(Pk={0,1}(1≤k≤n−2)),(7)σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2⋯σφjjε=εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i,1≤i≤n−3,2≤j≤n−2,Qk1,φk2={0,1}(i≤k1≤n−3,j≤k2≤n−2)),(7′)σn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε=εrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε(2<p<n,r={0,1},s≥⋯≥j≥i,1≤i≤n−3,2≤j,s≤n−2,Qk1,φk2,λk3={0,1}(i≤k1≤n−4,j≤k2≤n−3,s≤k3≤n−2)),(8)εσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−t=εσn−1σLn−2n−2⋯σLn−tn−tεσLn−1n−1σLn−2n−2⋯σLn−t+1n−t+1(2≤t≤n−1,Lk={0,1}(1≤k≤n−1)),(9)σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1⋯σU11)(σV(n−k)+2(n−k)+2σV(n−k)+1(n−k)+1⋯σV11)⋯(σSn−1n−1σSn−2n−2⋯σS11)(εσn−1σTn−2n−2⋯σT11)ε=(σ(n−k)+1σn−kσU(n−k)+1(n−k)+1⋯σU11)(σV(n−k)+2(n−k)+2σV(n−k)+1(n−k)+1⋯σV11)⋯(σSn−1n−1σSn−2n−2⋯σS11)(εσn−1σTn−2n−2⋯σT11)ε(2≤k≤n−1,Uk1,Vk2,Sk3,Tk4={0,1}(1≤k1≤(n−k)−1,1≤k2≤(n−k)+2,1≤k3≤n−1,1≤k4≤n−2)),(10)σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1⋯σX11)(σY(n−k)+2(n−k)+2σY(n−k)+1(n−k)+1⋯σY11)⋯(σZn−2n−2σZn−3n−3⋯σZ11)(εσn−1σn−2σWn−3n−3⋯σWii)(εσn−1σRn−2n−2⋯σRjj)ε=(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1⋯σX11)(σY(n−k)+2(n−k)+2σY(n−k)+1(n−k)+1⋯σY11)⋯(σZn−2n−2σZn−3n−3⋯σZ11)(εσn−1σn−2σWn−3n−3⋯σWii)(εσn−1σRn−2n−2⋯σRjj)ε(j>i,1≤i≤n−2,2≤j≤n−2,3≤k≤n−1,Xk1,Yk2,Zk3,Wk4,Rk5={0,1}(1≤k1≤(n−k)−1,1≤k2≤(n−k)+2,1≤k3≤n−2,1≤k4≤n−3,1≤k5≤n−2). $
|
We also have the following additional conditions.
● For the relation $ (5) $: For $ 1\leq k < i-1 $, to take $ M_k = 1 $ it is necessary $ M_{k+1} = 1 $.
● For the relation $ (6) $: For $ 1\leq k < n-2 $, to take $ P_k = 1 $ it is necessary $ P_{k+1} = 1 $.
● For the relation $ (7) $: For $ i\leq k < n-3 $, to take $ Q_k = 1 $ it is necessary $ Q_{k+1} = 1 $.
For $ j\leq k < n-2 $, to take $ \varphi_k = 1 $ it is necessary $ \varphi_{k+1} = 1 $.
● For the relation $ (7') $: For $ i\leq k < n-4 $, to take $ Q_k = 1 $ it is necessary $ Q_{k+1} = 1 $.
For $ j\leq k < n-3 $, to take $ \varphi_k = 1 $ it is necessary $ \varphi_{k+1} = 1 $.
For $ s\leq k < n-2 $, to take $ \lambda_k = 1 $ it is necessary $ \lambda_{k+1} = 1 $.
● For the relation $ (8) $: For $ n-t\leq k < n-2 $, to take $ L_k = 1 $ it is necessary $ L_{k+1} = 1 $.
● For the relation $ (9) $: For $ 1\leq t < (n-k)-1 $, to take $ U_t = 1 $ it is necessary $ U_{t+1} = 1 $.
For $ 1\leq t < (n-k)+2 $, to take $ V_t = 1 $ it is necessary $ V_{t+1} = 1 $.
For $ 1\leq t < n-1 $, to take $ S_t = 1 $ it is necessary $ S_{t+1} = 1 $.
For $ 1\leq t < n-2 $, to take $ T_t = 1 $ it is necessary $ T_{t+1} = 1 $.
● For the relation $ (10) $: For $ 1\leq t < (n-k)-1 $, to take $ X_t = 1 $ it is necessary $ X_{t+1} = 1 $.
For $ 1\leq t < (n-k)+2 $, to take $ Y_t = 1 $ it is necessary $ Y_{t+1} = 1 $.
For $ 1\leq t < n-2 $, to take $ Z_t = 1 $ it is necessary $ Z_{t+1} = 1 $.
For $ i\leq t < n-3 $, to take $ W_t = 1 $ it is necessary $ W_{t+1} = 1 $.
For $ j\leq t < n-2 $, to take $ R_t = 1 $ it is necessary $ R_{t+1} = 1 $.
Proof. Relations given for $ I_n $ in (1.1) provide relations among (1)–(10). Now we need to prove that all compositions among relations (1)–(10) are trivial. To do that, firstly, we consider intersection compositions of these relations. Hence we have the following ambiguties $ w $:
|
$ (1)∧(1):w=σ3i(1≤i≤n−1),(1)∧(2):w=σ2iσj(|i−j|>1),(1)∧(5):w=σ2i+1σiσMi−1i−1⋯σM11σi+1(1≤i≤n−2),(1)∧(6):w=σ2n−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε,(1)∧(7):w=σ2n−2εσn−1σQn−2n−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2σφn−3n−3⋯σφjjε,(1)∧(7′):w=σ2n−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε,(1)∧(9):w=σ2n−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε,(1)∧(10):w=σ2n−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σWn−3n−3⋯σWiiεσn−1σRn−2n−2σRn−3n−3⋯σRjjε(j>i), $
|
|
$ (2)∧(1):w=σiσ2j(|i−j|>1),(2)∧(2):w=σiσjσk(|i−j|>1,|j−k|>1),(2)∧(5):w=σiσj+1σjσMj−1j−1⋯σM11σj+1(|i−(j+1)>1|),(2)∧(7′):w=σiσn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε(|i−(n−p)>1|),(2)∧(9):w=σiσn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2..σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε(|i−(n−k)>1|),(2)∧(10):w=σiσn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2σRn−3n−3⋯σRjjε(j>i,|i−(n−k)>1|), $
|
|
$ (3)∧(3):w=ε3,(3)∧(4):w=ε2σi(1≤i≤n−2),(3)∧(8):w=ε2σn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−t, $
|
|
$ (4)∧(1):w=εσ2i(1≤i≤n−2),(4)∧(2):w=εσiσj(|i−j|>1),(4)∧(5):w=εσi+1σiσMi−1i−1σMi−2i−2⋯σM11σi+1(1≤i≤n−3),(4)∧(7):w=εσn−2εσn−1σQn−2n−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2σφn−3n−3⋯σφjjε,(4)∧(7′):w=εσn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε,(4)∧(9):w=εσn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε,(4)∧(10):w=εσn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2σRn−3n−3⋯σRjjε, $
|
|
$ (5)∧(1):w=σi+1σiσMi−1i−1⋯σM11σ2i+1(1≤i≤n−2),(5)∧(2):w=σi+1σiσMi−1i−1⋯σM11σi+1σj(|i+1−j|>1),(5)∧(5):w=σi+1σiσMi−1i−1⋯σM11σi+1σiσMi−1i−1⋯σM11σi+1(1≤i≤n−2),(5)∧(6):w=σn−1σn−2σMn−3n−3σMn−4n−4⋯σM11σn−1εσn−1σPn−2n−2⋯σP11ε,(5)∧(7):w=σn−2σn−3σMn−4n−4σMn−5n−5⋯σM11σn−2εσn−1σQn−2n−2⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i),(5)∧(7′):w=σn−pσn−p−1σMn−p−2n−p−2⋯σM11σn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε,(5)∧(9):w=σn−kσ(n−k)−1σM(n−k)−2(n−k)−2σM(n−k)−3(n−k)−3⋯σM11(σn−kσ(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε,(5)∧(9):w=σn−kσ(n−k)−1σM(n−k)−2(n−k)−2σM(n−k)−3(n−k)−3⋯σM11σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε,(5)∧(10):w=σn−kσ(n−k)−1σM(n−k)−2(n−k)−2⋯σM11σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2σRn−3n−3⋯σRjjε(j>i),(5)∧(10):w=σn−kσ(n−k)−1σM(n−k)−2(n−k)−2⋯σM11σn−kσ(n−k)−1σX(n−k)−2(n−k)−2⋯σX11⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2σRn−3n−3⋯σRjjε(j>i), $
|
|
$ (6)∧(3):w=σn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε2,(6)∧(4):w=σn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11εσi(1≤i≤n−2),(6)∧(6):w=σn−1εσn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε,(6)∧(7):w=σn−1εσn−1σn−2εσn−1σn−2σQn−3n−3σQn−4n−4⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i),(6)∧(8):w=σn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11εσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−t,(6)∧(8):w=σn−1εσn−1σPn−2n−2⋯σPn−tn−tεσn−1σPn−2n−2⋯σPn−tn−t, $
|
|
$ (7)∧(3):w=σn−2εσn−1σQn−2n−2⋯σQiiεσn−1σφn−2n−2⋯σφjjε2(j>i),(7)∧(4):w=σn−2εσn−1σQn−2n−2⋯σQiiεσn−1σφn−2n−2⋯σφjjεσt,(j>i,1≤i≤n−2,2≤j≤n−2,1≤t≤n−2),(7)∧(6):w=σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1εσn−1σPn−2n−2⋯σP11ε(1≤i≤n−2),(7)∧(7):w=σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i,1≤i≤n−3,2≤j≤n−2),(7)∧(8):w=σn−2εσn−1σQn−2n−2⋯σQiiεσn−1σφn−2n−2⋯σφjjεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−t(j>i,1≤i≤n−2,2≤j≤n−2),(7)∧(8):w=σn−2εσn−1σQn−2n−2⋯σQiiεσn−1σφn−2n−2⋯σφjjεσn−1σφn−2n−2⋯σφjj,(7′)∧(7′):w=σn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssεσn−1σϕn−2n−2⋯σϕppε,(7′)∧(8):w=σn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssεσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−t,(7′)∧(8):w=σn−pεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssεσn−1σλn−2n−2⋯σλss, $
|
|
$ (8)∧(1):w=εσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯(σLn−tn−t)2,(8)∧(2):w=εσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tσj(|n−t−j|>1),(8)∧(5):w=εσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tσ(n−t)−1σM(n−t)−2(n−t)−2⋯σM11σn−t(1≤t≤n−2),(8)∧(6):w=εσn−1εσn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε,(8)∧(6):w=εσn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε,(8)∧(7):w=εσn−1σn−2εσn−1σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i),(8)∧(7):w=εσn−1σn−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2⋯σφjjε(j>i),(8)∧(7′):w=εσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−tεrσn−1σn−2σn−3σQn−4n−4⋯σQiiεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε,(8)∧(7′):w=εσn−1σLn−2n−2⋯σLn−tn−tεσn−1σn−2σn−3σLn−4n−4⋯σLn−tn−tεσn−1σn−2σφn−3n−3⋯σφjjε⋯σn−1σλn−2n−2⋯σλssε,(8)∧(8):w=εσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−t,(8)∧(9):w=εσn−1σn−2⋯σn−kεσn−1σn−2⋯σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2⋯σT11ε,(8)∧(10):w=εσn−1σn−2⋯σn−kεσn−1σn−2⋯σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2⋯σRjjε(j>i), $
|
|
$ (9)∧(3):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11ε2,(9)∧(4):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11εσi(1≤i≤n−2),(9)∧(6):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯(σSn−1n−1σSn−2n−2σSn−3n−3⋯σS11)εσn−1εσn−1σPn−2n−2σPn−3n−3⋯σP11ε,(9)∧(7):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯(σSn−1n−1σSn−2n−2σSn−3n−3⋯σS11)εσn−1σn−2εσn−1σn−2σQn−3n−3σQn−4n−4⋯σQiiεσn−1σφn−2n−2σφn−3n−3⋯σφjjε(j>i),(9)∧(7):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯σSn−1n−1σSn−2n−2εσn−1σn−2σQn−3n−3⋯σQiiεσn−1σφn−2n−2σφn−3n−3⋯σφjjε(j>i),(9)∧(8):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11εσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−tεσn−1σLn−2n−2σLn−3n−3⋯σLn−tn−t,(9)∧(8):w=σn−k(σ(n−k)+1σn−kσU(n−k)−1(n−k)−1σU(n−k)−2(n−k)−2⋯σU11)⋯εσn−1σTn−2n−2σTn−3n−3⋯σT11εσn−1σTn−2n−2σTn−3n−3⋯σT11, $
|
|
$ (10)∧(3):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2⋯σRjjε2(j>i),(10)∧(4):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2⋯σRjjεσt(1≤t≤n−2),(10)∧(6):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1εσn−1σPn−2n−2⋯σP11ε,(10)∧(7):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σn−2εσn−1σn−2σQn−3n−3⋯σQttεσn−1σφn−2n−2⋯σφjjε(j>t),(10)∧(7′):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σn−2Rn−2⋯σRjjεσn−1σSn−2n−2⋯σSllε(l>j>i),(10)∧(8):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2⋯σRjjεσn−1εσn−1σLn−2n−2⋯σLn−tn−tεσn−1σLn−2n−2⋯σLn−tn−t(j>i),(10)∧(8):w=σn−k(σ(n−k)+1σn−kσX(n−k)−1(n−k)−1σX(n−k)−2(n−k)−2⋯σX11)⋯εσn−1σn−2σWn−3n−3⋯σWiiεσn−1σRn−2n−2⋯σRjjεσn−1σRn−2n−2⋯σRjj(j>i), $
|
All these ambiguities are trivial. Let us show some of them as in the following.
|
$ (1)∧(5):w=σ2i+1σiσMi−1i−1⋯σM11σi+1,(1≤i≤n−2),(f,g)w=(σ2i+1−1)σiσMi−1i−1⋯σM11σi+1−σi+1(σi+1σiσMi−1i−1⋯σM11σi+1−σiσi+1σiσMi−1i−1⋯σM11)=σ2i+1σiσMi−1i−1⋯σM11σi+1−σiσMi−1i−1⋯σM11σi+1−σ2i+1σiσMi−1i−1⋯σM11σi+1+σi+1σiσi+1σiσMi−1i−1⋯σM11 $
|
|
$ =σi+1σiσi+1σiσMi−1i−1⋯σM11−σiσMi−1i−1⋯σM11σi+1≡σiσi+1σi2σMi−1i−1⋯σM11−σiσMi−1i−1⋯σM11σi+1≡σiσi+1σMi−1i−1⋯σM11−σiσMi−1i−1⋯σM11σi+1≡σiσMi−1i−1⋯σM11σi+1−σiσMi−1i−1⋯σM11σi+1≡0mod(S,w). $
|
|
$ (2)∧(2):w=σiσjσk(|i−j|>1,|j−k|>1),(f,g)w=(σiσj−σjσi)σk−σi(σjσk−σkσj)=σiσjσk−σjσiσk−σiσjσk+σiσkσj=σiσkσj−σjσiσk≡σkσiσj−σjσkσi≡σkσjσi−σkσjσi≡0mod(S,w). $
|
|
$ (6)∧(4):w=σn−1εσn−1σPn−2n−2⋯σPii⋯σP11εσi(1≤i≤n−2),(f,g)w=(σn−1εσn−1σPn−2n−2⋯σPii⋯σP11ε−εσn−1σPn−2n−2⋯σPii⋯σP11ε)σi−σn−1εσn−1σPn−2n−2⋯σPii⋯σP11(εσi−σiε)=σn−1εσn−1σPn−2n−2⋯σPii⋯σP11εσi−εσn−1σPn−2n−2⋯σPii⋯σP11εσi−σn−1εσn−1σPn−2n−2⋯σPii⋯σP11εσi+σn−1εσn−1σPn−2n−2⋯σPii⋯σP11σiε=σn−1εσn−1σPn−2n−2⋯σPii⋯σP11σiε−εσn−1σPn−2n−2⋯σPii⋯σP11εσi≡σn−1εσn−1σPn−2n−2⋯σPi−1i−1σPiiσPi−1i−1⋯σP11ε−εσn−1σPn−2n−2⋯σPii⋯σP11σiε≡σPi−1i−1σn−1εσn−1σPn−2n−2⋯σP11ε−εσn−1σPn−2n−2⋯σPi−1i−1σPiiσPi−1i−1⋯σP11ε≡σPi−1i−1εσn−1σPn−2n−2⋯σP11ε−σPi−1i−1εσn−1σPn−2n−2⋯σP11ε≡0mod(S,w). $
|
It is seen that there are no any inclusion compositions among relations (1)–(10). This ends up the proof.
As a consequence of Lemma 1 and Theorem 2, we have the following result.
Corollary 3. Let $ C(u) $ be a normal form of a word $ u\in I_{n} $. Then $ C(u) $ is of the form
|
$ W1εk1W2εk2⋯Wnεkn, $
|
where $ {{k_p} = \left\{ {0, 1} \right\}} $ $ (1 \leq p \leq n) $. In this above expression,
● if $ {k_p} = 1\, \, \left({1 \leq p \leq n - 1} \right) $ then the word $ {W_{p\, + 1\, }} $ which begins with $ {\sigma _{n - 1}} $ and generated by $ \sigma _i $ $ (1 \leq i \leq n - 1) $ is actually a reduced word. Moreover the word $ {W_{1}} $ generated by $ \sigma _i $ $ (1 \leq i \leq n - 1) $ is an arbitrary reduced word.
● if $ {k_p} = 0\, \, \left({1 \leq p \leq n - 1} \right) $ then the word $ W_pW_{p+1} $ is also reduced.
In addition, subwords of the forms $ W_i\varepsilon^{k_i}W_{i+1}\varepsilon^{k_{i+1}} $ $ \left({1 \leq i \leq n - 1} \right) $, $ W_j\varepsilon^{k_j}W_{j+1}\varepsilon^{k_{j+1}}W_{j+2}\varepsilon^{k_{j+2}} $ $ \left({1 \leq j \leq n - 2} \right) $, $ W_r\varepsilon^{k_r}W_{r+1}\varepsilon^{k_{r+1}}W_{r+2}\varepsilon^{k_{r+2}}W_{r+3}\varepsilon^{k_{r+3}} $ $ \left({1 \leq r \leq n - 3} \right) $ and $ \varepsilon^{k_s}W_{s+1}\varepsilon^{k_{s+1}}W_{s+2} $ $ \left({1 \leq s \leq n - 2} \right) $ must be reduced.
By Corollary 3, we can say that the word problem is solvable for symmetric inverse monoid $ I_{n} $.
Remark 4. We note that if we change the orderings on words we find another Gröbner-Shirshov bases related to chosen orederings. Thus we get normal form for given algebraic structure depending on ordering. To get this normal form it is used third item of Composition-Diamond Lemma. It is known that to get normal form structure implies solvability of the word problem. If one can not obtain a Gröbner-Shirshov basis according to chosen ordering on words, this does not mean that the word problem is not solvable.
As an application of Theorem 2, we will give the following Example 5 which describes a Gröbner-Shirshov basis for the symmetric inverse monoid $ I_4 $. The accuracy and efficiency of this example can be seen by "$ GBNP $ package in GAP [1] which computes Gröbner bases of non-commutative polynomials as follows.
| $ \mathtt{gap \gt \ LoadPackage("GBNP",\ "0",\ {\bf{false}});}\\ \mathtt{{\bf{true}}}\\ \mathtt{gap \gt \ SetInfoLevel(InfoGBNP,\ 1);}\\ \mathtt{gap \gt \ SetInfoLevel(InfoGBNPTime,\ 1);}\\ \mathtt{gap \gt \ A: =\ FreeAssociativeAlgebraWithOne(Rationals,\ "s1",\ "s2",\ "s3",\ "e");}\\ \mathtt{ \lt algebra-with-one\ over\ Rationals,\ with\ 4\ generators \gt }\\ \mathtt{gap \gt \ g: =\ GeneratorsOfAlgebra(A);}\\ \mathtt{[\ (1)^{*} \lt identity\ ... \gt ,\ (1)^{*}s1,\ (1)^{*}s2,\ (1)^{*}s3,\ (1)^{*}e\ ]}\\ \mathtt{gap \gt \ s1: =\ g[2];;s2: =\ g[3];;s3: =\ g[4];;e: =\ g[5];;o: =\ g[1];}\\ \mathtt{(1)^{*} \lt identity\ ... \gt }\\ \mathtt{gap \gt \ GBNP.ConfigPrint(A);}\\ \mathtt{gap \gt \ twosidrels: =\ [s1} \wedge \mathtt{2-o,\ s2} \wedge \mathtt{2-o,\ s3} \wedge \mathtt{2-o,\ (s1^{*}s2)} \wedge \mathtt{3-o,\ (s2^{*}s3)} \wedge \mathtt{3-o,\ (s1^{*}s3)} \wedge \mathtt{2-o,}\\ \mathtt{e} \wedge \mathtt{2-e,\ s1^{*}e-e^{*}s1,\ s2^{*}e-e^{*}s2,\ e^{*}s3^{*}e-(e^{*}s3)} \wedge \mathtt{2,\ e^{*}s3^{*}e-(s3^{*}e)} \wedge \mathtt{2];}\\ \mathtt{[\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}s1} \wedge \mathtt{2,\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}s2} \wedge \mathtt{2,}\\ \mathtt{(-1)^{*} \lt identity\ ... \gt +(1)^{*}s3} \wedge \mathtt{2,\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}(s1^{*}s2)} \wedge \mathtt{3,}\\ \mathtt{(-1)^{*} \lt identity\ ... \gt +(1)^{*}(s2^{*}s3)} \wedge \mathtt{3,\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}(s1^{*}s3) \wedge 2,}\\ \mathtt{(-1)^{*}e+(1)^{*}e} \wedge \mathtt{2,\ (1)^{*}s1^{*}e+(-1)^{*}e^{*}s1,\ (1)^{*}s2^{*}e+(-1)^{*}e^{*}s2,}\\ \mathtt{(1)^{*}e^{*}s3^{*}e+(-1)^{*}(e^{*}s3)} \wedge \mathtt{2,\ (1)^{*}e^{*}s3^{*}e+(-1)^{*}(s3^{*}e)} \wedge \mathtt{2\ ]}\\ \mathtt{gap \gt \ prefixrels: =\ [e,\ s1-o,\ s2-o,\ s3^{*}e-s3];}\\ \mathtt{[\ (1)^{*}e,\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}s1,\ (-1)^{*} \lt identity\ ... \gt +(1)^{*}s2,\ (-1)^{*}s3+(1)^{*}s3^{*}e\ ]}\\ \mathtt{gap \gt \ PrintNPList(GBR.ts);}\\ \mathtt{s1} \wedge \mathtt{2\ -\ 1}\\ \mathtt{s2}\mathtt{\wedge\ 2\ -\ 1}\\ \mathtt{s3s1\ -\ s1s3}\\ \mathtt{s3}\mathtt{\wedge\ 2\ -\ 1}\\ \mathtt{es1\ -\ s1e}\\ \mathtt{es2\ -\ s2e}\\ \mathtt{e} \wedge \mathtt{2\ -\ e}\\ \mathtt{s2s1s2\ -\ s1s2s1}\\ \mathtt{s3s2s3\ -\ s2s3s2}\\ \mathtt{s3s2s1s3\ -\ s2s3s2s1}\\ \mathtt{s3es3e\ -\ es3e}\\ \mathtt{es3es3\ -\ es3e}\\ \mathtt{s3es3s2e\ -\ es3s2e}\\ \mathtt{s2s3s2es3e\ -\ s3s2es3e}\\ \mathtt{s3es3s2s1e\ -\ es3s2s1e}\\ \mathtt{es3s2es3s2\ -\ es3s2es3}\\ \mathtt{s2s3s2s1es3e\ -\ s3s2s1es3e}\\ \mathtt{s2s3s2es3s2e\ -\ s3s2es3s2e}\\ \mathtt{s2es3s2es3e\ -\ es3s2es3e}\\ \mathtt{s1s2s1s3s2es3e\ -\ s2s1s3s2es3e}\\ \mathtt{s2s3s2s1es3s2e\ -\ s3s2s1es3s2e}\\ \mathtt{s2s3s2es3s2s1e\ -\ s3s2es3s2s1e}\\ \mathtt{s2es3s2s1es3e\ -\ es3s2s1es3e}\\ \mathtt{es3s2s1es3s2s1\ -\ es3s2s1es3s2}\\ \mathtt{s1s2s1s3s2s1es3e\ -\ s2s1s3s2s1es3e}\\ \mathtt{s1s2s1s3s2es3s2e\ -\ s2s1s3s2es3s2e}\\ \mathtt{s1s2s1es3s2es3e\ -\ s2s1es3s2es3e}\\ \mathtt{s2s3s2s1es3s2s1e\ -\ s3s2s1es3s2s1e}\\ \mathtt{s2es3s2s1es3s2e\ -\ es3s2s1es3s2e}\\ \mathtt{s1s2s1s3s2s1es3s2e\ -\ s2s1s3s2s1es3s2e}\\ \mathtt{s1s2s1s3s2es3s2s1e\ -\ s2s1s3s2es3s2s1e}\\ \mathtt{s1s2s1es3s2s1es3e\ -\ s2s1es3s2s1es3e}\\ \mathtt{s1s3s2s1es3s2es3e\ -\ s3s2s1es3s2es3e}\\ \mathtt{s1s2s1s3s2s1es3s2s1e\ -\ s2s1s3s2s1es3s2s1e}\\ \mathtt{s1s2s1es3s2s1es3s2e\ -\ s2s1es3s2s1es3s2e}\\ \mathtt{s1s3s2s1es3s2s1es3e\ -\ s3s2s1es3s2s1es3e}\\ \mathtt{s1es3s2s1es3s2es3e\ -\ es3s2s1es3s2es3e}\\ \mathtt{s1s3s2s1es3s2s1es3s2e\ -\ s3s2s1es3s2s1es3s2e} $ |
We note that by $ GBNP $ package program one can compute Gröbner-Shirshov basis of symmetric inverse monoids for small sizes, for example $ I_4 $ and $ I_5 $. But there are no any other computer programs that compute a Gröbner-Shirshov basis for general size of symmetric inverse monoids. For this reason, it is worth to study and obtain a Gröbner-Shirshov basis for this important structure.
Example 5. The presentation of $ I_4 $ is as follows.
|
$ ⟨ε,σ1,σ2,σ3;σ21=σ22=σ23=1,σ3σ1=σ1σ3,ε2=ε,εσ1=σ1ε,εσ2=σ2ε,σ3σ2σ3=σ2σ3σ2,σ2σ1σ2=σ1σ2σ1,σ3εσ3ε=εσ3ε,εσ3εσ3=εσ3ε⟩. $
|
We use deg-lex order induced by $ \sigma _1 < \sigma _2 < \sigma _{3} < \varepsilon $. By this ordering, a Gröbner-Shirshov basis for symmetric inverse monoid $ I_4 $ consists of the following $ 38 $ relations.
|
$ (1)σ21=1,σ22=1,σ23=1,(2)σ3σ1=σ1σ3,(3)ε2=ε,(4)εσ1=σ1ε,εσ2=σ2ε,(5)σ3σ2σ3=σ2σ3σ2,σ2σ1σ2=σ1σ2σ1,σ3σ2σ1σ3=σ2σ3σ2σ1,(6)σ3εσ3ε=εσ3ε,σ3εσ3σ2ε=εσ3σ2ε,σ3εσ3σ2σ1ε=εσ3σ2σ1ε,(7)σ2εσ3σ2εσ3ε=εσ3σ2εσ3ε,σ2εσ3σ2σ1εσ3ε=εσ3σ2σ1εσ3ε,σ2εσ3σ2σ1εσ3σ2ε=εσ3σ2σ1εσ3σ2ε,(7′)σ1σ3σ2σ1εσ3σ2εσ3ε=σ3σ2σ1εσ3σ2εσ3ε,σ1σ3σ2σ1εσ3σ2σ1εσ3ε=σ3σ2σ1εσ3σ2σ1εσ3ε,σ1σ3σ2σ1εσ3σ2σ1εσ3σ2ε=σ3σ2σ1εσ3σ2σ1εσ3σ2ε,σ1εσ3σ2σ1εσ3σ2εσ3ε=εσ3σ2σ1εσ3σ2εσ3ε,(8)εσ3εσ3=εσ3ε,εσ3σ2εσ3σ2=εσ3σ2εσ3,εσ3σ2σ1εσ3σ2σ1=εσ3σ2σ1εσ3σ2,(9)σ2σ3σ2εσ3ε=σ3σ2εσ3ε,σ2σ3σ2σ1εσ3ε=σ3σ2σ1εσ3ε,σ2σ3σ2εσ3σ2ε=σ3σ2εσ3σ2ε,σ1σ2σ1σ3σ2εσ3ε=σ2σ1σ3σ2εσ3ε,σ2σ3σ2σ1εσ3σ2ε=σ3σ2σ1εσ3σ2ε,σ2σ3σ2εσ3σ2σ1ε=σ3σ2εσ3σ2σ1ε,σ1σ2σ1σ3σ2σ1εσ3ε=σ2σ1σ3σ2σ1εσ3ε,σ1σ2σ1σ3σ2εσ3σ2ε=σ2σ1σ3σ2εσ3σ2ε,σ2σ3σ2σ1εσ3σ2σ1ε=σ3σ2σ1εσ3σ2σ1ε,σ1σ2σ1σ3σ2σ1εσ3σ2ε=σ2σ1σ3σ2σ1εσ3σ2ε,σ1σ2σ1σ3σ2εσ3σ2σ1ε=σ2σ1σ3σ2εσ3σ2σ1ε,σ1σ2σ1σ3σ2σ1εσ3σ2σ1ε=σ2σ1σ3σ2σ1εσ3σ2σ1ε,(10)σ1σ2σ1εσ3σ2εσ3ε=σ2σ1εσ3σ2εσ3ε,σ1σ2σ1εσ3σ2σ1εσ3ε=σ2σ1εσ3σ2σ1εσ3ε,σ1σ2σ1εσ3σ2σ1εσ3σ2ε=σ2σ1εσ3σ2σ1εσ3σ2ε. $
|
The idea of Gröbner-Shirshov basis theory plays a significant role in several fields of mathematics (algebra, graph theory, knot theory), computer sciences (computational algebra) and information sciences. From algebraic way the method Gröbner-Shirshov basis theory gives a new algorithm to obtain normal forms of elements of groups, monoids, semigroups and various type of algebras, and hence a new algorithm to solve the word problem in these algebraic structures.
In this study, we obtained a Gröbner-Shirshov basis for a special type of braid monoids, namely the symmetric inverse monoid $ I_n $, in terms of the dex-leg ordering on the related elements of monoid. As known symmetric inverse monoids are partial bijections and they are very well known and important in combinatorics. By taking into account the Gröbner-Shirshov basis, we achieved the normal form structure of this important monoid. This normal form gave us the solution of the word problem. At the final part of this study, we presented an application of our main result which find out a Gröbner-Shirshov basis for the symmetric inverse monoid $ I_4 $ by using a package program, $ GBNP $, in GAP. Since $ GBNP $ is a restricted package program in point of size of symmetric inverse monoids it is worth to study and obtain a Gröbner-Shirshov basis for general size of this important structure.
In the future, the result of this work can be expanded to some other algebraic, computational structures and associated to graph theory, growth, Hilbert series and knot theory.
This work was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, under grant No (130-211-D1439). The authors, therefore, acknowledge with thanks DSR technical and financial support. The authors would like to thank to the referees for their suggestions and valuable comments.
The authors declare that they have no conflict of interest.
| [1] |
Kresge CT, Leonowicz ME, Roth WJ, et al. (1992) Ordered Mesoporous Molecular-Sieves Synthesized by a Liquid-Crystal Template Mechanism. Nature 359: 710-712. doi: 10.1038/359710a0
|
| [2] |
Moller K, Bein T (1998) Inclusion chemistry in periodic mesoporous hosts. Chem Mater 10:2950-2963. doi: 10.1021/cm980243e
|
| [3] |
Stein A, Melde BJ, Schroden RC (2000) Hybrid inorganic-organic mesoporous silicates - Nanoscopic reactors coming of age. Adv Mater 12: 1403-1419. doi: 10.1002/1521-4095(200010)12:19<1403::AID-ADMA1403>3.0.CO;2-X
|
| [4] | Asefa T, MacLachlan MJ, Coombs N, et al. (1999) Periodic mesoporous organosilicas with organic groups inside the channel walls. Nature 402: 867-871. |
| [5] |
Inagaki S, Guan S, Fukushima Y, et al. (1999) Novel mesoporous materials with a uniform distribution of organic groups and inorganic oxide in their frameworks. J Am Chem Soc 121:9611-9614. doi: 10.1021/ja9916658
|
| [6] |
Melde BJ, Holland BT, Blanford CF, et al. (1999) Mesoporous sieves with unified hybrid inorganic/organic frameworks. Chem Mater 11: 3302-3308. doi: 10.1021/cm9903935
|
| [7] |
Esquivel D, van den Berg O, Romero-Salguero FJ, et al. (2013) 100% thiol-functionalized ethylene PMOs prepared by "thiolacid-ene" chemistry. Chem Commun 49: 2344-2346. doi: 10.1039/c3cc39074h
|
| [8] |
Garcia RA, van Grieken R, Iglesias J, et al. (2010) Facile one-pot approach to the synthesis of chiral periodic mesoporous organosilicas SBA-15-type materials. J Catal 274: 221-227. doi: 10.1016/j.jcat.2010.07.003
|
| [9] |
Kuschel A, Luka M, Wessig M, et al. (2010) Organic Ligands Made Porous: Magnetic and Catalytic Properties of Transition Metals Coordinated to the Surfaces of Mesoporous Organosilica. Adv Funct Mater 20: 1133-1143. doi: 10.1002/adfm.200902056
|
| [10] |
Waki M, Mizoshita N, Tani T, et al. (2011) Periodic Mesoporous Organosilica Derivatives Bearing a High Density of Metal Complexes on Pore Surfaces. Angew Chem Int Edit 50: 11667-11671. doi: 10.1002/anie.201104063
|
| [11] |
Esquivel D, Jimenez-Sanchidrian C, Romero-Salguero FJ (2011) Comparison of the thermal and hydrothermal stabilities of ethylene, ethylidene, phenylene and biphenylene bridged periodic mesoporous organosilicas. Mater Lett 65: 1460-1462. doi: 10.1016/j.matlet.2011.02.037
|
| [12] |
Lopez MI, Esquivel D, Jimenez-Sanchidrian C, et al. (2013) Application of Sulfonic Acid Functionalised Hybrid Silicas Obtained by Oxidative Cleavage of Tetrasulfide Bridges as Catalysts in Esterification Reactions. Chemcatchem 5: 1002-1010. doi: 10.1002/cctc.201200509
|
| [13] |
Zhang YP, Jin Y, Yu H, et al. (2010) Pore expansion of highly monodisperse phenylene-bridged organosilica spheres for chromatographic application. Talanta 81: 824-830. doi: 10.1016/j.talanta.2010.01.022
|
| [14] |
Goethals F, Ciofi I, Madia O, et al. (2012) Ultra-low-k cyclic carbon-bridged PMO films with a high chemical resistance. J Mater Chem 22: 8281-8286. doi: 10.1039/c2jm30312d
|
| [15] |
De Canck E, Lapeire L, De Clercq J, et al. (2010) New Ultrastable Mesoporous Adsorbent for the Removal of Mercury Ions. Langmuir 26: 10076-10083. doi: 10.1021/la100204d
|
| [16] |
Bornscheuer UT (2003) Immobilizing enzymes: How to create more suitable biocatalysts. Angew Chem Int Edit 42: 3336-3337. doi: 10.1002/anie.200301664
|
| [17] |
Fried DI, Brieler FJ, Froba M (2013) Designing Inorganic Porous Materials for Enzyme Adsorption and Applications in Biocatalysis. Chemcatchem 5: 862-884. doi: 10.1002/cctc.201200640
|
| [18] |
Davis ME (2002) Ordered porous materials for emerging applications. Nature 417: 813-821. doi: 10.1038/nature00785
|
| [19] |
Hartmann M (2005) Ordered mesoporous materials for bioadsorption and biocatalysis. Chem Mater 17: 4577-4593. doi: 10.1021/cm0485658
|
| [20] |
Hudson S, Magner E, Cooney J, et al. (2005) Methodology for the immobilization of enzymes onto mesoporous materials. J Phys Chem B 109: 19496-19506. doi: 10.1021/jp052102n
|
| [21] |
Qiao SZ, Yu CZ, Xing W, et al. (2005) Synthesis and bio-adsorptive properties of large-pore periodic mesoporous organosilica rods. Chem Mater 17: 6172-6176. doi: 10.1021/cm051735b
|
| [22] |
Qiao SZ, Djojoputro H, Hu QH, et al. (2006) Synthesis and lysozyme adsorption of rod-like large-pore periodic mesoporous organosilica. Prog Solid State Ch 34: 249-256. doi: 10.1016/j.progsolidstchem.2005.11.023
|
| [23] |
Bhattacharyya MS, Hiwale P, Piras M, et al. (2010) Lysozyme Adsorption and Release from Ordered Mesoporous Materials. J Phys Chem C 114: 19928-19934. doi: 10.1021/jp1078218
|
| [24] |
Park M, Park SS, Selvaraj M, et al. (2009) Hydrophobic mesoporous materials for immobilization of enzymes. Micropor Mesopor Mat 124: 76-83. doi: 10.1016/j.micromeso.2009.04.032
|
| [25] |
Park M, Park SS, Selvaraj M, et al. (2011) Hydrophobic periodic mesoporous organosilicas for the adsorption of cytochrome c. J Porous Mat 18: 217-223. doi: 10.1007/s10934-010-9373-5
|
| [26] |
Li CM, Liu J, Shi X, et al. (2007) Periodic mesoporous organosilicas with 1,4- diethylenebenzene in the mesoporous wall: Synthesis, characterization, and bioadsorption properties. J Phys Chem C 111: 10948-10954. doi: 10.1021/jp071093a
|
| [27] |
Zhu L, Liu XY, Chen T, et al. (2012) Functionalized periodic mesoporous organosilicas for selective adsorption of proteins. Appl Surf Sci 258: 7126-7134. doi: 10.1016/j.apsusc.2012.04.011
|
| [28] |
Shin JH, Park SS, Selvaraj M, et al. (2012) Adsorption of amino acids on periodic mesoporous organosilicas. J Porous Mater 19: 29-35. doi: 10.1007/s10934-010-9443-8
|
| [29] |
Wang XQ, Lu DN, Austin R, et al. (2007) Protein refolding assisted by periodic mesoporous organosilicas. Langmuir 23: 5735-5739. doi: 10.1021/la063507h
|
| [30] |
Wang PY, Zhao L, Wu R, et al. (2009) Phosphonic Acid Functionalized Periodic Mesoporous Organosilicas and Their Potential Applications in Selective Enrichment of Phosphopeptides. J Phys Chem C 113: 1359-1366. doi: 10.1021/jp8093534
|
| [31] |
Wan JJ, Qian K, Zhang J, et al. (2010) Functionalized Periodic Mesoporous Organosilicas for Enhanced and Selective Peptide Enrichment. Langmuir 26: 7444-7450. doi: 10.1021/la9041698
|
| [32] |
Qian K, Gu WY, Yuan P, et al. (2012) Enrichment and Detection of Peptides from Biological Systems Using Designed Periodic Mesoporous Organosilica Microspheres. Small 8: 231-236. doi: 10.1002/smll.201101770
|
| [33] | Qian K, Liu F, Yang J, et al. (2012) Pore size-optimized periodic mesoporous organosilicas for the enrichment of peptides and polymers. RSC Adv 3: 14466-14472. |
| [34] |
Gan JR, Zhu J, Yan GQ, et al. (2012) Periodic Mesoporous Organosilica as a Multifunctional Nanodevice for Large-Scale Characterization of Membrane Proteins. Anal Chem 84: 5809-5815. doi: 10.1021/ac301146a
|
| [35] |
Shakeri M, Kawakami K (2008) Effect of the structural chemical composition of mesoporous materials on the adsorption and activation of the Rhizopus oryzae lipase-catalyzed transesterification reaction in organic solvent. Catal Commun 10: 165-168. doi: 10.1016/j.catcom.2008.08.012
|
| [36] | Serra E, Diez E, Diaz I, et al. (2010) A comparative study of periodic mesoporous organosilica and different hydrophobic mesoporous silicas for lipase immobilization. Micropor Mesopor Mat132: 487-493. |
| [37] |
Mayoral A, Arenal R, Gascon V, et al. (2013) Designing Functionalized Mesoporous Materials for Enzyme Immobilization: Locating Enzymes by Using Advanced TEM Techniques. Chemcatchem 5: 903-909. doi: 10.1002/cctc.201200737
|
| [38] |
Zhou Z, Taylor RNK, Kullmann S, et al. (2011) Mesoporous Organosilicas With Large Cage- Like Pores for High Efficiency Immobilization of Enzymes. Adv Mater 23: 2627-2632. doi: 10.1002/adma.201004054
|
| [39] |
Zhou Z, Inayat A, Schwieger W, et al. (2012) Improved activity and stability of lipase immobilized in cage-like large pore mesoporous organosilicas. Micropor Mesopor Mat 154:133-141. doi: 10.1016/j.micromeso.2012.01.003
|
| [40] |
Na W, Wei Q, Lan JN, et al. (2010) Effective immobilization of enzyme in glycidoxypropylfunctionalized periodic mesoporous organosilicas (PMOs). Micropor Mesopor Mat 134: 72-78. doi: 10.1016/j.micromeso.2010.05.009
|
| [41] | Nohair B, Phan THT, Vu THN, et al. (2012) Hybrid Periodic Mesoporous Organosilicas (PMOSBA-16): A Support for Immobilization of D-Amino Acid Oxidase and Glutaryl-7-amino Cephalosporanic Acid Acylase Enzymes. J Phys Chem C 116: 10904-10912. |
| [42] |
Guan LY, Di B, Su MX, et al. (2013) Immobilization of beta-glucosidase on bifunctional periodic mesoporous organosilicas. Biotechnol Lett 35: 1323-1330. doi: 10.1007/s10529-013-1208-4
|
| [43] |
Hudson S, Cooney J, Hodnett BK, et al. (2007) Chloroperoxidase on periodic mesoporous organosilanes: Immobilization and reuse. Chem Mater 19: 2049-2055. doi: 10.1021/cm070180c
|
| [44] |
Lin N, Gao L, Chen Z, et al. (2011) Elevating enzyme activity through the immobilization of horseradish peroxidase onto periodic mesoporous organosilicas. New J Chem 35: 1867-1875. doi: 10.1039/c1nj20311h
|
| [45] |
Wan MM, Gao L, Chen Z, et al. (2012) Facile synthesis of new periodic mesoporous organosilica and its performance of immobilizing horseradish peroxidase. Micropor Mesopor Mat 155: 24-33. doi: 10.1016/j.micromeso.2012.01.014
|
| [46] |
Ye F, Guo HF, Zhang HJ, et al. (2010) Polymeric micelle-templated synthesis of hydroxyapatite hollow nanoparticles for a drug delivery system. Acta Biomat 6: 2212-2218. doi: 10.1016/j.actbio.2009.12.014
|
| [47] |
Hu XL, Yan LS, Xiao HH, et al. (2013) Application of microwave-assisted click chemistry in the preparation of functionalized copolymers for drug conjugation. J Appl Polym Sci 127: 3365-3373. doi: 10.1002/app.37662
|
| [48] |
Elia R, Newhide DR, Pedevillano PD, et al. (2013) Silk-hyaluronan-based composite hydrogels: A novel, securable vehicle for drug delivery. J Biomater Appl 27: 749-762. doi: 10.1177/0885328211424516
|
| [49] | Vallet-Regi M (2010) Nanostructured mesoporous silica matrices in nanomedicine. J Intern Med267: 22-43. |
| [50] |
Vallet-Regi M, Ruiz-Hernandez E (2011) Bioceramics: From Bone Regeneration to Cancer Nanomedicine. Adv Mater 23: 5177-5218. doi: 10.1002/adma.201101586
|
| [51] |
Vallet-Regi M, Colilla M, Gonzalez B (2011) Medical applications of organic-inorganic hybrid materials within the field of silica-based bioceramics. Chem Soc Rev 40: 596-607. doi: 10.1039/C0CS00025F
|
| [52] |
Lin CX, Qiao SZ, Yu CZ, et al. (2009) Periodic mesoporous silica and organosilica with controlled morphologies as carriers for drug release. Micropor Mesopor Mater 117: 213-219. doi: 10.1016/j.micromeso.2008.06.023
|
| [53] |
Kao HM, Chung CH, Saikia D, et al. (2012) Highly Carboxylic-Acid-Functionalized Ethane- Bridged Periodic Mesoporous Organosilicas: Synthesis, Characterization, and Adsorption Properties. Chem Asian J 7: 2111-2117. doi: 10.1002/asia.201200244
|
| [54] |
Wu HY, Shieh FK, Kao HM, et al. (2013) Synthesis, Bifunctionalization, and Remarkable Adsorption Performance of Benzene-Bridged Periodic Mesoporous Organosilicas Functionalized with High Loadings of Carboxylic Acids. Chem Eur J 19: 6358-6367. doi: 10.1002/chem.201204400
|
| [55] |
Parambadath S, Rana VK, Zhao DY, et al. (2011) N,N '-diureylenepiperazine-bridged periodic mesoporous organosilica for controlled drug delivery. Micropor Mesopor Mater 141: 94-101. doi: 10.1016/j.micromeso.2010.10.051
|
| [56] | Parambadath S, Rana VK, Moorthy S, et al. (2011) Periodic mesoporous organosilicas with coexistence of diurea and sulfanilamide as an effective drug delivery carrier. J Solid State Chem184: 1208-1215. |
| [57] |
Moorthy MS, Park SS, Fuping D, et al. (2012) Step-up synthesis of amidoxime-functionalised periodic mesoporous organosilicas with an amphoteric ligand in the framework for drug delivery. J Mater Chem 22: 9100-9108. doi: 10.1039/c2jm16341a
|
| [58] |
Djojoputro H, Zhou XF, Qiao SZ, et al. (2006) Periodic mesoporous organosilica hollow spheres with tunable wall thickness. J Am Chem Soc 128: 6320-6321. doi: 10.1021/ja0607537
|
| [59] |
El Haskouri J, de Zarate DO, Guillem C, et al. (2002) Hierarchical porous nanosized organosilicas. Chem Mater 14: 4502-4504. doi: 10.1021/cm025650b
|
| [60] |
Cho EB, Kim D, Jaroniec M (2009) Preparation of mesoporous benzene-silica nanoparticles. Micropor Mesopor Mater 120: 252-256. doi: 10.1016/j.micromeso.2008.11.011
|
| [61] |
Li J, Wei Y, Deng YH, et al. (2010) An unusual example of morphology controlled periodic mesoporous organosilica single crystals. J Mater Chem 20: 6460-6463. doi: 10.1039/c0jm00663g
|
| [62] |
Urata C, Yamada H, Wakabayashi R, et al. (2011) Aqueous Colloidal Mesoporous Nanoparticles with Ethenylene-Bridged Silsesquioxane Frameworks. J Am Chem Soc 133: 8102-8105. doi: 10.1021/ja201779d
|
| [63] |
Guan BY, Cui Y, Ren ZY, et al. (2012) Highly ordered periodic mesoporous organosilica nanoparticles with controllable pore structures. Nanoscale 4: 6588-6596. doi: 10.1039/c2nr31662e
|
| [64] | Moorthy MS, Kim MJ, Bae JH, et al. (2013) Multifunctional Periodic Mesoporous Organosilicas for Biomolecule Recognition, Biomedical Applications in Cancer Therapy, and Metal Adsorption. Eur J Inorg Chem: 3028-3038. |
Dolores Esquivel, Pascal Van Der Voort, Francisco J. Romero-Salguero. Designing advanced functional periodic mesoporous organosilicas for biomedical applications[J]. AIMS Materials Science, 2014, 1(1): 70-86. doi: 10.3934/matersci.2014.1.70
DownLoad: