{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:28:20Z","timestamp":1747153700969,"version":"3.40.5"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Studies of issues related to computability and computational complexity involve the use of a model of computation. Central in such a model are computational processes. Processes of this kind can be described using an imperative process algebra based on ACP (Algebra of Communicating Processes). In this paper, it is investigated whether the imperative process algebra concerned can play a role in the field of models of computation. It is demonstrated that the process algebra is suitable to describe in a mathematically precise way models of computation corresponding to existing models based on sequential, asynchronous parallel, and synchronous parallel random access machines as well as time and work complexity measures for those models.<\/jats:p>","DOI":"10.1007\/s00224-024-10164-0","type":"journal-article","created":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T11:02:38Z","timestamp":1710414158000},"page":"529-570","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Imperative Process Algebra and Models of Parallel Computation"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8725-0197","authenticated-orcid":false,"given":"Cornelis A.","family":"Middelburg","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,14]]},"reference":[{"key":"10164_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley, Reading, MA (1974)"},{"key":"10164_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2015.07.013","volume":"603","author":"A Asperti","year":"2015","unstructured":"Asperti, A., Ricciotti, W.: A formalization of multi-tape Turing machines. Theoret. Comput. Sci. 603, 23\u201342 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.07.013","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10164_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0890-5401(88)90027-2","volume":"78","author":"JCM Baeten","year":"1988","unstructured":"Baeten, J.C.M., Bergstra, J.A.: Global renaming operators in concrete process algebra. Inf. Control 78(3), 205\u2013245 (1988). https:\/\/doi.org\/10.1016\/0890-5401(88)90027-2","journal-title":"Inf. Control"},{"key":"10164_CR4","doi-asserted-by":"publisher","unstructured":"Baeten, J.C.M., Weijland, W.P. : Process Algebra. Cambridge Tracts in Theoretical Computer Science, vol. 18. Cambridge University Press, Cambridge (1990) https:\/\/doi.org\/10.1017\/CBO9780511624193","DOI":"10.1017\/CBO9780511624193"},{"issue":"1\u20133","key":"10164_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0019-9958(84)80025-X","volume":"60","author":"JA Bergstra","year":"1984","unstructured":"Bergstra, J.A., Klop, J.W.: Process algebra for synchronous communication. Inf. Control 60(1\u20133), 109\u2013137 (1984). https:\/\/doi.org\/10.1016\/S0019-9958(84)80025-X","journal-title":"Inf. Control"},{"issue":"3","key":"10164_CR6","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.jal.2011.03.001","volume":"9","author":"JA Bergstra","year":"2011","unstructured":"Bergstra, J.A., Middelburg, C.A.: Inversive meadows and divisive meadows. J. Appl. Log. 9(3), 203\u2013220 (2011). https:\/\/doi.org\/10.1016\/j.jal.2011.03.001","journal-title":"J. Appl. Log."},{"issue":"2","key":"10164_CR7","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1219092.1219095","volume":"54","author":"JA Bergstra","year":"2007","unstructured":"Bergstra, J.A., Tucker, J.V.: The rational numbers as an abstract data type. J. ACM 54(2), 7 (2007). https:\/\/doi.org\/10.1145\/1219092.1219095","journal-title":"J. ACM"},{"issue":"2","key":"10164_CR8","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"Blum, M.: A machine-independent theory of the complexity of recursive functions. J. ACM 14(2), 322\u2013336 (1967). https:\/\/doi.org\/10.1145\/321386.321395","journal-title":"J. ACM"},{"key":"10164_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.4204\/EPTCS.322.5","volume":"322","author":"MS Bouwman","year":"2020","unstructured":"Bouwman, M.S., Luttik, S.P., Schols, W.R.M., Willemse, T.A.C.: A process algebra with global variables. Electronic Proceedings in Theoretical Computer Science 322, 33\u201350 (2020). https:\/\/doi.org\/10.4204\/EPTCS.322.5","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"10164_CR10","doi-asserted-by":"publisher","unstructured":"Cole, R., Zajicek, O. : The APRAM: Incorporating asynchrony into the PRAM model. In: SPAA \u201989. pp. 169\u2013178 ACM, New York (1989). https:\/\/doi.org\/10.1145\/72935.72954","DOI":"10.1145\/72935.72954"},{"key":"10164_CR11","doi-asserted-by":"publisher","unstructured":"Colvin, R., Hayes, I.J. : CSP with hierarchical state. In: Leuschel, M., Wehrheim, H. (eds) IFM 2009. Lecture Notes in Computer Science, vol. 5423. pp 118\u2013135. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-00255-7_9","DOI":"10.1007\/978-3-642-00255-7_9"},{"issue":"4","key":"10164_CR12","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1145\/800152.804898","volume":"7","author":"SA Cook","year":"1973","unstructured":"Cook, S.A., Reckhow, R.A.: Time bounded random access machines. J Comput. Syst. Sci. 7(4), 354\u2013375 (1973). https:\/\/doi.org\/10.1145\/800152.804898","journal-title":"J Comput. Syst. Sci."},{"key":"10164_CR13","doi-asserted-by":"publisher","unstructured":"De Nicola, R., Pugliese, R. (1997) Testing semantics of asynchronous distributed programs. In: Dam, M. (ed) LOMAPS 1996. Lecture Notes in Computer Science, vol. 1192. pp 320\u2013344. Springer, Berlin. https:\/\/doi.org\/10.1007\/3-540-62503-8_15","DOI":"10.1007\/3-540-62503-8_15"},{"key":"10164_CR14","doi-asserted-by":"publisher","unstructured":"van Emde\u00a0Boas, P. : Machine models and simulations. In: van Leeuwen, J. (ed.) Handbook of theoretical computer scienceo vol. A. pp 2\u201366. Elsevier, Amsterdam (1990) https:\/\/doi.org\/10.1016\/B978-0-444-88071-0.50006-0","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"key":"10164_CR15","doi-asserted-by":"publisher","unstructured":"Fehnker, A., van Glabbeek, R.J., H\u00f6fner, P., McIver, A., Portmann, M., Tan, W.L.: A process algebra for wireless mesh networks. In: Seidl, H. (ed) ESOP 2012. Lecture Notes in Computer Science, vol 7211. pp 295\u2013315. Springer, Berlin (2012) https:\/\/doi.org\/10.1007\/978-3-642-28869-2_15","DOI":"10.1007\/978-3-642-28869-2_15"},{"key":"10164_CR16","doi-asserted-by":"publisher","unstructured":"Fortune, S., Wyllie, J. : Parallelism in random access machines. In: STOC \u201978. pp 114\u2013118. ACM, New York, (1978) https:\/\/doi.org\/10.1145\/800133.804339","DOI":"10.1145\/800133.804339"},{"key":"10164_CR17","doi-asserted-by":"publisher","unstructured":"Gibbons, P.B. : A more practical PRAM model. In: SPAA \u201989. pp 158\u2013168. ACM, New York (1989) https:\/\/doi.org\/10.1145\/72935.72953","DOI":"10.1145\/72935.72953"},{"key":"10164_CR18","unstructured":"Goguen, J.A. : Theorem Proving and Algebra (2021) arXiv:2101.02690"},{"issue":"4","key":"10164_CR19","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"LM Goldschlager","year":"1982","unstructured":"Goldschlager, L.M.: A universal interconnection pattern for parallel computers. J. ACM 29(4), 1073\u20131086 (1982). https:\/\/doi.org\/10.1145\/322344.322353","journal-title":"J. ACM"},{"key":"10164_CR20","doi-asserted-by":"publisher","unstructured":"Goodrich, M.T. : Intersecting line segments in parallel with an output-sensitive number of processors. In: SPAA \u201989. pp 127\u2013137. ACM, New York (1989). https:\/\/doi.org\/10.1145\/72935.72950","DOI":"10.1145\/72935.72950"},{"key":"10164_CR21","doi-asserted-by":"publisher","unstructured":"Hartmanis, J., Simon, J. : On the power of multiplication in random access machines. In: SWAT \u201974, pp. 13\u201323. IEEE, New York (1974). https:\/\/doi.org\/10.1109\/SWAT.1974.20","DOI":"10.1109\/SWAT.1974.20"},{"issue":"5","key":"10164_CR22","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/BF01212486","volume":"5","author":"M Hennessy","year":"1993","unstructured":"Hennessy, M., Ing\u00f3lfsd\u00f3ttir, A.: Communicating processes with value-passing and assignments. Formal Aspects Comput. 5(5), 432\u2013466 (1993). https:\/\/doi.org\/10.1007\/BF01212486","journal-title":"Formal Aspects Comput."},{"key":"10164_CR23","volume-title":"Communicating Sequential Processes","author":"CAR Hoare","year":"1985","unstructured":"Hoare, C.A.R.: Communicating Sequential Processes. Prentice-Hall, Englewood Cliffs (1985)"},{"key":"10164_CR24","doi-asserted-by":"publisher","unstructured":"Karp, R.M., Ramachandran, V. : Parallel algorithms for shared-memory machines. In: van Leeuwen, J. (ed) Handbook of Theoretical Computer Science vol. A. pp 870\u2013941. Elsevier, Amsterdam (1990). https:\/\/doi.org\/10.1016\/B978-0-444-88071-0.50022-9","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"issue":"1","key":"10164_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"CP Kruskal","year":"1990","unstructured":"Kruskal, C.P.: Rudolph L, Snir M: A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71(1), 95\u2013132 (1990). https:\/\/doi.org\/10.1016\/0304-3975(90)90192-K","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10164_CR26","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1145\/177492.177726","volume":"16","author":"L Lamport","year":"1994","unstructured":"Lamport, L.: The temporal logic of actions. ACM Trans. Program. Lang. Syst. 16(3), 872\u2013923 (1994). https:\/\/doi.org\/10.1145\/177492.177726","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"10164_CR27","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1137\/S0097539794265402","volume":"26","author":"L Mak","year":"1997","unstructured":"Mak, L.: Parallelism always helps. SIAM Journal of Computing 26(1), 153\u2013172 (1997). https:\/\/doi.org\/10.1137\/S0097539794265402","journal-title":"SIAM Journal of Computing"},{"key":"10164_CR28","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.scico.2005.09.001","volume":"60","author":"WD Maurer","year":"2006","unstructured":"Maurer, W.D.: A theory of computer instructions. Sci. Comput. Program. 60, 244\u2013273 (2006). https:\/\/doi.org\/10.1016\/j.scico.2005.09.001","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"10164_CR29","doi-asserted-by":"publisher","first-page":"137","DOI":"10.7561\/SACS.2022.1.137","volume":"32","author":"CA Middelburg","year":"2022","unstructured":"Middelburg, C.A.: Imperative process algebra with abstraction. Sci. Ann. Comput. Sci. 32(1), 137\u2013179 (2022). https:\/\/doi.org\/10.7561\/SACS.2022.1.137","journal-title":"Sci. Ann. Comput. Sci."},{"issue":"6","key":"10164_CR30","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S0097539791219670","volume":"23","author":"N Nishimura","year":"1994","unstructured":"Nishimura, N.: A model for asynchronous shared memory parallel computation. SIAM J Comput. 23(6), 1122\u20131147 (1994). https:\/\/doi.org\/10.1137\/S0097539791219670","journal-title":"SIAM J Comput."},{"key":"10164_CR31","doi-asserted-by":"publisher","unstructured":"Norrish, M. : Mechanised computability theory. In: van Eekelen, M., Geuvers, H., Schmaltz, J., Wiedijk, F. (eds) ITP 2011. Lecture Notes in Computer Science, vol. 6898. pp 297\u2013311. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-22863-6_22","DOI":"10.1007\/978-3-642-22863-6_22"},{"key":"10164_CR32","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1994)"},{"issue":"1","key":"10164_CR33","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01053036","volume":"55","author":"D Pigozzi","year":"1995","unstructured":"Pigozzi, D., Salibra, A.: The abstract variable-binding calculus. Stud. Logica. 55(1), 129\u2013179 (1995). https:\/\/doi.org\/10.1007\/BF01053036","journal-title":"Stud. Logica."},{"key":"10164_CR34","doi-asserted-by":"publisher","unstructured":"Sannella, D., Tarlecki, A. : Algebraic preliminaries. In: Astesiano, E., Kreowski, H.-J., Krieg-Br\u00fcckner, B. (eds) Algebraic Foundations of Systems Specification. pp 13\u201330. Springer, Berlin (1999). https:\/\/doi.org\/10.1007\/978-3-642-59851-7_2","DOI":"10.1007\/978-3-642-59851-7_2"},{"key":"10164_CR35","doi-asserted-by":"publisher","unstructured":"Schneider, F.B. : On Concurrent Programming. Graduate Texts in Computer Science. Springer, Berlin (1997). https:\/\/doi.org\/10.1007\/978-1-4612-1830-2","DOI":"10.1007\/978-1-4612-1830-2"},{"issue":"2","key":"10164_CR36","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"LJ Stockmeyer","year":"1984","unstructured":"Stockmeyer, L.J.: Vishkin U: Simulation of parallel random access machines by circuits. SIAM Journal of Computing 13(2), 409\u2013422 (1984). https:\/\/doi.org\/10.1137\/0213027","journal-title":"SIAM Journal of Computing"},{"issue":"3\u20134","key":"10164_CR37","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1142\/S0129054194000128","volume":"5","author":"JL Trahan","year":"1994","unstructured":"Trahan, J.L., Vedantham, S.: Analysis of PRAM instruction sets from a log cost perspective. Int. J. Found. Comput. Sci. 5(3\u20134), 231\u2013246 (1994). https:\/\/doi.org\/10.1142\/S0129054194000128","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10164_CR38","doi-asserted-by":"publisher","unstructured":"Wirsing, M. : Algebraic specification. In: van Leeuwen, J. (ed) Handbook of Theoretical Computer Science vol. B. pp 675\u2013788. Elsevier, Amsterdam (1990). https:\/\/doi.org\/10.1016\/B978-0-444-88074-1.50018-4","DOI":"10.1016\/B978-0-444-88074-1.50018-4"},{"key":"10164_CR39","unstructured":"Wloka, M.G. : Parallel VLSI synthesis. PhD Thesis, Department of Computer Science, Brown University, Providence, RI (1991)"},{"key":"10164_CR40","doi-asserted-by":"publisher","unstructured":"Xu, J., Zhang, X., Urban, C. : Mechanising Turing machines and computability theory in Isabelle\/HOL. In: Blazy, S., Paulin-Mohring, C., Pichardie, D. (eds) ITP 2013. Lecture Notes in Computer Science, vol. 7998. pp 147\u2013162. Springer, Berlin (2013) https:\/\/doi.org\/10.1007\/978-3-642-39634-2_13","DOI":"10.1007\/978-3-642-39634-2_13"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10164-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10164-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10164-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T02:03:03Z","timestamp":1718935383000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10164-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,14]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10164"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10164-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,3,14]]},"assertion":[{"value":"18 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}