Parallel program schemata. (English) Zbl 0198.32603

From the author’s introduction: This paper introduces a model called the parallel program schema for the representation and study of programs containing parallel sequencing. The model is related to Janov’s program schema, but extends it, both by modelling memory structure in more detail and by admitting parallel computation. The emphasis is on decision procedures, both for traditional properties, such as equivalence, and for new properties particular to parallel computation, such as determinacy and boundedness.
Reviewer: Robert M. Baer


03-XX Mathematical logic and foundations
Full Text: DOI


[1] Ginsburg, S., (The Mathematical Theory of Context-Free Languages (1966), McGraw-Hill: McGraw-Hill New York) · Zbl 0184.28401
[2] Ianov, I. I., The logical schemes of algorithms, Problems of Cybernetics, I, 75-127 (1958) · Zbl 0085.34003
[3] Karp, R. M.; Miller, R. E., Properties of a model for parallel computations: determinacy termination, queueing, SIAM J. Appl. Math., 14, 1390-1411 (1966) · Zbl 0149.12501
[4] Karp, R. M.; Miller, R. E., Parallel program schemata: A mathematical model for parallel computation, (IEEE Conference Record of the Eighth Annual Symposium on Switching and Automata Theory (October 1967)), 55-61 · Zbl 0369.68013
[5] Karp, R. M.; Miller, R. E.; Winograd, S., The organization of computations for uniform recurrence equations, J. Assoc. Comp. Math., 14, 563-590 (1967) · Zbl 0171.38305
[6] König, D., (Theorie der Endlichen und Unendlichen Graphen (1936), Akademische Verlagsgesellschaft: Akademische Verlagsgesellschaft Leipzig)
[7] Luckham, D. C.; Park, D. M.R.; Paterson, M. S., On formalised computer programs, (Preliminary Draft (1967), Programming Research Group, Oxford University) · Zbl 0363.68027
[8] Post, E., A variant of a recursively unsolvable problem, Bull. Am. Math. Soc., 52, 264-268 (1946) · Zbl 0063.06329
[9] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Develop., 3, 198-220 (1959) · Zbl 0158.25404
[10] Rutledge, J. D., On Ianov’s program schemata, J. Assoc. Comp. Mach., 11, 1-9 (1964) · Zbl 0121.12107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.