**
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*.

**201**3

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
*(23^{rd} 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

**200**5

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.

**1997**

** Acta Informatica**,

**1995**

** Information and Computation**,

**1994**

35.
*Journal of*
*Information Processing and Cyberneti**cs*,
**30**, 3 (1994), 161-168.

*PARLE'94
*(Parallel Architectures and Languages Europe),
*Lecture Notes in Computer Science*
817,** **Springer 1994, 623-634.

**199**3

** Theoretical Computer Science**,

38. *Proceedings of*
*13th Fundamentals of Software
Technology and Theoretical Computer Science (FSTTC'93*),
*Lecture Notes in Computer Science*** **761, Springer 1993, 348-357.

*Proceedings of Annual CALIBAN*
*Workshop*, Munich, Germany (1993),
83-88.

**1992**

**
Future Generation Computer Systems**,

**
Algebraic Methodology and Software
Technology**, Springer-Verlag, 1992, 98-107.

*CALIBAN Workshop "What Good are*
*Partial Orders?"*, Sheffield, U.K.,
1992, in *Hildesheimer Informatik --
Berichte*,
13/92.

**1991**

** DIMACS Series in Discrete Mathematics
and Theoretical Computer Science**, 3 (1991), 231-250

*
Advances of Petri Nets '91*,

*Proceedings of*
*CAV'90 (Computer Aided Verification*),
*Lecture Notes in Computer Science*
531, Springer 1991.

*Proceedings of CONCUR'91*
*(International Conference on
Concurrency Theory*), *Lecture Notes
in Computer Science* 527, Springer 1991, 317-331.

*Proceedings of PARLE'91*
*(Parallel Architectures and Languages
Europe*), *Lecture Notes in Computer
Science* 506 Springer 1991), 59-74.

*3rd Workshop on*
*Concurrency and Compositionality*,
Goslar, Germany, 1991, 143-144.

*Proceedings of AMAST'91 (Algebraic Methodology and Software Technology)
Workshops in Computing*, Iowa City, Iowa, 1991, 83-86.

*13th IMACS World Congress on
Computation and Applied Mathematics*, Dublin, Ireland (July 1991),
709-713.

**1990**

** Theoretical Computer Science**,

**
Real-Time Systems, Theory and Applications**, North Holland, 1990,
133-142.

*Application and Theory of Petri*
*Nets '90*, Paris, France, June
1990.

*2nd Workshop on*
*Computer-Aided Verification*, Rutgers, New Jersey, June 1990

*18th ACM Computer Science Conference*,
Washington, D.C. (ACM Press, 1990), 147-153.

**1989**

*Parallel
Architectures and Languages Europe '89*,
*Lecture Notes in Computer Science*
366, Springer 1989, 73-88.

*1st International Conference on Algebraic Methodology and Software
Technology AMAST'89*, Iowa City, Iowa 1989, 141-144.

*17th ACM
Computer Science Conference*, Louisville, Kentucky (ACM Press, 1989),
221-231.

**1988**

*CIPS Edmonton.'88
Conference*, Edmonton, 1988, 81-88.

*17th Annual International Conference*
*on Parallel Processing*, Pheasant
Run, Illinois, (Penn State Press, 1988),**
**II, 150-156.

*16th ACM Computer Science*
*Conference*, Atlanta, Georgia (ACM
Press, 1988), 438-446.

**1987**

62.
R. Janicki, "A Formal Semantics for Concurrent Systems with a Priority
Relation", **
Acta Informatica**,

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**,

**1986**

65.
R. Janicki, P. E. Lauer, M. Koutny and R. Devillers, "Concurrent and
Maximally Concurrent Evolution of Non-Sequential Systems",
**
Theoretical Computer Science**,

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**,

68.
R. Janicki, "Equivalence Notion for Path Expressions Systems",
**
Elektron. Informations-verarbeitung
und Kybernetik**

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**,

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.

**198**0

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.

**1979**

**
Mathematical Research**,

**
Fundamenta Informaticae**,

*Lecture
Notes in Computer Science* 70, Springer 1979, 109-122.

**1978**

*Lecture Notes in
Computer Science* 64, Springer 1978, 289-307.

**1977**

**",
Fundamenta Informaticae**,

*Lecture Notes
in Computer Science* 56, Springer 1977, 113-119.

**1976**

*Lecture Notes in Computer
Science* 45, Springer 1976, 377-384.