Ph.D Thesis
Ph.D Student Fabienne Chouraqui Decision Problems in Tableau-Groups and Tableau-Semigroups Department of Mathematics Professor Juhasz Arie

Abstract

This work is about decision problems in some class of groups and monoids. We define a tableau-group (semigroup) to be a finitely presented group (semigroup) such that all the defining relations have positive words of length two on both sides of the equality . There is a lot of examples of such groups: Knot and link groups with the Wirtinger presentation, right-angled Artin groups, LOG groups (Labeled Oriented Graph), structure groups of set-theoretical solutions of the quantum Yang-Baxter equation and others . The class of tableau-groups or semigroups is closed under free, direct and graph product. Our research considers some subclasses of tableau-groups and monoids and we study their algorithmic and algebraic properties .

We establish a one-to-one correspondence between the structure groups of non degenerate, involutive and braided set-theoretical solutions of the quantum Yang-Baxter equation and a class of Garside tableau groups that satisfies certain conditions . Our approach is combinatorial and we use the tools developed by Dehornoy in the theory of Garside groups . We study the conjugacy problem in semigroups and monoids. There are several notions: the transposition problem, the left (right) conjugacy problem and the left and right conjugacy problem . The main idea in our proof can be described as follows . Let M  be a finitely presented monoid generated by Σ and let be a complete rewriting system for M .   Let u be a word in Σ*, the free monoid generated by Σ.  We consider u and all its cyclic conjugates in Σ* ,   u1=u, u2,.., uk and we apply on each element ui rules from . We say that u is cyclically irreducible if u and all its cyclic conjugates are irreducible modulo . If for some i, 1 i n, ui   reduces to v, then we say that u cyclically reduces to v. A question that arises naturally is when u and all its cyclic conjugates cyclically reduce to the same cyclically irreducible element (up to cyclic conjugation in Σ*), denoted by ρ(u). We find, given a word u in Σ*, a criteria that ensures the existence of a unique cyclically irreducible element ρ(u) . Moreover, the answer to this question gives a partial solution to the conjugacy problems presented above in the following way: if u and v are transposed, then ρ(u) and ρ(v) are cyclic conjugates in Σ* and this implies in turn that  u and v are left and right conjugates .