Skip to main content
University of Oxford Department of Computer Science
This page links to self-archived versions of papers.
Publishers' versions can be accessed via DBLP by clicking on the image below.
To see abstracts, hover the mouse over titles.
B. Bunting and A. S. Murawski, Reachability Types, Traces and Full Abstraction
F. Zaiser, A. S. Murawski and C.-H. L. Ong, Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops POPL 2025 Distinguished Paper Award.
B. Bunting and A. S. Murawski, Contextual Equivalence for State and Control via Nested Data
F. Zaiser, A. S. Murawski and C.-H. L. Ong, Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach
B. Bunting and A. S. Murawski, Operational Algorithmic Game Semantics A. Dixon and A. S. Murawski, Saturating Automata for Game Semantics
G. Li, A. S. Murawski and C.-H. L. Ong, Probabilistic Verification Beyond Context-Freeness
D. Chistikov, S. Kiefer, A. S. Murawski and D. Purser, The Big-O Problem
G. Jaber and A. S. Murawski, Compositional Relational Reasoning via Operational Game Semantics
A. Dixon, R. Lazić, A. S. Murawski and I. Walukiewicz, Verifying Higher-Order Concurrency with Data Automata
G. Jaber and A. S. Murawski, Complete Trace Models of State and Control
A. Dixon, R. Lazić, A. S. Murawski and I. Walukiewicz,
Leafy Automata for Higher-Order Concurrency
A. S. Murawski and N. Tzevelekos,
Game Semantics for Interface Middleweight Java
D. Chistikov, S. Kiefer, A. S. Murawski and D. Purser,
The Big-O Problem for Labelled Markov Chains and Weighted Automata
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, DEQ:
Equivalence Checker for Deterministic Register Automata © Springer-Verlag , 2019.
D. Chistikov, A. S. Murawski and D. Purser, Asymmetric Distances for Approximate Differential Privacy
P. Clairambault and A. S. Murawski, On the expressivity of linear recursion schemes
P. Clairambault, C. Grellois and A. S. Murawski, Linearity in Higher-Order Recursion Schemes , Proceedings of the ACM on Programming Languages 2 (POPL'18), pp 39:1-39:29, 2018.
D. Chistikov, A. S. Murawski and D. Purser, Bisimilarity Distances for Approximate Differential Privacy © Springer-Verlag , 2018.
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata
A. S. Murawski and N. Tzevelekos, Algorithmic Games for Full Ground References , Formal Methods in System Design 52(3), pp 277-314, 2018.
M. Hague, A. S. Murawski, C.-H. L. Ong and O. Serre, Collapsible Pushdown Automata and Recursion Schemes
A. S. Murawski and N. Tzevelekos, Higher-Order Linearisability , Proceedings of the 28th International Conference on Concurrency
Theory (CONCUR'17), Leibniz International Proceedings in Informatics 85, pp 34:1-34:18, 2017
C. Cotton-Barratt, A. S. Murawski and C.-H. L. Ong, ML and Extended Branching VASS © Springer-Verlag , 2017.
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Reachability in Pushdown Register Automata
A. S. Murawski and N. Tzevelekos, An Invitation to Game Semantics
A. S. Murawski and N. Tzevelekos, Nominal Game Semantics
R. Lazić and A. S. Murawski, Contextual Approximation and Higher-Order Procedures © Springer-Verlag , 2016.
A. S. Murawski and N. Tzevelekos, Block Structure vs Scope Extrusion: Between Innocence and Omniscience
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Game Semantic Analysis of Equivalence in IMJ © Springer-Verlag , 2015.
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, A Contextual Equivalence Checker for IMJ* © Springer-Verlag , 2015.
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Bisimilarity in Fresh-Register Automata
C. Cotton-Barratt, D. Hopkins, A. S. Murawski and C.-H. L. Ong, Fragments of ML Decidable by Nested Data Class Memory Automata © Springer-Verlag , 2015.
C. Cotton-Barratt, A. S. Murawski and C.-H. L. Ong, Weak and Nested Class Memory Automata © Springer-Verlag , 2015.
A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Reachability in Pushdown Register Automata © Springer-Verlag , 2014.
A. S. Murawski and N. Tzevelekos, Game Semantics for Nominal Exceptions © Springer-Verlag , 2014.
A. S. Murawski and N. Tzevelekos, Game Semantics for Interface Middleweight Java
P. Clairambault and A. S. Murawski, Boehm Trees as Higher-Order Recursive Schemes , Proceedings of the 33rd Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'13), Leibniz International Proceedings in Informatics 24, pp 91-102, 2013
M. Benedikt, S. Göller, S. Kiefer and A. S. Murawski, Bisimilarity of Pushdown Automata is Nonelementary , Proceedings of the 28th Annual IEEE Symposium on Logic in Computer Science (LICS'13), pp 488-498, IEEE Computer Society Press, 2013.
A. S. Murawski and N. Tzevelekos, Full Abstraction for Reduced ML
A. S. Murawski and N. Tzevelekos, Towards Nominal Abramsky , In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky , Lecture Notes in Computer Science 7860, pp 246-263, © Springer-Verlag , 2013.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, On the Complexity of Equivalence and Minimisation for Q-weighted Automata , Logical Methods in Computer Science, Volume 9, Issue 1, 2013.
A. S. Murawski and N. Tzevelekos, Deconstructing General References via Game Semantics , Proceedings of the 16th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'13), Lecture Notes in Computer Science 7794, pp 241-256, © Springer-Verlag , 2013.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, Algorithmic Probabilistic Game Semantics , Formal Methods in System Design, 43(2), pp 285-312, Springer-Verlag, 2013.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, Three Tokens in Herman's Algorithm , Formal Aspects of Computing, 24(4-6), pp 671-678, Springer-Verlag, 2012.
A. S. Murawski and N. Tzevelekos, Algorithmic Games for Full Ground References , Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12), Lecture Notes in Computer Science 7392, pp 312-324, © Springer-Verlag , 2012.
D. Hopkins, A. S. Murawski and C.-H. L. Ong, HECTOR: An Equivalence Checker for a Higher-Order Fragment of ML , Proceedings of the 24th International Conference on Computer Aided Verification (CAV'12), Lecture Notes in Computer Science 7358, pp 774-780, © Springer-Verlag , 2012.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, APEX: An Analyzer for Open Probabilistic Programs , Proceedings of the 24th International Conference on Computer Aided Verification (CAV'12), Lecture Notes in Computer Science 7358, pp 693-698, © Springer-Verlag , 2012.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, On the Complexity of the Equivalence Problem for Probabilistic Automata © Springer-Verlag , 2012.
D. Hopkins, A. S. Murawski and C.-H. L. Ong, A Fragment of ML Decidable by Visibly Pushdown Automata © Springer-Verlag , 2011.
S. Kiefer, A. S. Murawski, J. Ouaknine, J. Worrell and L. Zhang, On Stabilization in Herman's Algorithm © Springer-Verlag , 2011.
S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, Language Equivalence for Probabilistic Automata © Springer-Verlag , 2011.
A. S. Murawski and N. Tzevelekos, Game Semantics for Good General References , Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS'11), pp 75-84, IEEE Computer Society Press, 2011.
A. S. Murawski and N. Tzevelekos, Algorithmic Nominal Game Semantics , Proceedings of the 20th European Symposium on Programming (ESOP'11), Lecture Notes in Computer Science 6602, pp 419-438, © Springer-Verlag , 2011.
A. S. Murawski, Full Abstraction Without Synchronization Primitives , Proceedings of the 26th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXVI), Electronic Notes in Theoretical Computer Science 265, pp 423-436 , Elsevier, 2010.
A. S. Murawski and N. Tzevelekos, Block Structure vs Scope Extrusion: Between Innocence and Omniscience , Proceedings of the 13th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'10), Lecture Notes in Computer Science 6014, pp 33-47, © Springer-Verlag , 2010.
A. S. Murawski and N. Tzevelekos, Full Abstraction for Reduced ML , Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'09), Lecture Notes in Computer Science 5504, pp 32-47, © Springer-Verlag , 2009.
A. S. Murawski, Reachability Games and Game Semantics: Comparing Nondeterministic Programs , Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science (LICS'08), pp 353-363, IEEE Computer Society Press, 2008.
M. Hague, A. S. Murawski, C.-H. L. Ong and O. Serre, Collapsible Pushdown Automata and Recursion Schemes , Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science (LICS'08), pp 452-461, IEEE Computer Society Press, 2008.
A. Legay, A. S. Murawski, J. Ouaknine and J. Worrell, On Automated Verification of Probabilistic Programs , Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08), Lecture Notes in Computer Science 4963, pp 173-187, © Springer-Verlag , 2008.
A. S. Murawski, Bad Variables Under Control , Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic (CSL'07), Lecture Notes in Computer Science 4646, pp 558-572, © Springer-Verlag , 2007.
D. R. Ghica, A. S. Murawski, Compositional Model Extraction for Higher-Order Concurrent Programs , Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'06), Lecture Notes in Computer Science 3920, pp 303-317, © Springer-Verlag , 2006.
A. S. Murawski, Games for complexity of second-order call-by-name programs , Theoretical Computer Science, 343(1/2), pp 207-236, Elsevier, 2005.
A. S. Murawski and J. Ouaknine, On Probabilistic Program Equivalence and Refinement , Proceedings of the 16th International Conference on Concurrency Theory (CONCUR'05), Lecture Notes in Computer Science 3653, pp 156-170, © Springer-Verlag , 2005.
A. S. Murawski, C.-H. L. Ong and I. Walukiewicz, Idealized Algol with Ground Recursion, and DPDA Equivalence , Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp 917-929, © Springer-Verlag , 2005.
A. S. Murawski and I. Walukiewicz, Third-Order Idealized Algol with Iteration is Decidable , Proceedings of the 8th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'05), Lecture Notes in Computer Science 3411, pp 202-218, © Springer-Verlag , 2005.
A. S. Murawski, Functions with local state: regularity and undecidability , Theoretical Computer Science, 338(1/3), pp 315-349, Elsevier, 2005.
A. S. Murawski, About the undecidability of program equivalence in finitary languages with state , ACM Transactions on Computational Logic, 6(4), pp 701-726, ACM Press, 2005.
A. S. Murawski and C.-H. L. Ong, Fast verification of MLL proof-nets via IMLL , ACM Transactions on Computational Logic, 7(3), pp 473-498, ACM Press, 2006.
A. S. Murawski and C.-H. L. Ong, On an interpretation of safe recursion in light affine logic , Theoretical Computer Science, 318(1/2), pp 197-223, Elsevier, 2004.
D. R. Ghica, A. S. Murawski and C.-H. L. Ong, Syntactic control of concurrency , Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp 683-694, © Springer-Verlag , 2004.
S. Abramsky, D. R. Ghica, A. S. Murawski, C.-H. L. Ong and I. D. B. Stark, Nominal games and full abstraction for the nu-calculus , Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), pp 150-159, IEEE Computer Society Press, 2004.
D. R. Ghica and A. S. Murawski, Angelic semantics of fine-grained concurrency , Proceedings of the 7th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'04), Lecture Notes in Computer Science 2987, pp 211-225, © Springer-Verlag , 2004.
S. Abramsky, D. R. Ghica, A. S. Murawski and C.-H. L. Ong, Applying Game Semantics to Compositional Software Modelling and Verification , Proceedings of the 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'04), Lecture Notes in Computer Science 2988, pp 421-435, © Springer-Verlag , 2004.
A. S. Murawski, On program equivalence in languages with ground-type references . Proceedings of 18th IEEE Annual Symposium on Logic in Computer Science (LICS'03), pp 108-117, IEEE Computer Society Press, 2003.
A. S. Murawski and C.-H. L. Ong, Exhausting Strategies, Joker Games and Full Completeness for IMLL with Unit , Theoretical Computer Science 294 (1/2), pp 269-305, Elsevier, 2003.
A. S. Murawski and K. Yi, Static monotonicity analysis for lambda-definable functions over lattices , Proceedings of the 3rd International Workshop on Verification, Model Checking and Abstract Interpretation (VMCAI'02), Lecture Notes in Computer Science 2249, pp 139-153, © Springer-Verlag , 2002.
A. S. Murawski, On Semantic and Type-Theoretic Aspects of Polynomial-Time Computability [abstract]
A. S. Murawski and C.-H. L. Ong, Evolving Games and Essential Nets for Affine Polymorphism , Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (TLCA'01), Lecture Notes in Computer Science 2044, pp 360-375, © Springer-Verlag , 2001.
A. S. Murawski and C.-H. L. Ong, Discreet Games, Light Affine Logic and PTIME Computation , Proceedings of 14th Annual Conference of the European Association of Computer Science Logic (CSL'00), Lecture Notes in Computer Science 1862, pp 427-441, © Springer-Verlag , 2000.
A. S. Murawski and C.-H. L. Ong, Dominator Trees and Fast Verification of Proof Nets . Proceedings of 15th IEEE Annual Symposium on Logic in Computer Science (LICS'00), pp 181-191, IEEE Computer Society Press, 2000.
A. S. Murawski and C.-H. L. Ong, A Linear-time Algorithm for Verifying MLL Proof Nets via Essential Nets , in Davis, Roscoe and Woodcock (editors), Millennial Perspectives in Computer Science, Cornerstones of Computing Series, pp 289-302, Palgrave, 2000.
A. S. Murawski and C.-H. L. Ong, Exhausting Strategies, Joker Games and Full Completeness for IMLL with Unit (preliminary version) , Electronic Notes in Theoretical Computer Science 29, Elsevier, 1999.
