Conference Proceedings

  1. Piotr Hofmann, Slawomir Lasota, Richard Mayr, Patrick Totzke. Simulation over One-Counter Nets is PSPACE-complete. Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). IIT Guwahati, India. 2013. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2013 LIPIcs ISBN 978-3-939897-64-4.

  2. Richard Mayr and Patrick Totzke. Branching-Time Model Checking Gap-Order Constraint Systems. The 7th International Workshop on Reachability Problems. RP 2013. Uppsala, Sweden. 2013. (See also arxiv).

  3. Parosh Aziz Abdulla, Richard Mayr, Arnaud Sangnier, Jeremy Sproston. Solving Parity Games on Integer Vectors. 24th International Conference on Concurrency Theory (CONCUR 2013). Buenos Aires, Argentina. 2013. Full version: University of Edinburgh Technical Report EDI-INF-RR-1417 . (See also arXiv and Local copy.)

  4. Parosh Aziz Abdulla, Lorenzo Clemente, Richard Mayr, Sven Sandberg. Stochastic Parity Games on Lossy Channel Systems. 10th International Conference on Quantitative Evaluation of SysTems (QEST 2013). Buenos Aires, Argentina. 2013. Full version: University of Edinburgh Technical Report EDI-INF-RR-1416 . (See also arXiv and Local copy.)

  5. Piotr Hofman, Richard Mayr and Patrick Totzke. Decidability of Weak Simulation on One-counter Nets. 28th Annual IEEE Symposium on Logic in Computer Science (LICS 2013). New Orleans, USA. 2013. Full version: University of Edinburgh Technical Report EDI-INF-RR-1415 . (See also arXiv and Local copy.)

  6. Lorenzo Clemente and Richard Mayr. Advanced Automata Minimization. POPL 2013: 40th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Rome, Italy. Jan. 2013. Full version: University of Edinburgh Technical Report EDI-INF-RR-1414 . (See also arXiv and Local copy.)

  7. Parosh Aziz Abdulla and Richard Mayr. Petri Nets with Time and Cost. Infinity 2012. EPTCS volume 107, pages 9-24. 2012. Link to the paper.

  8. Parosh Aziz Abdulla, Yu-Fang Chen, Lorenzo Clemente, Lukas Holik, Chih-Duo Hong, Richard Mayr, Tomas Vojnar. Advanced Ramsey-based Buchi Automata Inclusion Testing . Proc. of CONCUR 2011, 22nd International Conference on Concurrency Theory. Aachen, Germany. Volume 6901 in LNCS. 2011.

  9. Parosh Aziz Abdulla and Richard Mayr. Computing Optimal Coverability Costs in Priced Timed Petri Nets . 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011). Toronto, Canada. 2011. arXiv.org .

  10. Lorenzo Clemente and Richard Mayr. Multipebble Simulations for Alternating Automata . Proc. of CONCUR 2010, 21st International Conference on Concurrency Theory. Paris, France. Volume 6269 in LNCS. 2010. (This is the long version with the appendix, i.e., University of Edinburgh Technical Report EDI-INF-RR-1376. )

  11. Parosh Aziz Abdulla, Yu-Fang Chen, Lorenzo Clemente, Lukas Holik, Chih Duo Hong, Richard Mayr and Tomas Vojnar. Simulation Subsumption in Ramsey-based Büchi Automata Universality and Inclusion Testing. Proc. of CAV 2010. 22nd International Conference on Computer Aided Verification. Edinburgh, UK. Volume 6174 in LNCS. 2010.

  12. Parosh Aziz Abdulla, Yu-Fang Chen, Lukas Holik, Richard Mayr and Tomas Vojnar. When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata). Proc. of TACAS 2010, Sixteenth International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Paphos, Cyprus. Volume 6015 in LNCS. 2010. (EATCS Best Theory Paper Award, 2010.)

  13. Stefan Göller, Richard Mayr and Anthony Widjaja To. On the Computational Complexity of Verifying One-Counter Processes. 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009). Los Angeles, USA. IEEE. 2009.

  14. Parosh Aziz Abdulla and Richard Mayr. Minimal Cost Reachability/Coverability in Priced Timed Petri Nets. Proc. FOSSACS 2009, 12th International Conference on Foundations of Software Science and Computation Structures. York, UK. Volume 5504 in LNCS. 2009.

  15. Parosh Aziz Abdulla, Noomene Ben Henda, Luca de Alfaro, Richard Mayr, and Sven Sandberg. Stochastic Games with Lossy Channels. Proc. FOSSACS 2008, 11th International Conference on Foundations of Software Science and Computation Structures. Budapest, Hungary. Volume 4962 in LNCS. 2008. (Here is the technical report with the full proofs.)

  16. Parosh Abdulla, Noomene Ben Henda, Richard Mayr and Sven Sandberg. Eager Markov Chains. Fourth international symposium on Automated Technology for Verification and Analysis (ATVA 2006). Beijing, China. Volume 4218 in LNCS. 2006.

  17. Parosh Abdulla, Noomene Ben Henda, Richard Mayr and Sven Sandberg. Limiting Behavior of Markov Chains with Eager Attractors. 3rd International Conference on the Quantitative Evaluation of SysTems (QEST) 2006. University of California, Riverside, USA. IEEE. 2006.

  18. Parosh Abdulla, Noomene Ben Henda and Richard Mayr. Verifying Infinite Markov Chains with a Finite Attractor or the Global Coarseness Property. Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005). Chicago, USA. IEEE. 2005.

  19. Javier Esparza, Antonin Kucera and Richard Mayr. Quantitative Analysis of Probabilistic Pushdown Automata: Expectations and Variances. Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005). Chicago, USA. IEEE. 2005.

  20. Parosh Abdulla, Pritha Mahata and Richard Mayr. Decidability of Zenoness, Syntactic Boundedness and Token-Liveness for Dense-Timed Petri Nets. 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Chennai, India. Volume 3328 in LNCS. Springer Verlag. 2004. (Here is the complete version with the appendix containing the proofs.)

  21. Javier Esparza, Antonin Kucera and Richard Mayr. Model Checking Probabilistic Pushdown Automata. Nineteenth Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE (LICS 2004). Turku, Finland. IEEE. 2004. (The journal version has appeared in LMCS.)

  22. Antonin Kucera and Richard Mayr. A Generic Framework for Checking Semantic Equivalences between Pushdown Automata and Finite-State Automata. In proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (IFIP TCS 2004, Toulouse, France), pages 395-408, Kluwer, 2004. (There is also a technical report with an extended version.)

  23. Stefan Leue, Richard Mayr, Wei Wei. A Scalable Incomplete Test for the Boundedness of UML RT Models. Tenth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2004). Barcelona, Spain. Volume 2988 in LNCS. Springer Verlag. 2004.

  24. Stefan Leue, Richard Mayr, Wei Wei. A Scalable Incomplete Test for Message Buffer Overflow in Promela Models. 11th International SPIN Workshop on Model Checking of Software (SPIN 2004). Barcelona, Spain. Volume 2989 in LNCS. Springer Verlag. 2004.

  25. Richard Mayr. Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Eindhoven, The Netherlands. Volume 2719 in LNCS. Springer Verlag. 2003.

  26. Richard Mayr. Weak Bisimilarity and Regularity of Context-free Processes is EXPTIME-hard. EXPRESS'03, 10th International Workshop on Expressiveness in Concurrency, Marseille, France. 2003. Electronic Notes in Theoretical Computer Science (ENTCS), volume 96. (An extended journal version has appeared in TCS.)

  27. Antonin Kucera and Richard Mayr. Why is Simulation Harder Than Bisimulation? 13th International Conference on Concurrency Theory (CONCUR 2002), Brno, Czech Republic. Volume 2421 in LNCS. Springer Verlag. 2002. (There is also a technical report with an extended version.)

  28. Antonin Kucera and Richard Mayr. On the Complexity of Semantic Equivalences for Pushdown Automata and BPA. 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Warszawa - Otwock, Poland. Volume 2420 in LNCS. Springer Verlag. 2002. (There is also a technical report with the complete proofs.)

  29. Ahmed Bouajjani and Peter Habermehl and Richard Mayr. Automatic Verification of Recursive Procedures with one Integer Parameter. 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), Marianske Lazne, Czech Republic. Volume 2136 in LNCS. Springer Verlag. 2001. ( Abstract in English and French.) ( Journal version has appeared in TCS (volume 295).)

  30. Richard Mayr. On the Complexity of Bisimulation Problems for Pushdown Automata. IFIP International Conference on Theoretical Computer Science (IFIP TCS'2000), Sendai, Japan. Volume 1872 in LNCS. Springer Verlag. 2000.

  31. Richard Mayr. On the Complexity of Bisimulation Problems for Basic Parallel Processes. International Colloquium on Automata, Languages and Programming (ICALP'2000), Geneva, Switzerland. Volume 1853 in LNCS. Springer Verlag. 2000.

  32. Richard Mayr. Undecidable Problems in Unreliable Computations. International Symposium on Latin American Theoretical Informatics (LATIN'2000), Punta del Este, Uruguay. Volume 1776 in LNCS. Springer Verlag. 2000. (A longer journal version has appeared in TCS.)

  33. Antonin Kucera and Richard Mayr. Weak Bisimilarity with Infinite-State Systems can be Decided in Polynomial Time. International Conference on Concurrency Theory (CONCUR'99), Eindhoven, The Netherlands. Volume 1664 in LNCS. 1999. (The journal version has appeared in TCS.)

  34. Javier Esparza, Alain Finkel, Richard Mayr. On the Verification of Broadcast Protocols. 14th IEEE Symposium on Logic in Computer Science (LICS'99). Trento, Italy. IEEE. 1999.

  35. Antonin Kucera and Richard Mayr. Simulation Preorder on Simple Process Algebras. International Colloquium on Automata, Languages and Programming (ICALP'99), Prague, Czech Republic. Volume 1644 in LNCS. 1999. (The journal version has appeared in Information and Computation.)

  36. Ahmed Bouajjani and Richard Mayr. Model Checking Lossy Vector Addition Systems. Symposium on Theoretical Aspects of Computer Science (STACS'99), Trier, Germany. Volume 1563 in LNCS, pages 323-333. 1999. (There is also an inofficial extended version. If this topic interests you then you should also read the following related paper. (which has appeared in TCS))

  37. Richard Mayr. Strict Lower Bounds for Model Checking BPA. In MFCS'98 Workshop on Concurrency - Algorithms and Tools, Tech. Report FIMU-RS-98-06, Masaryk University, Brno, Czech Republic, pages 141--148, 1998. (There is an extended version in ENTCS.)

  38. Petr Jancar, Antonin Kucera, Richard Mayr. Deciding Bisimulation-Like Equivalences with Finite-State Processes. International Colloquium on Automata, Languages and Programming (ICALP'98), Aalborg, Denmark. Volume 1443 in LNCS, pages 200-211, 1998. (There is also a journal version in TCS with the complete proofs.)

  39. Richard Mayr. Combining Petri Nets and PA-Processes. Theoretical Aspects of Computer Software (TACS'97), Sendai, Japan. Volume 1281 in LNCS, pages 547-561, 1997.

  40. Richard Mayr. Model Checking PA-Processes. Conference on Concurrency Theory (CONCUR'97), Warsaw, Poland. Volume 1243 in LNCS, pages 332-346, 1997. (The journal version is better. Richard Mayr. Decidability of Model Checking with the Temporal Logic EF. TCS, volume 256, pages 31-62, 2001.)

  41. Richard Mayr. Tableau Methods for PA-Processes. Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX'97), Pont-a-Mousson, France. Volume 1227 in LNAI, pages 276-290. Springer Verlag, 1997.

  42. Richard Mayr. Weak Bisimulation and Model Checking for Basic Parallel Processes. Proc. of FST&TCS'96, Hyderabad, India. Number 1180 in LNCS, pages 88-99. Springer Verlag, 1996. (This is an old paper. If you are interested in the model-checking part of it then read the chapter on BPP in my PhD thesis. If you are interested in the bisimulation part of it then read the following journal paper (TCS, volume 258, pages 409--433) which contains much more general results.)

  43. Richard Mayr. Semantic reachability for simple process algebras. In B. Steffen and T. Margaria, editors, Proceedings of INFINITY'96, Pisa, Italy. Number MIP-9614 in Technical report series of the University of Passau. 1996.

Journals

  1. Parosh Aziz Abdulla and Richard Mayr. Priced Timed Petri Nets. Logical Methods in Computer Science. Volume 9, Issue 4, Paper 10. 2013. ( Local copy available.)

  2. Antonin Kucera and Richard Mayr. On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes. Information and Computation. 208(7):772-796, 2010.

  3. S.Heber, R.Mayr, J.Stoye. Common Intervals of Multiple Permutations. Algorithmica 60(2):175-206. 2011. ISSN 0178-4617 (Print), 1432-0541 (Online), DOI 10.1007/s00453-009-9332-1. Local copy , Link .

  4. Parosh Abdulla, Noomene Ben Henda, Richard Mayr. Decisive Markov Chains. Logical Methods in Computer Science. Volume 3, Issue 4, Paper 7. 2007.

  5. Parosh Abdulla, Pritha Mahata, Richard Mayr. Dense-Timed Petri Nets: Checking Zenoness, Token Liveness and Boundedness. Logical Methods in Computer Science. Volume 3, Issue 1, Paper 1. 2007.

  6. Javier Esparza, Antonin Kucera, Richard Mayr. Model Checking Probabilistic Pushdown Automata. Logical Methods in Computer Science. Volume 2, Issue 1, Paper 2. 2006.

  7. Richard Mayr. Weak Bisimilarity and Regularity of Context-free Processes is EXPTIME-hard. TCS, volume 330, pages 553-575, 2005.

  8. Ahmed Bouajjani, Peter Habermehl and Richard Mayr. Automatic Verification of Recursive Procedures with one Integer Parameter. TCS, volume 295/1-3, pages 85-106, 2003.

  9. Antonin Kucera and Richard Mayr. Simulation Preorder over Simple Process Algebras. Information and Computation, 173(2):184-198, 2002.

  10. Richard Mayr. Undecidable Problems in Unreliable Computations. TCS 1-3(297):337-354, 2003.

  11. Antonin Kucera and Richard Mayr. Weak Bisimilarity between Finite-State Systems and BPA or Normed BPP is Decidable in Polynomial Time. TCS, volume 270, pages 677-700, 2001.

  12. Petr Jancar, Antonin Kucera, Richard Mayr. Deciding Bisimulation-Like Equivalences with Finite-State Processes. TCS, volume 258, pages 409-433, 2001.

  13. Richard Mayr. Decidability of Model Checking with the Temporal Logic EF. TCS, volume 256, pages 31-62, 2001.

  14. Richard Mayr. Process Rewrite Systems. Information and Computation. Volume 156. Number 1. Pages 264-286. 2000. Postscript-file. , PDF-file. (There is also a paper in INFINITY'98 about a related topic: Richard Mayr and Michael Rusinowitch. Reachability is decidable for ground AC rewrite systems. )

  15. Richard Mayr and Tobias Nipkow. Higher-Order Rewrite Systems and their Confluence. TCS, volume 192, pages 3-29, 1998.

  16. Richard Mayr. Weak Bisimilarity and Regularity of Context-free Processes is EXPTIME-hard. Electronic Notes in Theoretical Computer Science (ENTCS), volume 96. Proceedings of the Workshop "Expressiveness in Concurrency" (EXPRESS 2003), Barcelona, Spain, 2003.

  17. Richard Mayr. Strict Lower Bounds for Model Checking BPA. Electronic Notes in Theoretical Computer Science (ENTCS), volume 18. Extended version of a paper in the MFCS'98 Workshop on Concurrency - Algorithms and Tools, Masaryk University, Brno, Czech Republic, 1998.

  18. Richard Mayr. Process Rewrite Systems. Electronic Notes in Theoretical Computer Science (ENTCS), volume 7. Proceedings of the Workshop "Expressiveness in Concurrency" (EXPRESS'97), Santa Margherita Ligure, Italy, 1997.

  19. Richard Mayr. Semantic reachability. Electronic Notes in Theoretical Computer Science (ENTCS), volume 5. Extended version of the proceedings of the Workshop on the Verification of Infinite State Systems (INFINITY'96), Pisa, Italy, 1996.