arxiv: 2605.10829 · v1 · submitted 2026-05-11 · 💻 cs.LO

Recognition: 2 theorem links

· Lean Theorem

Preservation Theorems in Semiring Semantics

Sophie Brinke , Anuj Dawar , Erich Gr\"adel , Benedikt Pago

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:52 UTC · model grok-4.3

classification 💻 cs.LO

keywords preservation theoremssemiring semanticsŁoś-Tarski theoremhomomorphism preservationlattice semiringsfirst-order logicmodel theorydatabase provenance

0 comments

The pith

Preservation theorems from classical model theory hold for first-order logic over all lattice semirings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes that the Łoś-Tarski theorem on preservation under extensions and the homomorphism preservation theorem continue to hold in semiring semantics for first-order logic whenever the underlying semiring is a lattice semiring. Lattice semirings form a broad class that includes min-max semirings and other practically relevant structures used to track provenance, costs, or confidence in query evaluation. The proofs adapt classical compactness and amalgamation arguments together with reduction methods developed specifically for entailment questions in the semiring setting. For contrast, the existential preservation theorem fails over many non-lattice semirings such as the tropical, Viterbi, Łukasiewicz, and natural-number semirings, yet it holds when restricted to finite structures in a wider collection of semirings including all lattices. The results clarify which model-theoretic tools remain available once logic is lifted from the Boolean case to richer value domains.

Core claim

The preservation theorems do indeed hold for all lattice semirings. The proofs combine adaptations of the classical compactness and amalgamation methods with specific reduction methods for logical entailment that have been developed in semiring semantics. Variants of the existential preservation theorem fail for many other semirings, including the tropical semiring, the Viterbi semiring, the Łukasiewicz semiring, and the natural semiring. Surprisingly, the existential preservation theorem does hold for finite interpretations in a number of semirings, including all lattice semirings.

What carries the argument

lattice semirings, whose algebraic structure supports the adapted compactness and amalgamation arguments that recover classical preservation results from model theory

If this is right

A sentence preserved under extensions is equivalent to an existential sentence when interpreted over any lattice semiring.
A sentence preserved under homomorphisms is equivalent to an existential-positive sentence when interpreted over any lattice semiring.
The same equivalences apply to provenance tracking, cost computation, or confidence evaluation in database queries whenever the semiring is a lattice.
Existential preservation holds for all finite structures over every lattice semiring and over several additional semirings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Query optimizers that rely on provenance or cost lattices can safely apply classical syntactic simplifications that depend on preservation properties.
The divergence between the general and finite cases for non-lattice semirings raises the question of which preservation results survive when structures are required to be finite.
Similar adaptation techniques may extend preservation results to other logical languages or to semirings with additional algebraic structure beyond lattices.

Load-bearing premise

The definitions of semantic properties such as preservation under extensions, substructures, or homomorphisms naturally generalise to the setting of semiring semantics, and the algebraic properties of lattice semirings suffice for the adapted compactness and amalgamation arguments to go through.

What would settle it

A first-order sentence that is preserved under extensions over some lattice semiring yet is not equivalent to any existential sentence over that semiring.

read the original abstract

We study the status of preservation theorems such as the {\L}o\'s-Tarski theorem and the homomorphism preservation theorem in the context of semiring semantics. Semiring semantics has its origins in the provenance analysis of database queries. Depending on the underlying semiring, it allows us to track which atomic facts are responsible for the truth of a statement or practical information about the evaluation such as costs or confidence. The systematic development of semiring semantics for first-order logic and other logical systems raises the question to what extent classical model-theoretic results can be generalised to this setting and how such results depend on the underlying semiring. The definitions of semantic properties such as preservation under extensions, substructures, or homomorphisms naturally generalise to the setting of semiring semantics. However, the status of the corresponding preservation theorem strongly depends on the algebraic properties of the particular semirings. We prove that these preservation theorems do indeed hold for all lattice semirings (a quite large class, encompassing practically relevant semirings and in particular all min-max semirings). The proofs combine adaptations of the classical compactness and amalgamation methods with specific reduction methods for logical entailment that have been developed in semiring semantics. On the other side, variants of the existential preservation theorem fail for many other semirings, including the tropical semiring, the Viterbi semiring, the {\L}ukasiewicz semiring, and the natural semiring. Surprisingly, the existential preservation theorem does hold for finite interpretations in a number of semirings, including all lattice semirings. Thus, the situation for these semirings is in sharp contrast to the Boolean case, where the {\L}o\'s-Tarski theorem holds in general, but not in the finite.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows preservation theorems carry over to semiring semantics precisely for lattice semirings, with concrete failures for tropical, Viterbi and similar cases, plus a reversal on finite structures.

