MODELLING
CONCURRENCY WITH ORDER STRUCTURES AND GENERALIZED TRACES.
It has been shown (implicitly
Lamport 1986,
Gaifman-Pratt 1987, and explicitly
Janicki-Koutny 1991) that general modelling causality requires two relations,
i.e. some relational structure, called ‘order structure’. The first relation is
interpreted as “not later than” in the case when ‘interleavings imply
simultaneity’ (Janicki-Koutny 1993), and “not simultaneously” in the most
general settings (Janicki-Koutny-Kleijn-Mikulski 2015).
When all system runs are assumed to be adequately modeled
by stratified orders
(or step sequences), the names ‘stratified order structures’ (for
the
first relation
interpreted as “not later than”) and ‘generalized stratified order structures’
for the general case.
Concurrent behaviors, i.e. sets of the equivalent system runs, are modeled by ‘comtraces’
(Janicki-Koutny 1995) for the former case, and ‘step
traces’ (Janicki-Koutny-Kleijn-Mikulski 2015,
2016,
2017 and
2019) for the latter case.
Comtraces have been used by (Janicki-Koutny 1995) and especially (Kleijn-Koutny 2004) to define the semantics of inhibitor nets and nets with priorities, and by many others to net synthesis, modeling production systems, asynchronous circuits and real-time systems. Some recent examples of the application of more general step traces can also be found in computational biology, digital graphics, and model checking.
The case when system runs are represented by step sequences (stratified orders)
has been substantially developed and a monograph on order structures, step
traces and their applications to model semantics of concurrent systems, by
Janicki, Koutny, Kleijn,
and Mikulski, has just been submitted to Springer.
Current research in this area involves both remaining open problems (relations
to temporal logics, process semantics, computational complexities, etc.) and
wide areas of applications in modeling properties of structurally complex
concurrent systems.
It was argued by
Wiener in 1914 (and later more formally by
Janicki-Koutny in
1993) that any execution that can be observed by a single observer must be an
interval order.
This implies that the
most precise semantics ought to use interval orders as a model of system runs.
However, generating interval orders directly is problematic for most models of
concurrency, as interval orders do not have a natural sequential representation
(as for example step sequences), so one has to use either
sequence of
beginnings and ends or sequences of antichains.
The former approach led to the concepts of ‘ST-traces’ (Van Glabbeek-Vaandrager
1987, Vogler 2002) and ‘interval sequences’ and ‘interval traces’ on the level
of concurrent behaviours
(Janicki-Yin 2017). The latter has recently been used
to model operational semantics (Janicki-Koutny 2019). All mentioned approaches
assume implicitly or explicitly that ‘interleavings imply simultaneity’.
Relational structures representing ‘interval traces’ are called ‘interval order
structures’ (Janicki-Koutny 1997).
The interval orders case is much less developed than the case where system
runs are represented by step sequences (stratified orders), mainly because of
the
mathematical complexity of all issues. The main open problems that have to be
dealt with first are the following. For the general case, where interleavings
may not imply simultaneity, neither appropriate order structure nor its trace
model exists, it is an open research problem. Also,
no trace model exists for
operational semantics described in terms of sequences of antichains.
Current research involves many open problems in interval orders approach:
complete process semantics, synthesis, application to particular models of
concurrent systems as for instance Petri nets or process algebras, modeling
production systems, etc., all without the assumptions/restrictions needed for
using stratified order structures or interleavings.
LIST OF PUBLICATIONS – CONCURRENCY AND RELATED TOPICS
__________________________________________________________________________________________________________
2022
1. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Paradigms of Concurrency. Observations, Behaviours, and Systems - a Petri Net View, Studies in Computational Intelligence 1020, Springer 2022, 326 pages, doi.org/10.1007/978-3-662-64821-6
2. M. Assiri, R. Janicki, Towards Modeling of Cardiac Pacemakers With Timed Coloured Petri Nets And Related Tools, Proc. of PNSE’2021 (International Workshop on Petri Nets and Software Engineering) Paris, France, June 25-26, 2021, CEUR Workshop Proceedings, Vol. 2907, pp. 1-20.
2021
3. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Relational Structures for Concurrent Behaviours, Theoretical Computer Science 862 (2021) 174-192, doi: 10.1016/j.tcs.2020.10.019
2020
4. R. Janicki, Ł. Mikulski, Algebraic Structure of Step Traces and Interval Traces, Fundamenta Informaticae 175, 1-4 (2020), 253-280
2019
5. R. Janicki, M. Koutny, Operational Semantics, Interval Orders and Sequences of Antichains, Fundamenta Informaticae 169 (2019) 31-55
6. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Classifying Invariant Structures of Step Traces, Journal of Computer and System Sciences 104 (2019), 297-322
7. R. Janicki, On Relationship Between Inhibitor Nets and Activator Nets, ICATPN’2019 (40th International Conference on Application and Theory of Petri Nets), Lecture Notes in Computer Science 11552, Springer 2019, 192-213
2018
8. R. Janicki, J. Kleijn and Ł. Mikulski, A Precise Characterisation of Step Traces and Their Concurrent Histories, Scientific Annals of Computer Science, 28, 2 (2018), 237-267.
9. M. Alqarni, R. Janicki, Interval Semantics for Petri Nets with Inhibitor Arcs, Theoretical Computer Science, 727 (2018) 1-23.
10. R. Janicki, Modeling Operational Semantics with Interval Orders Represented by Sequences of Antichains, Proc. of ICATPN’2018 (39th International Conference on Application and Theory of Petri Nets), Lecture Notes in Computer Science 10877, Springer 2018, 251-271
2017
11. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Invariant Structures and Dependence Relations, Fundamenta Informaticae, 155 (2017) 1-29.
12. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Alphabets of Acyclic Invariant Structures, Fundamenta Informaticae, 154 (2017) 207-224.
13. R. Janicki, X. Yin, Modeling Concurrency With Interval Traces, Information and Computation, 253 (2017) 78-108.
14. R. Janicki, Jetty Kleijn, M. Koutny and Ł. Mikulski, Synthesis of step alphabets for acyclic invariant structures, Proc. of ATAED’2017 (Workshop on Algorithms & Theories for the Analysis of Event Data), Zaragoza, Spain, June 26–27, 2017, CEUR Workshop Proceedings, Vol. 1847, pp. 76-88.
2016
15. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Step Traces, Acta Informatica, 53 (2016) 35-65.
16. E. Assiri, M. Assiri and R. Janicki, Elevator System. A Case Study of Coloured Petri Nets, Proc. of ICAT’16 (International Conference on Advanced Technology & Sciences), Konya, Turkey, September 1-4, 2016, pp. 40-45.
2015
17. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Characterising Concurrent Histories, Fundamenta Informaticae, 139 (2015), 21-42.
18. M. Alqarni, R. Janicki, On Interval Process Semantics of Petri Nets with Inhibitor Arcs, Proc. of ICATPN’2015 (36th International Conference on Application and Theory of Petri Nets), Lecture Notes in Computer Science 9115, Springer 2015, 7-27.
19. R. Janicki, J. Kleijn, M. Koutny and Ł. Mikulski, Order Structures for Subclasses of Generalised Traces, Proc. of LATA’2015 (9th International Conference on Language and Automata Theory and Applications), Lecture Notes in Computer Science 8977, Springer 2015, 689-700.
20. M. Alqarni and R. Janicki, On Modeling Inhibitor Nets with Interval Processes and Interval Traces, Proc. of FCS’2015 (Foundations of Computer Science), Las Vegas, Nevada, USA, July 27-30, 2015, pp. 3-9, CSREA Press.
21. M. Assiri, M. Alqarni and R. Janicki, Modeling Elevator System With Coloured Petri Nets, Proc. of SERP’2015 (Software Engineering Research and Practice), Las Vegas, Nevada, USA, July 27-30, 2015, pp. 183-189, CSREA Press.
2013
22. Ryszard Janicki, Jetty Kleijn, Maciej Koutny and Łukasz Mikulski, Causal Structures for General Concurrent Behaviours, Proc. of CS&P’2013 (Concurrency, Specification and Programming), CEUR Workshops Proceedings, Vol. 1032, pp. 193-205
2012
23. R. Janicki, X. Yin, N. Zubkova, Modeling Interval Order Structures with Partially Commutative Monoids, Proc. of CONCUR’2012 (23rd Intern. Conf. On Concurrency Theory), Lecture Notes in Computer Science 7454, Springer 2012, 425-439
2011
24. R. Janicki, D. T. M. Le, Modelling Concurrency with Comtraces and Generalised Comtraces, Information and Computation 209 (2011), 1355-1389.
2010
25. R. Janicki, J. Kleijn, M. Koutny, Quotient Monoids and Concurrent Behaviours, In Carlos Martin-Vide (ed.), Series: Mathematics, Computing, Language and Life: Frontiers in Mathematical Linguistic and Language Theory - Vol 2 (Scientific Applications of Language Methods), World Scientific, London, 2010, pp. 311-385.
2009
26. R. Janicki, D.T.M. Le, N. Zubkova, Closure Operators for Order Structures, Proc. of FCT’2008 (Fundamentals of Computation Theory), Lecture Notes in Computer Science 5699, Springer 2009, 217-229.
27. R. Janicki, N. Zubkova, On Closure Operator for Interval Order Structures, Proc. of FCS’2009 (Foundations of Computer Science), Las Vegas, Nevada, USA 2009.
2008
28. R. Janicki, Relational Structures Model of Concurrency, Acta Informatica 45,4 (2008), 279-320.
29. R. Janicki, D.T.M. Le, Modelling Concurrency with Quotient Monoids, Proc. of ATPN’2008 (Application and Theory of Petri Nets), Lecture Notes in Computer Science 5062, Springer 2008, 251-269
2005
30. R. Janicki, A Generalisation of Relational Structures Model of Concurrency, Proc. of ICTAC’04 (Intern. Colloquium on Theoretical Aspect of Computing), Lecture Notes in Computer Science 3407, Springer-Verlag 2005, 85-99.
2002
31. G. Guo, R. Janicki, Modelling Concurrent Behaviours by Commutativity and Weak Causality Relations, Proc. of AMAST’02 (Algebraic Methodology and Software Technology), Lecture Notes in Computer Science 2422, Springer 2002, 178-191.
1999
32.
R. Janicki, M. Koutny, On Causality of Nets with Priorities,
Fundamenta Informaticae
38 (1999) 223-255.
35.
38.
1987
62. R. Janicki, "A Formal Semantics for Concurrent Systems with a Priority Relation", Acta Informatica, 24 (1987), 33-55.
63.
P. E. Lauer and R. Janicki, "An Introduction to the MACRO COSY Notation", In
K. Voss, H. J. Genrich, G. Rozenberg (eds.)
Concurrency and Nets: Advances in
Petri Nets, Springer-Verlag, 1987, 284-314.
64. R. Janicki and M. Koutny, "On Equivalent Execution Semantics of Concurrent Systems", In G. Rozenberg (ed.), Advances of Petri Nets '87, Lecture Notes in Computer Science 266 Springer‑Verlag, 1987, 89-103.
1986
65. R. Janicki, P. E. Lauer, M. Koutny and R. Devillers, "Concurrent and Maximally Concurrent Evolution of Non-Sequential Systems", Theoretical Computer Science, 43 (1986), 213-238.
66. R. Janicki, "On the Concept of Concurrency in Computers and Computations", Proceedings of 11th IMACS World Congress on System Simulation and Scientific Computations, in Computer Systems: Performance and Simulation, edited by M. Ruschitzka (North Holland, 1986), 95-102.
1985
67. R. Janicki, "Transforming Sequential Systems into Concurrent Systems", Theoretical Computer Science, 36 (1985), 27-58.
68. R. Janicki, "Equivalence Notion for Path Expressions Systems", Elektron. Informations-verarbeitung und Kybernetik EIK, 21, 6 (1985), 283-295.
69. R. Janicki, P. E. Lauer and R. Devillers, "Maximal Concurrent Evolution of Non-Sequential Systems", Lecture Notes in Computer Science 197, Springer 1985, 268-280.
1984
70. R. Janicki, "Nets, Sequential Components and Concurrency Relations", Theoretical Computer Science, 29 (1984), 87-121.
71. R. Janicki, "A Method for Developing Concurrent Systems", 6th International Symposium on Programming, Lecture Notes in Computer Science 167, Springer 1984, 155-166.
72. R. Janicki, "Mazurkiewicz Trace Semantics for Communicating Sequential Systems", 5th European Workshop on Application and Theory of Petri Nets, Aarhus, Denmark, 1984, 50-71.
73. P. E. Lauer, J. R. Just, R. Janicki, "Modelling the Control Structure for Microprocessor Systems by Means of Petri Nets", Modelling, Identification and Control MIC '84, Innsbruck, Austria, 1984.
1983
74. R. Janicki, P. E. Lauer, J. R. Just, "On the Description of Simple Microprocessor Configurations by Means of Petri Nets", 3rd Symposium on Microcomputer and Microprocessor Applications, Budapest, Hungary, 1983, 909-919.
1982
75. R. Janicki, "On Concurrent Systems and Concurrency Relations", Proceedings of the 8th International Conference on Operating Systems, Visegrad, Hungary, 1982, 43-54.
76. R. Janicki, "Analysis of Concurrent Systems by Means of Concurrency Relations", Proceedings of the 1st AFCET Conference "Mathematics for Computer Science", Paris, France, 1982, 265-272.
77. E. Eberbach and R. Janicki, "A Note on Infinite Sets of Equations and Fixedpoint Semantics of Vectors of Coroutines", Proceedings of the 8th International Conference on Operating Systems, Visegrad, Hungary, 1982, 13-36.
1981
78. R. Janicki, "A Construction of Concurrent Schemes by Means of Sequential Solutions and Concurrency Relations", Formalisation of Programming Concepts, Peniscola, Spain, 1981, Lecture Notes in Computer Science 107, Springer 1981, 327-334.
79. R. Janicki, "On the Design of Concurrent Systems", Proceedings of the 2nd Conference on Distributed Computing Systems. New York: Computer Society Press, 1981, 455-466.
1980
80. R. Janicki, "On Atomic Nets and Concurrency Relations", Mathematical Foundations of Computer Science 1980, Lecture Notes in Computer Science 88, Springer 1980, 320-333.
81. R. Janicki, "An Algebraic Structure of Petri Nets", 4th International Symposium on Programming, Lecture Notes in Computer Science 83, Springer 1980, 177-192.
82. R. Janicki, "Remarks on the Structure of Unmarked Petri Nets", Proceedings of the 6th International Conference on Operating Systems, Visegrad, Hungary, 1980, 141-158.