Anti-unification and the Theory of Semirings

David Cerna

doi:10.1016/j.tcs.2020.10.020

Anti-unification and the Theory of Semirings

David Cerna

Research Institute for Symbolic Computation

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	133-139
Number of pages	7
Journal	Theoretical Computer Science
Volume	848
DOIs	https://doi.org/10.1016/j.tcs.2020.10.020
Publication status	Published - 24 Dec 2020

Fields of science

101 Mathematics
101001 Algebra
101005 Computer algebra
101009 Geometry
101012 Combinatorics
101013 Mathematical logic
101020 Technical mathematics

JKU Focus areas

Digital Transformation

Access to Document

10.1016/j.tcs.2020.10.020

Cite this

@article{b8b97febb46a4a51bb5e2f1cadfc38b2,

title = "Anti-unification and the Theory of Semirings",

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.",

author = "David Cerna",

year = "2020",

month = dec,

day = "24",

doi = "10.1016/j.tcs.2020.10.020",

language = "English",

volume = "848",

pages = "133--139",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Anti-unification and the Theory of Semirings

AU - Cerna, David

PY - 2020/12/24

Y1 - 2020/12/24

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

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

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

U2 - 10.1016/j.tcs.2020.10.020

DO - 10.1016/j.tcs.2020.10.020

M3 - Article

SN - 0304-3975

VL - 848

SP - 133

EP - 139

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Anti-unification and the Theory of Semirings

Abstract

Fields of science

JKU Focus areas

Access to Document

Other files and links

Cite this