A Behavioural Thesis of Synchronous Parallel Algorithms -- Correction of the Simplified Parallel ASM Thesis

arXiv:1504.06203 · cs.LO · Submitted 2015-04-23 · Read on arXiv

cs.LO

Submitted: 2015-04-23

Updated: 2026-10-29

Comments: 52 pages. v2 corrects v1: Lemma 7.11 of v1 is false and the characterization theorem fails under the original postulates. The bounded exploration postulate now requires uniformly definable updates, and the theorem is proved anew. Title changed. A revised form of v1 appeared in Theor. Comput. Sci. 649 (2016) 25-53; a corrigendum has been submitted to the same journal

Journal ref: Theoretical Computer Science, 2016, Volume 649, 11 October 2016, Pages 25--53

DOI: 10.1016/j.tcs.2016.08.013

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

Related papers