Metraipolis › archive › dc_d817830befe8
On the Expressiveness of Asynchronous Processes with Nested Session Types — arXiv:2610.32558
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.32558
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-26T19:54:43.241Z
- SHA-256 of the archived text
1ece00229a34b8045a7b084c93c8c488a057deaedc8abce63165a1f3465920da- Stable URL of this page
https://metraipolis.com/documento/dc_d817830befe8
How to cite
On the Expressiveness of Asynchronous Processes with Nested Session Types — arXiv:2610.32558 — arXiv (en), https://arxiv.org/abs/2610.32558 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d817830befe8 (Metraipolis archive dc_d817830befe8, sha256 1ece00229a34b8045a7b084c93c8c488a057deaedc8abce63165a1f3465920da)
BibTeX
@misc{dcd817830befe8,
title = {On the Expressiveness of Asynchronous Processes with Nested Session Types — arXiv:2610.32558},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.32558},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d817830befe8; sha256 1ece00229a34b8045a7b084c93c8c488a057deaedc8abce63165a1f3465920da},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.32558. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Session types are a type-based approach to correct message-passing programs, where types specify protocols for channels and type checking guarantees communication correctness. Traditional session types express regular protocols only, which leaves out many protocols found in practice. Aiming at overcoming this limitation, Nested Session Types (NSTs) can specify nested recursive protocols. NSTs are known to be characterised by one-counter machines and deterministic context-free languages. In this paper, we study the expressiveness of ASP (Asynchronous Session Processes), the process model associated with NSTs as introduced by Das et al. We prove that AST is Turing complete by giving a correct encoding of two-counter machines into typed processes. Our encoding uses a non-trivial state-aware representation of counters and instructions that is neatly governed by NSTs. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Programming Languages (cs.PL) ; Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2610.32558 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-26T19:46:03.306Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).