Concurrent Depth-First Search Algorithms

1. Armstrong, P., Lowe, G., Ouaknine, J., Roscoe, A.W.: Model checking timed CSP. In: Proceedings of HOWARD-60 (2012)

   Google Scholar 

2. Barnat, J., Chaloupka, J., van de Pol, J.: Distributed algorithms for SCC decomposition. Journal of Logic and Computation 21(1), 23–44 (2011)

   Article  MATH  MathSciNet  Google Scholar 

3. Evangelista, S., Laarman, A., Petrucci, L., van de Pol, J.: Improved multi-core nested depth-first search. In: Chakraborty, S., Mukund, M. (eds.) ATVA 2012. LNCS, vol. 7561, pp. 269–283. Springer, Heidelberg (2012)

   Chapter  Google Scholar 

4. Evangelista, S., Petrucci, L., Youcef, S.: Parallel nested depth-first searches for LTL model checking. In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 381–396. Springer, Heidelberg (2011)

   Chapter  Google Scholar 

5. Fleischer, L.K., Hendrickson, B.A., Pinar, A.: On identifying strongly connected components in parallel. In: Rolim, J.D.P. (ed.) IPDPS-WS 2000. LNCS, vol. 1800, pp. 505–511. Springer, Heidelberg (2000)

   Chapter  Google Scholar 

6. Gibson-Robinson, T., Armstrong, P., Boulgakov, A., Roscoe, A.W.: FDR3 — A modern refinement checker for CSP. In: Ábrahám, E., Havelund, K. (eds.) TACAS 2014. LNCS, vol. 8413, pp. 180–194. Springer, Heidelberg (2014)

   Google Scholar 

7. Laarman, A., van de Pol, J., Weber, M.: Boosting multi-core reachability performance with shared hash tables. In: Proceedings of 10th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2010 (2010)

   Google Scholar 

8. Laarman, A., Langerak, R., van de Pol, J., Weber, M., Wijs, A.: Multi-core nested depth-first search. In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 321–335. Springer, Heidelberg (2011)

   Chapter  Google Scholar 

9. Laarman, A.W., van de Pol, J.C.: Variations on multi-core nested depth-first search. In: Proceedings of the 10th International Workshop on Parallel and Distributed Methods in Verification. Electronic Proceedings in Theoretical Computer Science, vol. 72, pp. 13–28 (2011)

   Google Scholar 

10. Lowe, G.: Implementing generalised alt: A case study in validated design using CSP. In: Communicating Process Architectures (2011)

    Google Scholar 

11. McLendon III, W., Hendrickson, B., Plimpton, S.J., Rauchwerger, L.: Finding strongly connected components in distributed graphs. Journal of Parallel and Distributed Computing 65(8), 901–910 (2005)

    Article  MATH  Google Scholar 

12. Odersky, M., Spoon, L., Venners, B.: Programming in Scala. Artima (2008)

    Google Scholar 

13. Orzan, S.: On Distributed Verification and Verified Distribution. PhD thesis, Free University of Amsterdam (2004)

    Google Scholar 

14. Reif, J.H.: Depth-first search is inherently sequential. Information Processing Letters 20(5), 229–234 (1985)

    Article  MATH  MathSciNet  Google Scholar 

15. Roscoe, A.W.: Theory and Practice of Concurrency. Prentice Hall (1998)

    Google Scholar 

16. Roscoe, A.W.: Understanding Concurrent Systems. Springer (2010)

    Google Scholar 

17. Tarjan, R.: Depth-first search and linear graph algorithms. SIAM Journal of Computing 1(2), 146–160 (1972)

    Article  MATH  MathSciNet  Google Scholar 

18. University of Oxford. Failures-Divergence Refinement—FDR 3 User Manual (2013), http://www.cs.ox.ac.uk/projects/fdr/manual/index.html

19. Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification. In: Proceedings of Logic in Computer Science (1986)

    Google Scholar 

Download references