Equational theories of tropical semirings

Luca Aceto*, Zoltán Ésik, Anna Ingólfsdóttir

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

6 Citations (Scopus)

Abstract

This paper studies the equational theories of various exotic semirings presented in the literature. Exotic semirings are semirings whose underlying carrier set is some subset of the set of real numbers equipped with binary operations of minimum or maximum as sum, and addition as product. Two prime examples of such structures are the (max,+) semiring and the tropical semiring. It is shown that none of the exotic semirings commonly considered in the literature has a finite basis for its equations, and that similar results hold for the commutative idempotent weak semirings that underlie them. For each of these commutative idempotent weak semirings, the paper offers characterizations of the equations that hold in them, decidability results for their equational theories, explicit descriptions of the free algebras in the varieties they generate, and relative axiomatization results.

Original languageEnglish
Pages (from-to)417-469
Number of pages53
JournalTheoretical Computer Science
Volume298
Issue number3
DOIs
Publication statusPublished - 11 Apr 2003
EventFoundations of Software Science and Computation Structures - Genova, Italy
Duration: 2 Apr 20014 Apr 2001

Bibliographical note

Funding Information:
∗Corresponding author. E-mail addresses: luca@cs.auc.dk (L. Aceto), ze@inf.u-szeged.hu (Z. Esik),* annai@cs.auc.dk (A. Ingo*lfsdo*ttir). URLs: http://www.cs.auc.dk/∼luca, http://www.cs.auc.dk/∼annai 1Partially supported by BRICS and research grant no. T30511 from the National Foundation of Hungary for Scienti2c Research. This work was partly carried out while this author was visiting professor at the Department of Computer Science, Aalborg University.

Other keywords

  • Commutative idempotent weak semirings
  • Complete axiomatizations
  • Convexity
  • Equational logic
  • Exponential time complexity
  • Relative axiomatizations
  • Tropical semirings
  • Varieties

Fingerprint

Dive into the research topics of 'Equational theories of tropical semirings'. Together they form a unique fingerprint.

Cite this