Solving linear equations over polynomial semirings

Paliath Narendran

Solving linear equations over polynomial semirings

Paliath Narendran

Computer Science

University at Albany

Research output: Contribution to journal › Conference article › peer-review

22 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	466-472
Number of pages	7
Journal	Proceedings - Symposium on Logic in Computer Science
State	Published - 1996
Event	Proceedings of the 1996 11th Annual IEEE Symposium on Logic in Computer Science, LICS'96 - New Brunswick, NJ, USA Duration: Jul 27 1996 → Jul 30 1996

Cite this

@article{8319d74006e745d6b1a77f6653f39c4e,

title = "Solving linear equations over polynomial semirings",

abstract = "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",

year = "1996",

language = "English",

pages = "466--472",

journal = "Proceedings - Symposium on Logic in Computer Science",

issn = "1043-6871",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the 1996 11th Annual IEEE Symposium on Logic in Computer Science, LICS'96 ; Conference date: 27-07-1996 Through 30-07-1996",

}

TY - JOUR

T1 - Solving linear equations over polynomial semirings

AU - Narendran, Paliath

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0029714151

M3 - Conference article

SN - 1043-6871

SP - 466

EP - 472

JO - Proceedings - Symposium on Logic in Computer Science

JF - Proceedings - Symposium on Logic in Computer Science

T2 - Proceedings of the 1996 11th Annual IEEE Symposium on Logic in Computer Science, LICS'96

Y2 - 27 July 1996 through 30 July 1996

ER -

Solving linear equations over polynomial semirings

Abstract

Other files and links

Fingerprint

Cite this