Théorèmes de transfert pour les polynômes partiellement commutatifs. (Transfer theorems for partially commutative polynomials)
type: Item
instance of: scholarly article
title: Théorèmes de transfert pour les polynômes partiellement commutatifs. (Transfer theorems for partially commutative polynomials)
zbMATH Open document ID: 0662.16022
DOI: 10.1016/0304-3975(88)90041-2
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: A semiring \(K=(K,+,\cdot)\) [such that \((K,+)\) is commutative and has a neutral 0 satisfying \(0x=x0=0\) for all \(x\in K]\) is called multiplicatively left cancellative if \(x\neq 0\) and \(xy=xz\) imply \(y=z\), and called zero divisor free if \(xy=0\) implies \(x=0\) or \(y=0\), both for all x,y,z\(\in K\). Let X be a [not necessarily finite] alphabet, \(\vartheta\) \(\subseteq X\times X\) a relation on X and \(\equiv_{\vartheta}\) the congruence on the free monoid \(X^*\) generated by (ab,ba) for all (a,b)\(\in \vartheta\). Then \(X^*/\equiv_{\vartheta}\) is called the free partially commutative monoid M(X,\(\vartheta)\). Denote by \(K<M,\vartheta >\) the semigroup semiring of M(X,\(\vartheta)\) over a semiring K, i.e. the set of all mappings of M(X,\(\vartheta)\) into K with finite support, established with pointwise addition and the product of convolution. The main part of this paper is devoted to prove the following theorem: \(K<M,\vartheta >\) is zero divisor free iff K is; \(K<M,\vartheta >\) is additively cancellative and multiplicatively left cancellative iff K has the same properties. Moreover, an algorithm is given which tests the divisibility of elements of \(K<M,\vartheta >\), and computes the quotient in the case of a positive answer. [Remarks: 1) In a forthcoming paper the referee will show that the above theorem also holds for the semiring \(K<<M,\vartheta >>\) of all mappings of M(X,\(\vartheta)\) into K. 2) There are various meanings of the term ``semiring'' in the literature, and an ``alphabet'' is sometimes assumed to be finite, and sometimes not. A few words about the meaning of those terms spare the trouble for the reader to find that out as a puzzle.]
Mathematics Subject Classification ID: 16Y60
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 16W60
Mathematics Subject Classification ID: 20M25
Mathematics Subject Classification ID: 20M15
zbMATH DE Number: 4081771
zbMATH Keywords: semirings of polynomials in partially commuting indeterminates
zbMATH Keywords: multiplicatively left cancellative semirings
zbMATH Keywords: zero divisor free
zbMATH Keywords: alphabet
zbMATH Keywords: congruence
zbMATH Keywords: free monoid
zbMATH Keywords: semigroup semiring
zbMATH Keywords: additively cancellative
zbMATH Keywords: divisibility of elements
author: G. H. E Duchamp
author: Jean-Yves Thibon
reviewed by: Hanns Joachim Weinert
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90041-2
OpenAlex ID: W1971905014
cites work: Combinatorial problems of commutation and rearrangements
cites work: Q5571530
cites work: Q3853827
cites work: Integrité des algèbres de séries formelles sur un alphabet partiellement commutatif
cites work: Q3736919
description: scientific article; zbMATH DE number 4081771