Anthony W. Lin's Publications

On this page, you will find pre-print versions of my writings in a chronological order (recent one first). Author names are often ordered alphabetically as commonly done in theoretical computer science and mathematics, though I also do reverse-alphabetical order just for fun. All papers can be downloaded for personal or research purposes only. If a paper (or a full version thereof) is not available here, you may send me an email to obtain it.

Peer-Reviewed Publications

  1. Probabilistic Bisimulation for Parameterized Systems (with applications to verifying anonymous protocols). In CAV'19. (with Chih-Duo Hong, Rupak Majumdar, and Philipp Ruemmer)
  2. Monadic Decomposability of Regular Relations. In ICALP'19. (with Pablo Barcelo, Chih-Duo Hong, Xuan Bach Le, and Reino Niskanen)
  3. CSS Minification via Constraint Solving. Recently accepted in ACM Transactions of Programming Languages and Systems, to be presented at POPL'19. (with Matthew Hague and Chih-Duo Hong)
  4. Decision Procedures for Path Feasibility of String-Manipulating Programs with Complex Operations. In POPL'19. (with Taolue Chen, Matt Hague, Philipp Rümmer, and Zhilin Wu) [Click here for our solver OSTRICH.]
  5. Complexity Analysis of Tree Share Structure. In APLAS'18. (Joint with Xuan-Bach Le and Aquinas Hobor)
  6. Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility. In ATVA'18. (Joint with Rupak Majumdar)
  7. Decidable models of integer-manipulating programs with recursive parallelism. Accepted in 2018 for publications in Theoretical Computer Science, Special Issue of Reachability Problems (RP) 2016. (with Matthew Hague) [The conference version can be found here]
  8. String Constraints with Concatenation and Transducers Solved Efficiently, In POPL'18. (Joint with Lukas Holik, Petr Janku, Philipp Ruemmer, and Tomas Vojnar)
  9. What is Decidable About String Constraints with ReplaceAll Function, In POPL'18. (Joint with Taolue Chen, Yan Chen, Matthew Hague, and Zhilin Wu)
  10. Learning to Prove Safety over Parameterised Concurrent Systems, In Proceedings of Formal Methods in Computer-Aided Design (FMCAD), 2017. (Joint with Yu-Fang Chen, Chih-Duo Hong, and Philipp Ruemmer)
  11. Fair Termination for Parameterized Probabilistic Concurrent Systems, In Proceedings of 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2017. (Joint with Ondrej Lengal, Rupak Majumdar, and Philipp Ruemmer)
  12. Decidability and Complexity of Tree Share Formulas, In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016. (with Xuan Bach Le and Aquinas Hobor)
  13. Liveness of Randomised Parameterised Systems under Arbitrary Schedulers, In Proceedings of Computer Aided Verification (CAV), 2016. AEC badge (with Philipp Ruemmer) [Click here for the tool SLRP] [Click here for my slides for the conference talk]
  14. String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation XSS. In Proceedings of POPL 2016. (with Pablo Barcelo) [Click here for my slides for the conference talk.]
  15. Regular Symmetry Patterns. In Proceedings of VMCAI 2016. (with Truong Khanh Nguyen, Philipp Ruemmer, and Jun Sun) [Click here for the slides from my conference talk.]
  16. A linear-time algorithm for the orbit problem over cyclic groups. Acta Informatica, 53(5): 493-508 (2016). (with Sanming Zhou) [Full version of a CONCUR'14 paper nominated for Best Paper Award]
  17. Detecting Redundant CSS Rules in HTML5 Applications: A Tree-Rewriting Approach. In Proceedings of OOPSLA, 2015. AEC badge (with Matt Hague and Luke Ong) [Click here for the tool; Click here for the slides from conference talk]
  18. Expressive Path Queries on Graphs with Data. Logical Methods in Computer Science, 11(4): (2015). [Full version of an LPAR'13 paper]. (with Pablo Barcelo and Gaelle Fontaine)
  19. Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems. ACM Transactions on Computational Logic, 15(4): (2014). [Full version of a CONCUR'11 paper] (with Stefan Goller)
  20. Analysis of Probabilistic Basic Parallel Processes. In Proceedings of FoSSaCS, 2014. (with Remi Bonnet and Stefan Kiefer)
  21. Accelerating Tree Automatic Relations. In Proceedings of FSTTCS, 2012.
  22. Weakly-Synchronized Ground Tree Rewriting (with Applications to Verifying Multithreaded Programs). In Proceedings of MFCS, 2012. [Slides]
  23. Synchronisation- and Reversal-Bounded Analysis of Multithreaded Programs with Counters. In Proceedings of CAV, 2012 (with Matthew Hague)
  24. Concurrency Makes Simple Theories Hard. In Proceedings of STACS, 2012. (with Stefan Göller)
  25. Expressive Languages for Path Queries over Graph-structured Data. ACM Transactions on Database Systems 37(4):31 (2012) (with Pablo Barcelo, Leonid Libkin, and Peter Wood)
  26. Model Checking Recursive Programs with Numeric Data Types, In Proceedings of Computer Aided Verification (CAV), 2011. (with Matthew Hague)
  27. The Complexity of Verifying Ground Tree Rewrite Systems, In Proceedings of Logic in Computer Science (LICS), 2011. (with Stefan Göller)
  28. The Complexity of Model Checking (Collapsible) Higher-Order Pushdown Systems, In Proceedings of FSTTCS 2010. (with Matthew Hague)
  29. Parikh Images of Grammars: Complexity and Applications, In Proceedings of Logic in Computer science (LICS), 2010. (with Eryk Kopczynski)
  30. Parikh Images of Regular Languages: Complexity and Applications, accepted at LICS'10 after merging. (Kleene Award for Best Student Paper) (arXiv link)
  31. Algorithmic metatheorems for decidable LTL model checking over infinite systems, In Proceedings of Foundations of Software Science and Computation Structures (FoSSaCS), 2010. (with Leonid Libkin)
  32. Logical Queries over Views: Decidability and Expressiveness, ACM Transactions on Computational Logic 11(2): (2010). (with James Bailey and Guozhu Dong)
  33. Model checking FO(R) over one-counter processes and beyond, In Proceedings of Computer Science Logic (CSL), 2009.
  34. On the Computational Complexity of Verifying One-Counter Processes, In Proceedings of Logic in Computer Science (LICS), 2009. (with Stefan Göller and Richard Mayr)
  35. Unary finite automata vs. arithmetic progressions, Information Processing Letters, 2009.
  36. Recurrent Reachability Analysis in Regular Model Checking, In Proceedings of 15th International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR), 2008. (with Leonid Libkin)


  1. Model Checking Infinite-State Systems: Generic and Specific Approaches. PhD thesis, School of Informatics, University of Edinburgh, August 2010.
  2. On Unary-conjunctive-view Queries. Undergraduate thesis, Department of Computer Science and Software Engineering, University of Melbourne, 2004.


  1. Book review of Algebraic Complexity Theory. Appeared in ACM SIGACT Newsletter, Issue 2, June 2006.
  2. The Limits of Computations, appeared in the February edition of the Journal of Young Investigators 2004. (ps|pdf)
  3. Book review of Algorithms Sequential and Parallel A Unified Approach. Appeared in ACM SIGACT Newsletter, issue 2, June 2003. (view)

Anthony Widjaja Lin

Last Modified: May 2019