Weak models of distributed computing, with connections to modal logic
From MaRDI portal
Publication:5918244
DOI10.1007/s00446-013-0202-3zbMath1322.68075OpenAlexW3102677305WikidataQ58179389 ScholiaQ58179389MaRDI QIDQ5918244
Matti Järvisalo, Tuomo Lempiäinen, Juhana Laurinharju, Jonni Virtema, Jukka Suomela, Kerkko Luosto, Antti Kuusisto, Lauri Hella
Publication date: 25 March 2015
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/37409
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items
Node labels in local decision, Counter machines and distributed automata -- a story about exchanging space and time, Constant space and non-constant time in distributed computing, Communicating Finite-State Machines and Two-Variable Logic, Emptiness problems for distributed automata, Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic, Unnamed Item, Unnamed Item, Unnamed Item, On the expressive power of message-passing neural networks as global feature map transformers, Modal Logic S5 Satisfiability in Answer Set Programming, Efficient SAT-based minimal model generation methods for modal logic S5
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Anonymous wireless rings
- Local approximability of max-min and min-max linear programs
- A simple local 3-approximation algorithm for vertex cover
- Computing on anonymous networks with sense of direction
- Impact of locality on location aware unit disk graphs
- Almost stable matchings by truncating the Gale-Shapley algorithm
- A note on graded modal logic
- Beeping a maximal independent set
- In so many possible worlds
- Survey of local algorithms
- Lower bounds for local approximation
- Computing anonymously with arbitrary knowledge
- Brief Announcement: Distributed Approximations for the Semi-matching Problem
- Knowledge and common knowledge in a distributed environment
- Groupings and Pairings in Anonymous Networks
- Fast Distributed Approximations in Planar Graphs
- The price of being near-sighted
- Deploying Wireless Networks with Beeps
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Statistical mechanics of cellular automata
- Computing on an anonymous ring
- Locality in Distributed Graph Algorithms
- Gap Theorems for Distributed Computation
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- Computing functions on asynchronous anonymous networks
- Stone age distributed computing
- Distributed algorithms for edge dominating sets
- On the complexity of distributed graph coloring
- Origins of bisimulation and coinduction
- Weak models of distributed computing, with connections to modal logic
