Imperative process algebra and models of computation
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929392466264064 |
|---|---|
| author | Middelburg, C. A. |
| author_facet | Middelburg, C. A. |
| contents | Studies of issues related to computability and computational complexity involve the use of a model of computation. Pivotal to such a model are the computational processes considered. 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. A probabilistic variant of the model based on sequential random access machines and complexity measures for it are also described. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_02472 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Imperative process algebra and models of computation Middelburg, C. A. Logic in Computer Science Computational Complexity D.1.3; F.1.1; F.1.2; F.1.3 Studies of issues related to computability and computational complexity involve the use of a model of computation. Pivotal to such a model are the computational processes considered. 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. A probabilistic variant of the model based on sequential random access machines and complexity measures for it are also described. |
| title | Imperative process algebra and models of computation |
| topic | Logic in Computer Science Computational Complexity D.1.3; F.1.1; F.1.2; F.1.3 |
| url | https://arxiv.org/abs/2206.02472 |