Anti-unification and the theory of semirings

Authors: David M. Cerna
Publication year: 2020
Publication type: Článek v odborném periodiku
Periodical: Theoretical Computer Science
Bibliographic citation: CERNA, David M. Anti-unification and the theory of semirings. Theoretical Computer Science. 2020, 848(December 2020), 133-139. ISSN 0304-3975. E-ISSN 1879-2294
Dostupné z: doi:10.1016/j.tcs.2020.10.020.
DOI: 10.1016/j.tcs.2020.10.020
ID: 534054
Online record: View online record

Abstract

It was recently shown that anti-unification over an equational theory consisting of only unit equations (more than one) is nullary. Such pure theories are artificial and are of little effect on practical aspects of anti-unification. In this work, we extend these nullarity results to the theory of semirings, a heavily studied theory with many practical applications. Furthermore, our argument holds over semirings with commutative multiplication and/or idempotent addition. We also cover a few open questions discussed in previous work.