Visualisation of concurrent processes

• Autorzy: Mikulski Ł , Piątkowski M.
• Języki publikacji: EN

Abstrakty

EN

Mazurkiewicz traces are a widely used model for describing the languages of concurrent systems computations. The causal structure of atomic actions occurring in a process modeled as a trace generates a partial order. Hasse diagrams of such order are very common structures used for presentation and investigation in the concurrency theory, especially from the behavioural perspective. We present effective algorithms for Hasse diagrams construction and transformation. Later on, we use them for enumeration of all linearisations of the partial order that represents a concurrent process. Additionally, we attach the flexible visual implementation of all considered Algorithms.

Słowa kluczowe

EN

concurrency; partial order; Hasse diagram; directed acyclic graph; linearisation; Mazurkiewicz traces

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2013
• Tom: Vol. 42, no. 3
• Strony: 699--725
• Opis fizyczny: Bibliogr. 36 poz., rys., wykr.

Twórcy

autor

Mikulski Ł

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University 87-100 Toruń, ul. Chopina 12/18

autor

Piątkowski M.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University 87-100 Toruń, ul. Chopina 12/18

Bibliografia

• 1. Aho, A. V., Garey, M. R. and Ullman, J. D. (1972) The transitive reduction of a directed graph. SICOMP: SIAM Journal on Computing, 1, 131–137.
• 2. Cartier, P. and Foata, D. (1969) Problèmes combinatoires de commutation et réarrangements, LNM 85. Springer, Berlin.
• 3. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001) Introduction to Algorithms. MIT Press, 2 ed.
• 4. Diekert, V. and Rozenberg, G., eds. (1995) The Book of Traces. World Scientific, Singapore.
• 5. Dilworth, R. P. (1950) A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1), 161–166.
• 6. Eve, J. and Kurki-Suonio, R. (1977) On computing the transitive closure of a relation. Acta Informatica, 8, 303–314.
• 7. Freese, R. (2004a) Automated lattice drawing. In: International Conference on Formal Concept Analysis (ICFCA), LNCS 2, 112–127.
• 8. Freese, R. (2004b) Lattice drawing applet. http:/latdraw.org. Retrieved on 12.09.13.
• 9. Ganter, B. and Wille, R. (1999) Formal Concept Analysis: Mathematical Foundations. Springer.
• 10. Garg, A. and Tamassia, R. (1994) Advances in graph drawing. In: CIAC: Italian Conference on Algorithms and Complexity. Springer, 12–21.
• 11. Gastin, P. (1990) Infinite traces. In: Semantics of Systems of Concurrent Processes. LNCS 469, Springer 277–308.
• 12. Graham, R. L., Grötschel, M. and Lovász, L., eds. (1995) Handbook of Combinatorics (vol. 2). MIT Press, Cambridge, MA, USA.
• 13. Grayson, D., Stillman, M. and Eisenbud, D. (2013) Macaulay2 software system v. 1.6. http://www.math.uiuc.edu/Macaulay2/. Retrieved on 12.09.13.
• 14. Greene, C. (2010) Mathematica package for studying posets v. 3.0. http://www.haverford.edu/math/cgreene/posets.html. Retrieved on 12.09.13.
• 15. Hopcroft, J. E. and Ullman, J. D. (1979) Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
• 16. IBM (2008) Infosphere platform http://www-01.ibm.com/software/data/infosphere/. Retrieved on 12.09.13.
• 17. Jipsen, P. (1999) Interactive Poset and Lattice Drawing Java Applet. http://www1.chapman.edu/~jipsen/gap/posets.html. Retrieved on 12.09.13.
• 18. Knuth, D. E. (2005) The Art of Computer Programming: Volume 4, Fascicle 3. Generating All Combinations and Partitions. Addison-Wesley.
• 19. MathWorks (2013) MATLAB – the language for technical computing v. 5.01. http://www.mathworks.com/products/matlab/. Retrieved on 12.09.13.
• 20. Mazurkiewicz, A. (1977) Concurrent program schemes and their interpretations. Daimi report pb-78, Aarhus University.
• 21. Mikulski, Ł. (2008) Projection representation of Mazurkiewicz traces. Fundamenta Informaticae, 85, 399–408.
• 22. Mikulski, Ł. and Koutny, M. (2011) Hasse diagrams of combined traces. Technical report cs-tr-1301, Newcastle University.
• 23. Mikulski, Ł. and Piątkowski, M. (2012) Diadem – Hasse diagram demon strator. http://folco.mat.umk.pl/DiaDem/. Retrieved on 12.09.13.
• 24. Mikulski, Ł., Piątkowski, M. and Smyczyński, S. (2011) Algorithmics of posets generated by words over partially commutative alphabets. In: J. Holub, and J. Ž’árek, eds. Proceedings of the Prague Stringology Conference 2011. Czech Technical University in Prague, Prague, 209–219.
• 25. O’Madadhain, J., Fisher, D. and Nelson, T. (2010) JUNG: Java Universal Network/Graph Framework v. 2.0.1. http://jung.sourceforge.net/. Retrieved on 12.09.13.
• 26. Petri, C. A. (1962) Kommunikation mit Automaten. Ph.D. thesis, University of Bonn, Bonn, Germany.
• 27. Poutré, J. A. L. and van Leeuwen, J. (1987) Maintenance of transitive closures and transitive reductions of graphs. In: H. Göttler and H. J. Schneider, eds., Proc. of Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 314, Springer, 106–120.
• 28. Purdom, P. W. (1970) A transitive closure algorithm. BIT, 10, 76–94.
• 29. Rozenberg, G. and Salomaa, A.. eds., (1997) Handbook of Formal Languages, vol. 1: Word, Language, Grammar. Springer-Verlag New York, Inc.
• 30. Snow, J. (2006) JavaScript Lattice Drawing Program. http://estrada.cune.edu/facweb/john.snow/resources/drawLat.html. Retrieved on 12.09.13.
• 31. Stein, W. (2004) Sage mathematical software system. http://www.sagemath.org/doc/reference/index.html. Retrieved on 12.09.13.
• 32. Stembridge, J. (2009) Maple posets package v. 2.4 http://www.math.lsa.umich.edu/˜jrs/maple.html. Retrieved on 12.09.13.
• 33. Stevenson, W. (2007) Operations Management . McGraw-Hill/Irwin, 9th ed.
• 34. Szpilrajn, E. (1930) Sur l’extension de l’ordre partiel. Fundamenta Mathematicae, 16 (1), 386–389.
• 35. Talete (2008) Dart (decision analysis by ranking techniques). http://www.talete.mi.it/products/dart_description.htm. Retrieved on 12.09.13.
• 36. Zimmerman, P. (2001) MuPAD-combinat – algebraic combinatorics packane for MuPAD. http://mupad-combinat.sourceforge.net/. Retrieved on 12.09.13.