Eleventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1996)

Paper: Solving linear equations over polynomial semirings (at LICS 1996)

Authors: Paliath Narendran


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.


    author = 	 {Paliath Narendran},
    title = 	 {Solving linear equations over polynomial semirings},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {466-472},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}