Logic and Computation through the Lens of Semirings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909617310662656 |
|---|---|
| author | Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura |
| author_facet | Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura |
| contents | We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of Blum-Shub-Smale machines and arithmetic circuits defined over a semiring. In particular, we give a logical characterization of constant-depth arithmetic circuits by an extension of first-order logic that holds for any semiring that is both commutative and positive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12939 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Logic and Computation through the Lens of Semirings Barlag, Timon Fröhlich, Nicolas Hankala, Teemu Hannula, Miika Hirvonen, Minna Holzapfel, Vivian Kontinen, Juha Meier, Arne Strieker, Laura Logic in Computer Science Computational Complexity We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of Blum-Shub-Smale machines and arithmetic circuits defined over a semiring. In particular, we give a logical characterization of constant-depth arithmetic circuits by an extension of first-order logic that holds for any semiring that is both commutative and positive. |
| title | Logic and Computation through the Lens of Semirings |
| topic | Logic in Computer Science Computational Complexity |
| url | https://arxiv.org/abs/2502.12939 |