Abstrakti
We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.
| Alkuperäiskieli | Englanti |
|---|---|
| Otsikko | 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 |
| Toimittajat | Jerome Leroux, Sylvain Lombardy, David Peleg |
| Kustantaja | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| ISBN (elektroninen) | 9783959772921 |
| DOI - pysyväislinkit | |
| Tila | Julkaistu - elok. 2023 |
| OKM-julkaisutyyppi | A4 Artikkeli konferenssijulkaisussa |
| Tapahtuma | International Symposium on Mathematical Foundations of Computer Science - Bordeaux, Ranska Kesto: 28 elok. 2023 → 1 syysk. 2023 |
Julkaisusarja
| Nimi | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Vuosikerta | 272 |
| ISSN (elektroninen) | 1868-8969 |
Conference
| Conference | International Symposium on Mathematical Foundations of Computer Science |
|---|---|
| Maa/Alue | Ranska |
| Kaupunki | Bordeaux |
| Ajanjakso | 28/08/23 → 1/09/23 |
Rahoitus
Funding Antti Kuusisto and Veeti Ahvonen were supported by the Academy of Finland project Theory of computational logics, grant numbers 352419, 352420, 353027, 324435, 328987. Antti Kuusisto was also supported by the Academy of Finland consortium project Explaining AI via Logic (XAILOG), grant number 345612. Veeti Ahvonen was also supported by the Vilho, Yrjö and Kalle Väisälä Foundation of the Finnish Academy of Science and Letters.
Julkaisufoorumi-taso
- Jufo-taso 1
!!ASJC Scopus subject areas
- Software