Abstract state machines capture parallel algorithms
- 1 October 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 4 (4), 578-651
- https://doi.org/10.1145/937555.937561
Abstract
We give an axiomatic description of parallel, synchronous algorithms. Our main result is that every such algorithm can be simulated, step for step, by an abstract state machine with a background that provides for multisets.Keywords
This publication has 9 references indexed in Scilit:
- Quantum Computing and Abstract State MachinesLecture Notes in Computer Science, 2003
- Fixed Point LogicsBulletin of Symbolic Logic, 2002
- Fixed Point LogicsBulletin of Symbolic Logic, 2002
- The Logic of ChoiceThe Journal of Symbolic Logic, 2000
- Sequential abstract-state machines capture sequential algorithmsACM Transactions on Computational Logic, 2000
- Choiceless polynomial timeAnnals of Pure and Applied Logic, 1999
- Metafinite Model TheoryInformation and Computation, 1998
- Processes are in the eye of the beholderTheoretical Computer Science, 1997
- Parallel Algorithms for Shared-Memory MachinesPublished by Elsevier BV ,1990