We consider the problem of solving linear equations over various semirings. In particular, solving of linear equations over polynomial rings with the additional restriction that the solutions must have only non-negative coefficients is shown to be undecidable. Applications to undecidability proofs of several unification problems are illustrated, one of which, unification modulo one associative-commutative function and one endomorphism, has been a long-standing open problem. The problem of solving multiset constraints is also shown to be undecidable.
['Paliath Narendran']
Solving linear equations over polynomial semirings