Variable ordering heuristics are essential for making symbolic model checking more efficient. In the current setup, the symbolic model checking tools in mCRL2 (www.mcrl2.org) do not automatically adjust the variable ordering. Instead, they allow users to specify a custom variable ordering via the command line. mCRL2 also includes a script that optimizes variable ordering using a hill-climbing approach.

In this project, you will explore various variable ordering heuristics found in existing literature, such as FORCE or sparse matrix algorithms that aim to reduce bandwidth or wavefront. You will select one of these heuristics, implement it, and evaluate its performance using a set of representative model checking examples in mCRL2. Your findings, including a comparison with the standard variable ordering and mCRL2’s current heuristic, will be documented in a detailed report.

[1] mCRL2 homepage

[2] Groote, J.F. and Mousavi, M.R. (2014) Modeling and analysis of communicating systems. The MIT Press.

[3] Meijer, J. et al. (2014) ‘Read, write and copy dependencies for symbolic model checking’, in E. Yahav (ed.) Hardware and Software: Verification and Testing. Cham: Springer International Publishing (Lecture Notes in Computer Science), pp. 204–219. Available at: https://doi.org/10.1007/978-3-319-13338-6_16.

[4] Meijer, J. and van de Pol, J. (2016) ‘Bandwidth and Wavefront Reduction for Static Variable Ordering in Symbolic Reachability Analysis’, in S. Rayadurgam and O. Tkachuk (eds) NASA Formal Methods. Cham: Springer International Publishing, pp. 255–271. Available at: https://doi.org/10.1007/978-3-319-40648-0_20.