Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 42 | nr 3 | 699--725
Tytuł artykułu

Visualisation of Concurrent Processes

Treść / Zawartość
Warianty tytułu
Języki publikacji
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. (original abstract)
Opis fizyczny
  • Nicolaus Copernicus University in Toruń, Poland
  • Nicolaus Copernicus University in Toruń, Poland
  • 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.
  • Cartier, P. and Foata, D. (1969) Problèmes combinatoires de commutation et réarrangements, LNM 85. Springer, Berlin.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001) Introduction to Algorithms. MIT Press, 2 ed.
  • Diekert, V. and Rozenberg, G., eds. (1995) The Book of Traces. World Scientific, Singapore.
  • Dilworth, R. P. (1950) A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1), 161-166.
  • Eve, J. and Kurki-Suonio, R. (1977) On computing the transitive closure of a relation. Acta Informatica, 8, 303-314.
  • Freese, R. (2004a) Automated lattice drawing. In: International Conference on Formal Concept Analysis (ICFCA), LNCS 2, 112-127.
  • Freese, R. (2004b) Lattice drawing applet. http:/ Retrieved on 12.09.13.
  • Ganter, B. and Wille, R. (1999) Formal Concept Analysis: Mathematical Foundations. Springer.
  • Garg, A. and Tamassia, R. (1994) Advances in graph drawing. In: CIAC: Italian Conference on Algorithms and Complexity. Springer, 12-21.
  • Gastin, P. (1990) Infinite traces. In: Semantics of Systems of Concurrent Processes. LNCS 469, Springer 277-308.
  • Graham, R. L., Grötschel, M. and Lovász, L., eds. (1995) Handbook of Combinatorics (vol. 2). MIT Press, Cambridge, MA, USA.
  • Grayson, D., Stillman, M. and Eisenbud, D. (2013) Macaulay2 software system v. 1.6. Retrieved on 12.09.13.
  • Greene, C. (2010) Mathematica package for studying posets v. 3.0. Retrieved on 12.09.13.
  • Hopcroft, J. E. and Ullman, J. D. (1979) Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
  • IBM (2008) Infosphere platform Retrieved on 12.09.13.
  • Jipsen, P. (1999) Interactive Poset and Lattice Drawing Java Applet. Retrieved on 12.09.13.
  • Knuth, D. E. (2005) The Art of Computer Programming: Volume 4, Fascicle 3. Generating All Combinations and Partitions. Addison-Wesley.
  • MathWorks (2013) MATLAB - the language for technical computing v. 5.01. Retrieved on 12.09.13.
  • Mazurkiewicz, A. (1977) Concurrent program schemes and their interpretations. Daimi report pb-78, Aarhus University.
  • Mikulski, Ł. (2008) Projection representation of Mazurkiewicz traces. Fundamenta Informaticae, 85, 399-408.
  • Mikulski, Ł. and Koutny, M. (2011) Hasse diagrams of combined traces. Technical report cs-tr-1301, Newcastle University.
  • Mikulski, Ł. and Piątkowski, M. (2012) Diadem - Hasse diagram demonstrator. Retrieved on 12.09.13.
  • 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.
  • O'Madadhain, J., Fisher, D. and Nelson, T. (2010) JUNG: Java Universal Network/Graph Framework v. 2.0.1. Retrieved on 12.09.13.
  • Petri, C. A. (1962) Kommunikation mit Automaten. Ph.D. thesis, University of Bonn, Bonn, Germany.
  • 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.
  • Purdom, P. W. (1970) A transitive closure algorithm. BIT, 10, 76-94.
  • Rozenberg, G. and Salomaa, A.. eds., (1997) Handbook of Formal Languages, vol. 1: Word, Language, Grammar. Springer-Verlag New York, Inc.
  • Snow, J. (2006) JavaScript Lattice Drawing Program. Retrieved on 12.09.13.
  • Stein, W. (2004) Sage mathematical software system. Retrieved on 12.09.13.
  • Stembridge, J. (2009) Maple posets package v. 2.4˜jrs/maple.html. Retrieved on 12.09.13.
  • Stevenson, W. (2007) Operations Management. McGraw-Hill/Irwin, 9th ed.
  • Szpilrajn, E. (1930) Sur l'extension de l'ordre partiel. Fundamenta Mathematicae, 16 (1), 386-389.
  • Talete (2008) Dart (decision analysis by ranking techniques). Retrieved on 12.09.13.
  • Zimmerman, P. (2001) MuPAD-combinat - algebraic combinatorics packane for MuPAD. Retrieved on 12.09.13.
Typ dokumentu
Identyfikator YADDA

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
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ć.