ON POLYNOMIAL REWRITING OF SEMIRINGS

ABSTRACT: Introduced originally as a method for solving word problems, rewriting theory has developed into one of the most successful and general areas of symbolic computation. On the other hand, semirings have become an important tool in applied mathematics and theoretical computer science.

Thus it is of interest to develop rewriting systems for semirings, which would provide algorithmic solutions to various problems related to semirings.

Using admissible orderings, Madlener and Reinert have shown how congruences on monoids can be characterized by certain ideals in corresponding monoid rings, and established that the Knuth-Bendix completion procedure for a monoid (or group) presentation is closely related to the computation of Gr\"obner bases for certain restricted two-sided ideals in the corresponding free monoid (or group) ring.

In the present talk we discuss polynomial rewriting on semirings. Our method relies on a new version of Mal'cev lemma which describes congruences generated by relations on algebras (or, in another terminology, Thue congruences). Note that in the classical case of rings the proposed techniques give well-known results without requiring the initial ring to be a field.