COMMUTATIVITY IN FREE INVERSE MONOIDS

Citation
C. Choffrut et F. Dalessandro, COMMUTATIVITY IN FREE INVERSE MONOIDS, Theoretical computer science, 204(1-2), 1998, pp. 35-54
Citations number
17
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
ISSN journal
03043975
Volume
204
Issue
1-2
Year of publication
1998
Pages
35 - 54
Database
ISI
SICI code
0304-3975(1998)204:1-2<35:CIFIM>2.0.ZU;2-B
Abstract
This article characterizes the solutions of the commutativity equation xy = yx in free inverse monoids. The main result implies the followin g interesting property that is the natural generalization to free inve rse monoids of the solutions of the same equation in free monoids. Let x and y be non-idempotent elements of a free inverse monoid such that xy = yx. Then there exist some elements chi and z such that x and y a re conjugate by chi to some positive powers of z, namely x chi = chi z (n) and y chi = chi z(m), with n, m greater than or equal to 1. We als o show that the centralizer of a given non-idempotent element is a rat ional, non-recognizable subset of the free inverse monoid. (C) 1998-El sevier Science B.V. All rights reserved.