UNAMBIGUOUS SHARED-MEMORY SYSTEMS
2010
Shared-memory systems appear as a generalization of asynchronous cellular automata. In this paper we relate the partial-order semantics of shared-memory systems to Mazurkiewicz trace languages by means of a new refinement construction. We show that a set of labeled partial orders is recognized by some unambiguous shared-memory system if and only if it is definable in monadic second-order logic and media-bounded.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
1
Citations
NaN
KQI