Descriptive complexity for distributed computing with circuits

DOI10.1093/LOGCOM/EXAE087MaRDI QIDQ6915737zbMATH OpenFDO

Authors Veeti Ahvonen, Damian Heiman, Lauri Hella, Antti Kuusisto

Publication date 15 October 2025

Published in Journal of Logic and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1093/LOGCOM/EXAE087

zbMATH Keywords

distributed computinggraph coloringlogicdescriptive complexity

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Cites work

• Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Elements of finite model theory.
• Identifiers in registers. Describing network algorithms with logic
• Infinite networks, halting and local algorithms
• Modal logic and distributed message passing automata
• Parallel Symmetry-Breaking in Sparse Graphs
• The descriptive complexity of graph neural networks
• The logic of graph neural networks
• Theory of graph neural networks: representation and learning
• Weak models of distributed computing, with connections to modal logic
• Weak models of distributed computing, with connections to modal logic

Cited in

(1)

• Descriptive complexity for neural networks via Boolean networks

This page was built for publication: Descriptive complexity for distributed computing with circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6915737)