read the letter

This paper classifies when classical preservation theorems survive in semiring semantics. The central result is that Łoś-Tarski, homomorphism preservation, and existential preservation all hold for every lattice semiring, including the min-max family that shows up in practice. The proofs adapt compactness and amalgamation in a semiring-aware way and use existing reduction techniques for entailment. On the negative side, the same theorems fail for the tropical semiring, the Viterbi semiring, the Łukasiewicz semiring, and the natural numbers semiring, with explicit counterexamples supplied. The finite-model behavior flips: existential preservation holds for finite interpretations over lattice semirings, in contrast to the Boolean case where it fails finitely but holds in general. That contrast is the most striking part of the work. The algebraic distinction is new; earlier semiring-semantics papers did not isolate the lattice condition or produce these specific counterexamples. The arguments rest on standard model-theoretic tools plus reductions already in the literature, so there is no circularity or invented machinery. The counterexample constructions and the finite-model proofs are the parts that would need the closest check in a full reading, but the abstract and stress-test give no sign of load-bearing gaps. The paper is aimed at model theorists who already know semiring provenance and at database researchers who use these semirings for query tracking or cost analysis. Anyone working on generalized semantics or on practical provenance systems will get immediate value from the classification. It is worth sending to peer review; the results are specific, the methods are standard, and the finite-model reversal is worth having on record even if the proofs require minor polishing.

Referee Report

0 major / 3 minor

Summary. The paper examines the status of classical preservation theorems (Łoś-Tarski, homomorphism preservation, and existential preservation) when first-order logic is interpreted over semiring semantics. It shows that the theorems hold for the broad class of lattice semirings by adapting compactness and amalgamation arguments together with existing semiring-specific reduction techniques for entailment; explicit counterexamples are given for the tropical, Viterbi, Łukasiewicz, and natural semirings. The paper further establishes that existential preservation holds over finite interpretations for all lattice semirings, in contrast to the Boolean case where the Łoś-Tarski theorem fails in the finite.

Significance. If the claimed proofs and counterexamples are correct, the work supplies a precise algebraic demarcation (lattice vs. non-lattice semirings) under which model-theoretic preservation results survive in the provenance setting. This is valuable both for database theory and for the systematic study of generalized semantics. The combination of adapted compactness/amalgamation with semiring reduction methods, together with the finite-model positive results, constitutes a substantive contribution that clarifies the boundary between classical and semiring model theory.

minor comments (3)

The abstract and introduction refer to 'adaptations of the classical compactness and amalgamation methods' without indicating the precise section where the adapted compactness theorem for lattice semirings is stated and proved; a forward reference would help readers locate the technical core.
Notation for semiring operations (addition, multiplication, zero, one) is introduced early but occasionally reused with different fonts in later sections; consistent use of a single macro or font throughout would improve readability.
The counterexample constructions for the tropical and Viterbi semirings are described at a high level; adding a short table summarizing the key algebraic properties that cause the failure (e.g., lack of idempotence or distributivity) would make the contrast with lattice semirings sharper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary correctly captures the main results on preservation theorems for lattice semirings and the counterexamples for non-lattice semirings, as well as the finite-model existential preservation result.

Circularity Check

0 steps flagged

No significant circularity; standard model-theoretic tools plus prior independent reductions

full rationale

The paper adapts classical compactness and amalgamation arguments to lattice semirings and invokes reduction methods for entailment developed in the semiring-semantics literature. These are external, previously published techniques rather than self-referential definitions or fitted parameters renamed as predictions. No equation or theorem in the derivation reduces by construction to the target preservation statement itself. Minor self-citations to semiring-semantics foundations exist but are not load-bearing for the central claims, which remain independently verifiable via the algebraic properties of lattice semirings and standard first-order model theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard compactness theorem of first-order logic, the existence of amalgamations in model theory, and the algebraic definition of lattice semirings; no new free parameters or postulated entities are introduced.

axioms (2)

standard math Compactness theorem for first-order logic
Invoked in the adaptation of classical proofs to semiring semantics.
standard math Amalgamation property for models
Used together with compactness in the lattice-semiring case.

