A Behavioural Thesis of Synchronous Parallel Algorithms -- Correction of the Simplified Parallel ASM Thesis
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
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring