Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
Research

Recent Publications

Many of the papers listed below may be downloaded from the authors' web pages.

2021

  • Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare, Qiyi Tang, Franck van Breugel. Computing Probabilistic Bisimilarity Distances for Probabilistic Automata. Logical Methods in Computer Science, 17(1), 2021.
  • Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In Proc. Proc. 35th International Symposium on Distributed Computing, 2021.
  • Syyeda Zainab Fatmi, Xiang Chen, Yash Dhamija, Maeve Wildes, Qiyi Tang, Franck van Breugel. Probabilistic Model Checking of Randomized Java Code. In Proc. 27th International Symposium on Model Checking Software - 27th International Symposium (SPIN), 2021.
  • George Tourlakis, Computability, Springer, 2021.
  • Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun. Constant-time snapshots with applications to concurrent data structures. In Proc. 26th ACM Symposium on Principles and Practice of Parallel Programming, 2021.

2020

  • Qiyi Tang, Franck van Breugel. Deciding probabilistic bisimilarity distance one for probabilistic automata. Journal of Computer and System Sciences 111: 57-84, 2020.

2019

  • Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare, Qiyi Tang, Franck van Breugel. Computing Probabilistic Bisimilarity Distances for Probabilistic Automata. In Proc. 30th International Conference on Concurrency Theory, 2019.
  • Panagiota Fatourou, Elias Papavasileiou, Eric Ruppert. Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019.
  • Niloufar Shafiei. Non-blocking Patricia tries with replace operations. Distributed Computing, 32(5): 423-442, 2019.

2018

  • Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi. Hardness of Function Composition for Semantic Read once Branching Programs. In Proc. Computational Complexity Conference, 2018.
  • Qiyi Tang, Franck van Breugel. Deciding Probabilistic Bisimilarity Distance One for Labelled Markov Chains. In Proc. 30th International Conference on Computer Aided Verification Part 1, 2018.
  • Qiyi Tang, Franck van Breugel. Deciding Probabilistic Bisimilarity Distance One for Probabilistic Automata. In Proc. 29th International Conference on Concurrency Theory, 2018.

2017

  • Franck van Breugel. Probabilistic bisimilarity distances. In ACM SIGLOG News 4(4): 33-51, 2017.
  • Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, Tobias Mömke. Improved analysis of the online set cover problem with advice. Theoretical Computer Science, 689: 96-107, 2017.
  • Eric Ruppert. Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write. In Proc. ACM Symposium on Principles of Distributed Computing, 2017.
  • Ben Spencer, Michael Benedikt, Anders Møller, Franck van Breugel. ArtForm: a tool for exploring the codebase of form-based websites. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis , 2017.
  • Qiyi Tang, Franck van Breugel. Algorithms to Compute Probabilistic Bisimilarity Distances for Labelled Markov Chains. In Proc. 28th International Conference on Concurrency Theory, 2017.

2016

  • James Aspnes, Eric Ruppert. Depth of a random binary search tree with concurrent insertions. In Proc. International Conference on Distributed Computing, 2016.
  • Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi. Upper and Lower Bounds on the Power of Advice. SIAM Journal on Computing, 45(4): 1412-1432, 2016.
  • Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi. Lower bounds for nondeterministic semantic read-once branching programs. In Proc. International Colloquium on Automata, Languages, and Programming, 2016.
  • Qiyi Tang, Franck van Breugel. Computing probabilistic bisimilarity distances via policy iteration. In Proc. International Conference on Concurrency Theory, 2016.

2015

  • Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov, Eric Ruppert. On the space complexity of set agreement. In Proc. ACM Symposium on Principles of Distributed Computing, 2015.
  • Md. Kowsar Hossain, Suprakash Datta, Jeff Edmonds. Ad-ATMA: An efficient MAC protocol for wireless sensor and ad hoc networks. In Proc. International Conference on Ambient Systems, Networks and Technologies, 2015.
  • Niloufar Shafiei. Doubly-linked lists with good amortized complexity. In Proc. 19th International Conference on Principles of Distributed Systems, 2015. This paper won the conference's best paper award.

Publications in Previous Years

Recent Graduate Theses

  • Niloufar Shafiei, Non-Blocking Data Structures Handling Multiple Changes Atomically, Ph.D. thesis, 2015.
  • Nastaran Shafiei, Model-Checking of Distributed Multithreaded Java Applications, Ph.D. thesis, 2014.
  • Stuart Maclean, Advances in Connectivity-Based Positioning for Mobile Wireless Sensor Networks, Ph.D. thesis, 2013.
  • Xiwen Chen, Formal Verification of a Concurrent Binary Search Tree, M.Sc. thesis, 2013.
  • Elise Cormie-Bowins, Measuring Progress of Probabilistic LTL Model Checking, M.Sc. thesis, 2012.
  • Rahul Chaturvedi, Electing and Maintaining Leaders in Populations of Autonomous Agents, M.Sc. thesis, 2012.
  • Xin Zhang, Measuring Progress of Model Checking Randomized Algorithms, M.Sc. thesis, 2010.
  • Niloufar Shafiei, Array-based Lock-free Implementations of Stacks and Queues, M.Sc. thesis, 2007.
  • Babita Sharma, An Algorithm to Quantify Behavioural Similarity between Probabilistic Systems, 2006. (Winner of York University's Thesis Prize.)
  • Anton Belov, Syntactic Characterization of Propositional Satisfiability, M.Sc. thesis, 2005. (Winner of the department's Joseph Liu Thesis Award.)
  • Kien Huynh, Analysis Through Reflection: Walking the EMF Model of BPEL4WS, M.Sc. thesis, 2005.
  • Francisco Kibedi, Adding a Binary Modal Operator to Predicate Logic, M.A. thesis, 2005.
  • Mariya Koshkina, Verification of Business Processes for Web Services, M.Sc. thesis, 2003.
  • Mikhail Fomitchev, Lock-Free Linked Lists and Skip Lists, M.Sc. thesis, 2003. (Winner of York University's Thesis Prize.)

Recent Undergraduate (CSE4080) Projects

  • Trevor Brown, Non-blocking Search Trees, 2010.
  • Nazanin Mirmohammadi, Techniques in Complexity Theory, 2004.
  • Stan Li, Implementing DPE in BPEL4WS, 2003.
  • Hongming Wu, A New Algorithm for Quantitative Verification of Probabilistic Transition Systems, 2002.
Last modified:
2021/10/15 07:09