Top-Down or Bottom-Up? Complexity Analyses of Synchronous Multiparty Session Types
summary
Compares top-down global-type workflows against bottom-up endpoint inference with concrete algorithms: a new quadratic type-graph subtyping algorithm replacing exponential inductive checks, a PSPACE sound-and-complete coinductive projection via type graphs, and a novel type inference that builds minimum type graphs but is exponential in process size. Shows liveness/property checking for typing contexts is PSPACE-hard, gives nondeterministic PSPACE and deterministic exponential procedures, and argues top-down is often cheaper.
AI-written summary · about