pith-pipeline@v0.9.0 · 5622 in / 1562 out tokens · 102405 ms · 2026-05-12T03:52:18.527305+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that these preservation theorems do indeed hold for all lattice semirings (a quite large class, encompassing practically relevant semirings and in particular all min-max semirings).
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The proofs combine adaptations of the classical compactness and amalgamation methods with specific reduction methods for logical entailment that have been developed in semiring semantics.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

146 extracted references · 146 canonical work pages

[1]

Abiteboul and R

S. Abiteboul and R. Hull and V.Vianu , title =

work page
[2]

Amer , title =

K. Amer , title =. Alg. Universalis , volume =

work page
[3]

Amsterdamer and S

Y. Amsterdamer and S. Davidson and D. Deutch and T. Milo and J. Stoyanovich and V Tannen , title =

work page
[4]

CoRR , volume =

Dawar, Anuj and Pago, Benedikt and Seppelt, Tim , title =. CoRR , volume =. 2025 , doi =

work page 2025
[5]

, year =

Stanley, Richard P. , year =. Enumerative combinatorics , isbn =

work page
[6]

Large networks and graph limits , isbn =

Lovász, László , year =. Large networks and graph limits , isbn =

work page
[7]

and Deutch, D

Amsterdamer, Y. and Deutch, D. and Tannen, V. On the Limitations of Provenance for Queries with Difference. 3rd Workshop on the Theory and Practice of Provenance, TaPP'11. 2011

work page 2011
[8]

and Deutch, D

Amsterdamer, Y. and Deutch, D. and Tannen, V. Provenance for aggregate queries. Principles of Database Systems, PODS. 2011

work page 2011
[9]

and van Benthem, J

Andr\'eka, H. and van Benthem, J. and N\'emeti, I. Modal Languages and Bounded Fragments of Predicate Logic. Journal of Philosophical Logic. 1998. doi:10.1023/A:1004275029985

work page doi:10.1023/a:1004275029985 1998
[10]

Lectures in Game Theory for Computer Scientists. 2011. doi:10.1017/CBO9780511973468

work page doi:10.1017/cbo9780511973468 2011
[11]

and Barcel \' o , P

Arenas, M. and Barcel \' o , P. and Libkin, L. Game-based notions of locality over finite models. Ann. Pure Appl. Log. 2008. doi:10.1016/j.apal.2007.11.012

work page doi:10.1016/j.apal.2007.11.012 2008
[12]

Atserias and P

A. Atserias and P. Kolaitis , title =. Samson Abramsky on Logic and Structure in Computer Science and Beyond, volume 25 of Outstanding Contributions to Logic , editor =

work page
[13]

Atserias and P

A. Atserias and P. Kolaitis , title =. Proc. 2024 , doi =

work page 2024
[14]

2025 , journal =

Codd's Theorem for Databases over Semirings , author=. 2025 , journal =

work page 2025
[15]

Badia and V

G. Badia and V. Costa and P. Dellunde and C. Noguera , title =. Soft Comput. , volume =. 2019 , doi =

work page 2019
[16]

and D\' az, J

Balc\'azar, J. and D\' az, J. and Gabarr\'o, J. Structural Complexity II. 1990. doi:10.1007/978-3-642-75357-2

work page doi:10.1007/978-3-642-75357-2 1990
[17]

and ten Cate , B

B\' a r\' a ny, V. and ten Cate , B. and Segoufin, L. Guarded Negation. J. ACM. 2015. doi:10.1145/2701414

work page doi:10.1145/2701414 2015
[18]

and Gottlob, G

B\' a r\' a ny, V. and Gottlob, G. and Otto, M. Querying the Guarded Fragment. Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer Science. 2010. doi:10.1109/LICS.2010.26

work page doi:10.1109/lics.2010.26 2010
[19]

and Bourhis, P

Benedikt, M. and Bourhis, P. and Vanden Boom , M. Characterizing Definability in Decidable Fixpoint Logics. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. 2017. doi:10.4230/LIPIcs.ICALP.2017.107

work page doi:10.4230/lipics.icalp.2017.107 2017
[20]

and ten Cate , B

Benedikt, M. and ten Cate , B. and Vanden Boom , M. Effective Interpolation and Preservation in Guarded Logics. ACM Trans. Comput. Log. 2016. doi:10.1145/2814570

work page doi:10.1145/2814570 2016
[21]

and Griffin, T

Benedikt, M. and Griffin, T. and Libkin, L. Verifiable Properties of Database Transactions. Inf. Comput. 1998. doi:10.1006/inco.1998.2731

work page doi:10.1006/inco.1998.2731 1998
[22]

Bergerem, S. van. Learning Concepts Definable in First-Order Logic with Counting. 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019. 2019. doi:10.1109/LICS.2019.8785811

work page doi:10.1109/lics.2019.8785811 2019
[23]

van and Grohe, M

Bergerem, S. van and Grohe, M. and Ritzert, M. On the Parameterized Complexity of Learning First-Order Logic. PODS '22: International Conference on Management of Data. 2022. doi:10.1145/3517804.3524151

work page doi:10.1145/3517804.3524151 2022
[24]

van and Schweikardt, N

Bergerem, S. van and Schweikardt, N. Learning Concepts Described By Weight Aggregation Logic. 29th EACSL Annual Conference on Computer Science Logic, CSL 2021. 2021. doi:10.4230/LIPIcs.CSL.2021.10

work page doi:10.4230/lipics.csl.2021.10 2021
[25]

Bosbach , title =

B. Bosbach , title =. Math. Ann. , volume =

work page
[26]

and Gr\"

Brinke, S. and Gr\". 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.CSL.2024.19 , annote =

work page doi:10.4230/lipics.csl.2024.19 2024
[27]

and Dawar, A

Brinke, S. and Dawar, A. and Gr\". 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) , pages =. 2026 , volume =. doi:10.4230/LIPIcs.CSL.2026.13 , annote =

work page doi:10.4230/lipics.csl.2026.13 2026
[28]

Locality Theorems in Semiring Semantics

Bizi. Locality Theorems in Semiring Semantics. 2023. arXiv:2303.12627

work page arXiv 2023
[29]

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) , pages =

Bizi\`. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.MFCS.2023.20 , annote =

work page doi:10.4230/lipics.mfcs.2023.20 2023
[30]

and de Rijke , M

Blackburn, P. and de Rijke , M. and Venema, Y. Modal Logic. 2001. doi:10.1017/CBO9781107050884

work page doi:10.1017/cbo9781107050884 2001
[31]

and Gurevich, Y

Blass, A. and Gurevich, Y. Strong extension axioms and S helah's zero-one law for choiceless polynomial time. Journal of Symbolic Logic. 2003. doi:10.2178/jsl/1045861507

work page doi:10.2178/jsl/1045861507 2003
[32]

and Ozaki, A

Bourgaux, C. and Ozaki, A. and Pe \ n aloza, R. and Predoiu, L. Provenance for the Description Logic ELHr. Proceedings of IJCAI 2020. 2020. doi:10.24963/ijcai.2020/258

work page doi:10.24963/ijcai.2020/258 2020
[33]

and Walukiewicz, I

Bradfield, J. and Walukiewicz, I. The mu-calculus and model checking. Handbook of Model Checking. 2018. doi:10.1007/978-3-319-10575-8_26

work page doi:10.1007/978-3-319-10575-8_26 2018
[34]

Ehrenfeucht-Fra

Brinke, S. Ehrenfeucht-Fra. 2023

work page 2023
[35]

Brinke, S. and Gr. The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen , pages =. 2024 , volume =

work page 2024
[36]

Canavoi, F. and Gr. Defining winning strategies in fixed-point logic. 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 2015. doi:10.1109/LICS.2015.42

work page doi:10.1109/lics.2015.42 2015
[37]

ACM Transactions on Computational Logic , year=

Homomorphism Preservation Theorems for Many-Valued Structures , author=. ACM Transactions on Computational Logic , year=

work page
[38]

and Seara, C

Castro, J. and Seara, C. Complexity classes between _k^P and _k^P. RAIRO - Theoretical Informatics and Applications - Informatique Th\' e orique et Applications. 1996

work page 1996
[39]

and Dvor \' a k, W

Chatterjee, K. and Dvor \' a k, W. and Henzinger, M. and Loitzenbauer, V. Conditionally Optimal Algorithms for Generalized. 2016

work page 2016
[40]

Chatterjee and M

Chatterjee, K. and Henzinger, M. Efficient and Dynamic Algorithms for Alternating. J. ACM. 2014. doi:10.1145/2597631

work page doi:10.1145/2597631 2014
[41]

and Henzinger, T

Chatterjee, K. and Henzinger, T. and Piterman, N. Algorithms for. 2008

work page 2008
[42]

and Navara, M

Cintula, P. and Navara, M. Compactness of fuzzy logics , journal =. 2004 , url =. doi:10.1016/J.FSS.2003.06.002 , timestamp =

work page doi:10.1016/j.fss.2003.06.002 2004
[43]

0-1 laws in logic and combinatorics

Compton, K. 0-1 laws in logic and combinatorics. N A T O Advanced Study Institute on Algorithms and Order. 1998. doi:10.1007/978-94-009-2639-4_10

work page doi:10.1007/978-94-009-2639-4_10 1998
[44]

and Gr\"

Dannert, K. and Gr\". Provenance Analysis: A Perspective for Description Logics?. Description Logic, Theory Combination, and All That. 2019. doi:10.1007/978-3-030-22102-7_12

work page doi:10.1007/978-3-030-22102-7_12 2019
[45]

and Gr\"

Dannert, K. and Gr\". Semiring Provenance for guarded logics. Hajnal Andr \'e ka and Istv \'a n N \'e meti on Unity of Science: From Computing to Relativity Theory through Algebraic Logic. 2020. doi:10.1007/978-3-030-64187-0_3

work page doi:10.1007/978-3-030-64187-0_3 2020
[46]

Dannert, K. and Gr. Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic. 2019

work page 2019
[47]

Dannert, K. and Gr. Semiring Provenance for Fixed-Point Logic. 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). 2021. doi:10.4230/LIPIcs.CSL.2021.17

work page doi:10.4230/lipics.csl.2021.17 2021
[48]

and Grohe, M

Dawar, A. and Grohe, M. and Kreutzer, S. and Schweikardt, N. Approximation Schemes for First-Order Definable Optimisation Problems. 21th IEEE Symposium on Logic in Computer Science ( LICS 2006). 2006. doi:10.1109/LICS.2006.13

work page doi:10.1109/lics.2006.13 2006
[49]

Dawar and A

A. Dawar and A. Sankaran , title =. 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) , pages =. 2021 , doi =

work page 2021
[50]

Dellunde and A

P. Dellunde and A. Vidal , title =. International Journal of Uncertainty, Fuzzyness, and Knowledge-Based Systems , volume =

work page
[51]

Deutch and Y

D. Deutch and Y. Moskovitch and V. Tannen , title =

work page
[52]

and Milo, T

Deutch, D. and Milo, T. and Roy, S. and Tannen, V. Circuits for Datalog Provenance. Proc. 17th International Conference on Database Theory ICDT. 2014. doi:10.5441/002/icdt.2014.22

work page doi:10.5441/002/icdt.2014.22 2014
[53]

and Kimelfeld, B

Doleschal, J. and Kimelfeld, B. and Martens, W. and Peterfreund, L. Weight Annotation in Information Extraction. International Conference on Database Theory, ICDT 2020. 2020. doi:10.4230/LIPIcs.ICDT.2020.8

work page doi:10.4230/lipics.icdt.2020.8 2020
[54]

and Gastin, P

Droste, M. and Gastin, P. Weighted automata and weighted logics. International Colloquium on Automata, Languages, and Programming. 2005

work page 2005
[55]

and Gastin, P

Droste, M. and Gastin, P. Weighted automata and weighted logics. Handbook of weighted automata. 2009. doi:10.1007/978-3-642-01492-5_5

work page doi:10.1007/978-3-642-01492-5_5 2009
[56]

Handbook of Weighted Automata. 2009. doi:10.1007/978-3-642-01492-5

work page doi:10.1007/978-3-642-01492-5 2009
[57]

and Kuich, W

Droste, M. and Kuich, W. Semirings and formal power series. Handbook of Weighted Automata. 2009. doi:10.1007/978-3-642-01492-5_1

work page doi:10.1007/978-3-642-01492-5_1 2009
[58]

and Rahonis, G

Droste, M. and Rahonis, G. Weighted automata and weighted logics on infinite words. International Conference on Developments in Language Theory. 2006. doi:10.1007/11779148_6

work page doi:10.1007/11779148_6 2006
[59]

Positive games and persistent strategies

Duparc, J. Positive games and persistent strategies. International Workshop on Computer Science Logic. 2003. doi:10.1007/978-3-540-45220-1_17

work page doi:10.1007/978-3-540-45220-1_17 2003
[60]

and Flum, J

Ebbinghaus, H.-D. and Flum, J. Finite Model Theory. 1995. doi:10.1007/3-540-28788-4

work page doi:10.1007/3-540-28788-4 1995
[61]

and Jutla, C

Emerson, A. and Jutla, C. The complexity of tree automata and logics of programs. Proceedings of FOCS 1988. 1988. doi:10.1109/SFCS.1988.21949

work page doi:10.1109/sfcs.1988.21949 1988
[62]

Probabilities on finite models

Fagin, R. Probabilities on finite models. Journal of Symbolic Logic. 1976. doi:10.1017/S0022481200051756

work page doi:10.1017/s0022481200051756 1976
[63]

Nathan and Green, Todd J

Foster, J. Nathan and Green, Todd J. and Tannen, Val , title =. Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , pages =. 2008 , doi =

work page 2008
[64]

On Local and Non-Local Properties

Gaifman, H. On Local and Non-Local Properties. Proceedings of the Herbrand Symposium. 1982. doi:10.1016/S0049-237X(08)71879-2

work page doi:10.1016/s0049-237x(08)71879-2 1982
[65]

and Poggi, A

Geerts, F. and Poggi, A. On database query languages for K-relations. Journal of Applied Logic. 2010. doi:10.1016/j.jal.2009.09.001

work page doi:10.1016/j.jal.2009.09.001 2010
[66]

and Unger, T

Geerts, F. and Unger, T. and Karvounarakis, G. and Fundulaki, I. and Christophides, V. Algebraic Structures for Capturing the Provenance of SPARQL Queries. J. ACM. 2016. doi:10.1145/2810037

work page doi:10.1145/2810037 2016
[67]

Data Provenance

Glavic, B. Data Provenance. Foundations and Trends in Databases. 2021. doi:10.1561/1900000068

work page doi:10.1561/1900000068 2021
[68]

and Kogan, D

Glebskii, Y. and Kogan, D. and Liogon'kii, M. and Talanov, V. Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika. 1969. doi:10.1007/BF01071084

work page doi:10.1007/bf01071084 1969
[69]

Semiring Parsing

Goodman, J. Semiring Parsing. Computational Linguistics. 1999

work page 1999
[70]

Finite Model Theory and Its Applications

Gr. Finite Model Theory and Its Applications. 2007. doi:10.1007/3-540-68804-8

work page doi:10.1007/3-540-68804-8 2007
[71]

On the restraining power of guards

Gr. On the restraining power of guards. Journal of Symbolic Logic. 1999. doi:10.2307/2586808

work page doi:10.2307/2586808 1999
[72]

Why are modal logics so robustly decidable?

Gr. Why are modal logics so robustly decidable?. Bulletin of the European Association for Theoretical Computer Science. 1999

work page 1999
[73]

Metafinite Model Theory

Gr. Metafinite Model Theory. Information and Computation. 1998. doi:10.1006/inco.1997.2675

work page doi:10.1006/inco.1997.2675 1998
[74]

LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022

Gr. LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022. 2022. doi:10.1145/3531130.3533358

work page doi:10.1145/3531130.3533358 2022
[75]

Semiring Provenance for B \"u chi Games: Strategy Analysis with Absorptive Polynomials

Gr. Semiring Provenance for B \"u chi Games: Strategy Analysis with Absorptive Polynomials. 2021

work page 2021
[76]

Semiring Provenance for

Gr. Semiring Provenance for. Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021). 2021. doi:10.4204/EPTCS.346.5

work page doi:10.4204/eptcs.346.5 2021
[77]

Elementary Equivalence Versus Isomorphism in Semiring Semantics

Gr\". Elementary Equivalence Versus Isomorphism in Semiring Semantics. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). 2021. doi:10.4230/LIPIcs.ICALP.2021.133

work page doi:10.4230/lipics.icalp.2021.133 2021
[78]

The Freedoms of (Guarded) Bisimulation

Gr. The Freedoms of (Guarded) Bisimulation. Trends in Logic: Johan van Benthem on Logical and Informational Dynamics. 2014. doi:10.1007/978-3-319-06025-5_1

work page doi:10.1007/978-3-319-06025-5_1 2014
[79]

Semiring Provenance for First-Order Model Checking

Gr. Semiring Provenance for First-Order Model Checking. 2017. arXiv:1712.01980

work page arXiv 2017
[80]

Provenance Analysis and Semiring Semantics for First-Order Logic

Gr. Model Theory, Computer Science and Graph Polynomials. Festschrift for Johann A. Makowsky , title = "Provenance Analysis and Semiring Semantics for First-Order Logic", year = "2025", publisher =

work page 2025

Showing first 80 references.