License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.133
URN: urn:nbn:de:0030-drops-142022
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14202/
Go to the corresponding LIPIcs Volume Portal

Grädel, Erich ; Mrkonjić, Lovro

Elementary Equivalence Versus Isomorphism in Semiring Semantics

pdf-format:
LIPIcs-ICALP-2021-133.pdf (0.8 MB)

Abstract

We study the first-order axiomatisability of finite semiring interpretations or, equivalently, the question whether elementary equivalence and isomorphism coincide for valuations of atomic facts over a finite universe into a commutative semiring. Contrary to the classical case of Boolean semantics, where every finite structure is axiomatised up to isomorphism by a first-order sentence, the situation in semiring semantics is rather different, and depends on the underlying semiring. We prove that for a number of important semirings, including min-max semirings, and the semirings of positive Boolean expressions, there exist finite semiring interpretations that are elementarily equivalent but not isomorphic. The same is true for the polynomial semirings that are universal for the classes of absorptive, idempotent, and fully idempotent semirings, respectively. On the other side, we prove that for other, practically relevant, semirings such as the Viterby semiring ?, the tropical semiring ?, the natural semiring ℕ and the universal polynomial semiring ℕ[X], all finite semiring interpretations are first-order axiomatisable, and thus elementary equivalence implies isomorphism.

BibTeX - Entry

@InProceedings{gradel_et_al:LIPIcs.ICALP.2021.133,
  author =	{Gr\"{a}del, Erich and Mrkonji\'{c}, Lovro},
  title =	{{Elementary Equivalence Versus Isomorphism in Semiring Semantics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{133:1--133:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14202},
  URN =		{urn:nbn:de:0030-drops-142022},
  doi =		{10.4230/LIPIcs.ICALP.2021.133},
  annote =	{Keywords: Semiring semantics, elementary equivalence, axiomatisability}
}

Keywords: Semiring semantics, elementary equivalence, axiomatisability
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI