Publications

Hover the mouse over titles to see abstracts

• A. S. Murawski and N. Tzevelekos, Higher-Order Linearisability, Proceedings of the 28th International Conference on Concurrency Theory (CONCUR), Leibniz International Proceedings in Informatics ??, pp ??-???, 2017
• C. Cotton-Barratt, A. S. Murawski and C.-H. L. Ong, ML and Extended Branching VASS, Proceedings of the 26th European Symposium on Programming (ESOP), Lecture Notes in Computer Science 10201, pp 314-340 © Springer-Verlag, 2017.
• A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Reachability in Pushdown Register Automata, Journal of Computer and System Sciences 87, pp 58-83, 2017.
• A. S. Murawski and N. Tzevelekos, An Invitation to Game Semantics, SIGLOG News 3(2), pp 56-67, 2016.
• A. S. Murawski and N. Tzevelekos, Nominal Game Semantics, Foundations and Trends in Programming Languages 2(4), pp 191-269, 2016.
• R. Lazić and A. S. Murawski, Contextual Approximation and Higher-Order Procedures, Proceedings of the 19th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'16), Lecture Notes in Computer Science 9634, pp 162-179 © Springer-Verlag, 2016.
• A. S. Murawski and N. Tzevelekos, Block Structure vs Scope Extrusion: Between Innocence and Omniscience, Logical Methods in Computer Science 12(3), 2016.
• A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Game Semantic Analysis of Equivalence in IMJ, Proceedings of the 13th International Symposium on Automated Technology for Verification and Analysis (ATVA), Lecture Notes in Computer Science 9364, pp 411-428 © Springer-Verlag, 2015.
• A. S. Murawski, S. J. Ramsay and N. Tzevelekos, A Contextual Equivalence Checker for IMJ*, Proceedings of the 13th International Symposium on Automated Technology for Verification and Analysis (ATVA), Lecture Notes in Computer Science 9364, pp 234-240 © Springer-Verlag, 2015.
• A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Bisimilarity in Fresh-Register Automata, Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp 156-167, IEEE Computer Society Press, 2015.
• C. Cotton-Barratt, D. Hopkins, A. S. Murawski and C.-H. L. Ong, Fragments of ML Decidable by Nested Data Class Memory Automata, Proceedings of the 18th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'15), Lecture Notes in Computer Science 9034, pp 249-263, © Springer-Verlag, 2015.
• C. Cotton-Barratt, A. S. Murawski and C.-H. L. Ong, Weak and Nested Class Memory Automata, Proceedings of 9th International Conference on Language and Automata Theory and Applications (LATA'15), Lecture Notes in Computer Science 8977, pp 188-199, © Springer-Verlag, 2015.
• A. S. Murawski, S. J. Ramsay and N. Tzevelekos, Reachability in Pushdown Register Automata, Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), Lecture Notes in Computer Science 8634 (Part I), pp 464-473, © Springer-Verlag, 2014.
• A. S. Murawski and N. Tzevelekos, Game Semantics for Nominal Exceptions, Proceedings of the 17th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'14), Lecture Notes in Computer Science 8412, pp 164-179, © Springer-Verlag, 2014.
• A. S. Murawski and N. Tzevelekos, Game Semantics for Interface Middleweight Java, Proceedings of 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'14), pp 517-528, 2014.
• 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, Annals of Pure and Applied Logic, 164(11), pp 1118-1143, Elsevier, 2013.
• 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, Proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'12), Lecture Notes in Computer Science 7213, pp 467-481, © Springer-Verlag, 2012.
• D. Hopkins, A. S. Murawski and C.-H. L. Ong, A Fragment of ML Decidable by Visibly Pushdown Automata, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11), Lecture Notes in Computer Science 6756, pp 149-161, © Springer-Verlag, 2011.
• S. Kiefer, A. S. Murawski, J. Ouaknine, J. Worrell and L. Zhang, On Stabilization in Herman's Algorithm, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11), Lecture Notes in Computer Science 6756, pp 466-477, © Springer-Verlag, 2011.
• S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter and J. Worrell, Language Equivalence for Probabilistic Automata, Proceedings of the 23rd International Conference on Computer Aided Verification (CAV'11), Lecture Notes in Computer Science 6806, pp 526-540, © 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 , D.Phil. thesis, University of Oxford, 2001. [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.