article

Parallel program schemata

Authors:

Richard M. Karp,

Raymond E. MillerAuthors Info & Claims

Journal of Computer and System Sciences, Volume 3, Issue 2

Pages 147 - 195

https://doi.org/10.1016/S0022-0000(69)80011-5

Published: 01 May 1969 Publication History

Abstract

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 Ianov'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.

References

[1]

In: The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York.

Crossref

Google Scholar

[2]

The logical schemes of algorithms. Problems of Cybernetics. vI. 75-127.

Google Scholar

[3]

Properties of a model for parallel computations: determinacy termination, queueing. SIAM J. Appl. Math. v14. 1390-1411.

Google Scholar

[4]

Parallel program schemata: A mathematical model for parallel computation. In: IEEE Conference Record of the Eighth Annual Symposium on Switching and Automata Theory, pp. 55-61.

Crossref

Google Scholar

[5]

The organization of computations for uniform recurrence equations. J. Assoc. Comp. Math. v14. 563-590.

Crossref

Google Scholar

[6]

In: Theorie der Endlichen und Unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig.

Google Scholar

[7]

On formalised computer programs. In: Preliminary Draft, Programming Research Group, Oxford University.

Google Scholar

[8]

A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. v52. 264-268.

Crossref

Google Scholar

[9]

Finite automata and their decision problems. IBM J. Res. Develop. v3. 198-220.

Crossref

Google Scholar

[10]

On Ianov's program schemata. J. Assoc. Comp. Mach. v11. 1-9.

Crossref

Google Scholar

Cited By

View all

Luchsinger ADoty DSoloveichik DKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Optimally Encoding Information in Chemical Reaction NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662827(61-64)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662827
Aiswarya CCalvanese DDi Cosmo FMontali M(2024)Verification of Unary Communicating Datalog ProgramsProceedings of the ACM on Management of Data10.1145/36515902:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651590
Balasubramanian AMajumdar RThinniyam RZetzsche G(2024)Reachability in Continuous Pushdown VASSProceedings of the ACM on Programming Languages10.1145/36332798:POPL(90-114)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3633279
Show More Cited By

Parallel program schemata
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Parallel Program Schemata and Maximal Parallelism I. Fundamental Results

The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part I presents the basic properties of this model. Two types of equivalence relation on computations are presented, to each of which there ...
On Ianov's Program Schemata

Ianov has defined a formal abstraction of the notion of program which represents the sequential and control properties of a program but suppresses the details of the operations. For these schemata he defines a notion corresponding to computation and ...
On maximally parallel schemata
SWAT '70: Proceedings of the 11th Annual Symposium on Switching and Automata Theory (swat 1970)

A model for parallel computation called a schema is presented. This model is similar to that presented in the recent work of Karp and Miller2. Section 1 presents a description of the model, and some results on the characterization of computations within ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 3, Issue 2

May, 1969

113 pages

ISSN:0022-0000

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 May 1969

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

257
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Luchsinger ADoty DSoloveichik DKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Optimally Encoding Information in Chemical Reaction NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662827(61-64)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662827
Aiswarya CCalvanese DDi Cosmo FMontali M(2024)Verification of Unary Communicating Datalog ProgramsProceedings of the ACM on Management of Data10.1145/36515902:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651590
Balasubramanian AMajumdar RThinniyam RZetzsche G(2024)Reachability in Continuous Pushdown VASSProceedings of the ACM on Programming Languages10.1145/36332798:POPL(90-114)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3633279
Payet É(2024)Non-termination in Term Rewriting and Logic ProgrammingJournal of Automated Reasoning10.1007/s10817-023-09693-z68:1Online publication date: 2-Feb-2024
https://dl.acm.org/doi/10.1007/s10817-023-09693-z
Anderson RFu BMassie AMukhopadhyay GSalinas ASchweller RTomai EWylie T(2024)Computing Threshold Circuits with Bimolecular Void Reactions in Step Chemical Reaction NetworksUnconventional Computation and Natural Computation10.1007/978-3-031-63742-1_18(253-268)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-63742-1_18
Colom J(2024)Harnessing Structure Theory of Petri Nets in Discrete Event System SimulationApplication and Theory of Petri Nets and Concurrency10.1007/978-3-031-61433-0_1(3-23)Online publication date: 26-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-61433-0_1
Hilaire TIlcinkas DLeroux J(2024)A State-of-the-Art Karp-Miller Algorithm Certified in CoqTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57246-3_21(370-389)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57246-3_21
Leroux J(2024)Ackermannian Completion of SeparatorsFoundations of Software Science and Computation Structures10.1007/978-3-031-57228-9_1(3-10)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57228-9_1
Demri SRönnholm RMarquis PSon TKern-Isberner G(2023)How to manage a budget with ATL+Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/19(188-197)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/19
Demri SFervari RWilliams BChen YNeville J(2023)Model-checking for ability-based logics with constrained plansProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25776(6305-6312)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25776
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations