PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Visualisation of concurrent processes

Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
699--725
Opis fizyczny
Bibliogr. 36 poz., rys., wykr.
Twórcy
autor
  • Faculty of Mathematics and Computer Science Nicolaus Copernicus University 87-100 Toruń, ul. Chopina 12/18
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f6a693ab-bd4d-47ff-be56-11059bfeded1
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.