Journal article icon

Journal article

Causal computational complexity of distributed processes

Abstract:

This article studies the complexity of π-calculus processes with respect to the quantity of transitions caused by an incoming message. First, we propose a typing system for integrating Bellantoni and Cook's characterisation of polytime computable functions into Deng and Sangiorgi's typing system for termination. We then define computational complexity of distributed messages based on Degano and Priami's causal semantics, which identifies the dependency between interleaved transitions. Next, w...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.ic.2022.104998

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Wolfson College
Role:
Author
ORCID:
0000-0002-3925-8557
Publisher:
Elsevier
Journal:
Information and Computation More from this journal
Volume:
290
Article number:
104998
Publication date:
2022-12-07
Acceptance date:
2022-11-27
DOI:
EISSN:
1090-2651
ISSN:
0890-5401
Language:
English
Keywords:
Pubs id:
1310669
Local pid:
pubs:1310669
Deposit date:
2022-11-29

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP