Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911102970888192 |
|---|---|
| author | Schewe, Klaus-Dieter Ferrarotti, Flavio |
| author_facet | Schewe, Klaus-Dieter Ferrarotti, Flavio |
| contents | We develop a behavioural theory of reflective parallel algorithms (RAs), i.e. synchronous parallel algorithms that can modify their own behaviour. The theory comprises a set of postulates defining the class of RAs, an abstract machine model, and the proof that all RAs are captured by this machine model. RAs are sequential-time, parallel algorithms, where every state includes a representation of the algorithm in that state, thus enabling linguistic reflection. Bounded exploration is preserved using multiset comprehension terms as values. The abstract machine model is defined by reflective Abstract State Machines (rASMs), which extend ASMs using extended states that include an updatable representation of the main ASM rule to be executed by the machine in that state. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09053 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms Schewe, Klaus-Dieter Ferrarotti, Flavio Logic in Computer Science 68Q10, 68N19 We develop a behavioural theory of reflective parallel algorithms (RAs), i.e. synchronous parallel algorithms that can modify their own behaviour. The theory comprises a set of postulates defining the class of RAs, an abstract machine model, and the proof that all RAs are captured by this machine model. RAs are sequential-time, parallel algorithms, where every state includes a representation of the algorithm in that state, thus enabling linguistic reflection. Bounded exploration is preserved using multiset comprehension terms as values. The abstract machine model is defined by reflective Abstract State Machines (rASMs), which extend ASMs using extended states that include an updatable representation of the main ASM rule to be executed by the machine in that state. |
| title | Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms |
| topic | Logic in Computer Science 68Q10, 68N19 |
| url | https://arxiv.org/abs/2508.09053 |