2026-07-20T05:59:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19005 2024-03-06T11:03:15Z ddc:004 open_access

Subtyping Context-Free Session Types Silva, Gil Mordido, Andreia Vasconcelos, Vasco T. Session types Subtyping Simulation Simple grammars Non-regular recursion Context-free session types describe structured patterns of communication on heterogeneously typed channels, allowing the specification of protocols unconstrained by tail recursion. The enhanced expressive power provided by non-regular recursion comes, however, at the cost of the decidability of subtyping, even if equivalence is still decidable. We present an approach to subtyping context-free session types based on a novel kind of observational preorder we call XYZW-simulation, which generalizes XY-simulation (also known as covariant-contravariant simulation) and therefore also bisimulation and plain simulation. We further propose a subtyping algorithm that we prove to be sound, and present an empirical evaluation in the context of a compiler for a programming language. Due to the general nature of the simulation relation upon which it is built, this algorithm may also find applications in other domains. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gil Silva and Andreia Mordido and Vasco T. Vasconcelos 2023 Is Part Of LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2023.11 urn:nbn:de:0030-drops-190055 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode