Operational algorithmic game semantics

Conference item

We consider a simply-typed call-by-push-value calculus with state, and provide a fully abstract trace model via a labelled transition system (LTS) in the spirit of operational game semantics. By examining the shape of configurations and performing a series of natural optimisation steps based on name recycling, we identify a fragment for which the LTS can be recast as a deterministic visibly pushdown automaton. This implies decidability of contextual equivalence for the fragment identified and solvability in exponential time for terms in canonical form. We also identify a fragment for which these automata are finite-state machines.Further, we use the trace model to prove that translations of prototypical call-by-name (IA) and call-by-value (RML) languages into our call-by-push-value language are fully abstract. This allows our decidability results to be seen as subsuming several results from the literature for IA and RML. We regard our operational approach as a simpler and more intuitive way of deriving such results. The techniques we rely on draw upon simple intuitions from operational semantics and the resultant automata retain operational style, capturing the dynamics of the underlying language.

Authors: Bunting, B; Murawski, AS

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: Proceedings of the 38th ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
• Pages: 1-13
• Publication date: 2023-07-14
• Acceptance date: 2023-04-05
• Event title: 38th ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
• Event location: Boston, MA, USA
• Event website: https://lics.siglog.org/lics23/
• Event start date: 2023-06-26
• Event end date: 2023-06-29
• DOI: 10.1109/LICS56636.2023.10175791
• EISBN: 979-8-3503-3587-3
• ISBN: 979-8-3503-3588-0
• Language: English
• Keywords: FFR