Step traces

详细信息    查看全文

• 作者：Ryszard Janicki ; Jetty Kleijn ; Maciej Koutny ; Łukasz Mikulski
• 关键词：Trace ; Step trace ; Causality ; Independence ; Simultaneity ; Serialisability ; Sequentialisability ; Interleaving ; Extending concurrency alphabets ; Dependence graph ; Dependence structure ; Invariant order structure
• 刊名：Acta Informatica
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：53
• 期：1
• 页码：35-65
• 全文大小：888 KB
• 参考文献：1.Baldan, P., Busi, N., Corradini, A., Pinna, G.M.: Domain and event structure semantics for Petri nets with read and inhibitor arcs. Inf. Comput. 323, 129–189 (2004)MathSciNet MATH
  2.Biermann, I., Rozoy, B.: Reliable generalized and context dependent commutation relations. In: TAPSOFT’97, Lecture Notes in Computer Science, vol. 1214, pp. 165–176. Springer, Berlin (1997)
  3.Busi, N., Pinna, G.M.: Process semantics for place/transition nets with inhibitor and read arcs. Fundam. Inform. 40(2–3), 165–197 (1999)MathSciNet MATH
  4.Clerbout, M.: Commutations partielles et familles de langages. Ph.D. thesis, University of Lille (1984)
  5.Diekert, V., Gastin, P., Petit, A.: Recognizable complex trace languages. In: MFCS 1991, Lecture Notes in Computer Science, vol. 520, pp. 131–140. Springer, Berlin (1991)
  6.Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)
  7.Gaifman, H., Pratt, V.R.: Partial order models of concurrency and the computation of functions. In: LICS, pp. 72–85. IEEE Computer Society, Silver Spring, MD (1987)
  8.Gastin, P.: Infinite traces. In: Semantics of Systems of Concurrent Processes 1990, Lecture Notes in Computer Science, vol. 469, pp. 277–308. Springer, Berlin (1990)
  9.Hoogeboom, H.J., Rozenberg, G.: Dependence graphs. In: Diekert, V., Rozenberg, G. (eds.) The Book of Traces, pp. 43–67. World Scientific, Singapore (1995)CrossRef
  10.Hoogers, P.W., Kleijn, H.C.M., Thiagarajan, P.S.: A trace semantics for Petri nets. Inf. Comput. 117(1), 98–114 (1995)CrossRef MathSciNet MATH
  11.Hung, D.V., Knuth, E.: Semi-commutations and Petri nets. Theor. Comput. Sci. 64, 67–81 (1989)CrossRef MATH
  12.Janicki, R., Kleijn, J., Koutny, M., Mikulski, Ł.: Causal structures for general concurrent behaviours. In: M.S. Szczuka, L. Czaja, M. Kacprzak (eds.) CS&P, CEUR Workshop Proceedings, vol. 1032, pp. 193–205. CEUR-WS.org (2013)
  13.Janicki, R., Kleijn, J., Koutny, M., Mikulski, Ł.: Generalising traces. TR-CS 1436, Newcastle University (2014)
  14.Janicki, R., Kleijn, J., Koutny, M., Mikulski, Ł.: Characterising concurrent histories. Fundam. Inform. 139, 21–42 (2015)CrossRef MathSciNet
  15.Janicki, R., Kleijn, J., Koutny, M., Mikulski, L.: Order structures for subclasses of generalised traces. In: LATA 2015, Lecture Notes in Computer Science, vol. 8977, pp. 689–700. Springer, Berlin (2015)
  16.Janicki, R., Koutny, M.: Invariants and paradigms of concurrency theory. In: PARLE 1991, Lecture Notes in Computer Science, vol. 506, pp. 59–74. Springer, Berlin (1991)
  17.Janicki, R., Koutny, M.: Structure of concurrency. Theor. Comput. Sci. 112(1), 5–52 (1993)CrossRef MathSciNet MATH
  18.Janicki, R., Koutny, M.: Semantics of inhibitor nets. Inf. Comput. 123(1), 1–16 (1995)CrossRef MathSciNet MATH
  19.Janicki, R., Le, D.T.M.: Modelling concurrency with comtraces and generalized comtraces. Inf. Comput. 209(11), 1355–1389 (2011)CrossRef MathSciNet MATH
  20.Janicki, R., Yin, X., Zubkova, N.: Modeling interval order structures with partially commutative monoids. In: CONCUR 2012, Lecture Notes in Computer Science, vol. 7454, pp. 425–439. Springer, Berlin (2012)
  21.Juhás, G., Lorenz, R., Mauser, S.: Causal semantics of algebraic Petri nets distinguishing concurrency and synchronicity. Fundam. Inform. 86(3), 255–298 (2008)MATH
  22.Juhás, G., Lorenz, R., Mauser, S.: Complete process semantics of Petri nets. Fundam. Inform. 87(3–4), 331–365 (2008)MATH
  23.Juhás, G., Lorenz, R., Neumair, C.: Synthesis of controlled behavior with modules of signal nets. In: ICATPN 2004, Lecture Notes in Computer Science, vol. 3099, pp. 238–257. Springer, Berlin (2004)
  24.Kleijn, J., Koutny, M.: Formal languages and concurrent behaviours. In: Enguix, G.B., Jiménez-López, M.D., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications, Studies in Computational Intelligence, vol. 113, pp. 125–182. Springer, Berlin (2008)
  25.Kleijn, J., Koutny, M.: Mutex causality in processes and traces of general elementary nets. Fundam. Inform. 122(1–2), 119–146 (2013)MathSciNet MATH
  26.Kuske, D., Morin, R.: Pomsets for local trace languages—recognizability, logic & Petri nets. In: CONCUR 2000, Lecture Notes in Computer Science, vol. 1877, pp. 426–441. Springer, Berlin (2000)
  27.Lamport, L.: The mutual exclusion problem: part I—a theory of interprocess communication. J. ACM 33(2), 313–326 (1986)CrossRef MathSciNet MATH
  28.Le, D.T.M.: On three alternative characterizations of combined traces. Fundam. Inform. 113(3–4), 265–293 (2011)MATH
  29.Mazurkiewicz, A.: Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University (1977)
  30.Mazurkiewicz, A.W.: Trace theory. In: Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Lecture Notes in Computer Science, vol. 255, pp. 279–324. Springer, Berlin (1987)
  31.Mazurkiewicz, A.W.: Basic notions of trace theory. In: J.W. de Bakker, W.P. de Roever, G. Rozenberg (eds.) REX Workshop, Lecture Notes in Computer Science, vol. 354, pp. 285–363. Springer, Berlin (1988)
  32.Mikulski, Ł., Koutny, M.: Folded Hasse diagrams of combined traces. Inf. Process. Lett. 114(4), 208–216 (2014)CrossRef MathSciNet MATH
  33.Nielsen, M., Plotkin, G.D., Winskel, G.: Petri nets, event structures and domains. Part I. Theor. Conput. Sci. 13, 85–108 (1981)CrossRef MathSciNet MATH
  34.Penczek, W., Kuiper, R.: Traces and logic. In: Diekert, V., Rozenberg, G. (eds.) The Book of Traces, pp. 307–390. World Scientific, Singapore (1995)CrossRef
  35.Pratt, V.: Modeling concurrency with partial orders. Int. J. Parallel Program 15(1), 33–71 (1986)CrossRef MathSciNet MATH
  36.Reinhardt, K.: On the synchronization of semi-traces. In: Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 965, pp. 393–403. Springer, Berlin (1995)
  37.Rozenberg, G., Engelfriet, J.: Elementary net systems. In: Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science, vol. 1491, pp. 12–121. Springer, Berlin (1998)
  38.Shields, M.: Adequate path expressions. In: G. Kahn (ed.) Semantics of Concurrent Computation, Lecture Notes in Computer Science, vol. 70, pp. 249–265. Springer, Berlin (1979)
  39.Szpilrajn, E.: Sur l’extension de l’ordre partiel. Fundam. Math. 16, 386–389 (1930)MATH
  40.Thiagarajan, P., Walukiewicz, I.: An expressively complete linear time temporal logic for Mazurkiewicz traces. Inf. Comput. 179(2), 230–249 (2002)CrossRef MathSciNet MATH
  41.Vogler, W.: A generalization of trace theory. RAIRO Infornatique théorique et applications 25(2), 147–156 (1991)MathSciNet MATH
  42.Vogler, W.: Partial order semantics and read arcs. Theor. Comput. Sci. 286(1), 33–63 (2002)CrossRef MathSciNet MATH
  
• 作者单位：Ryszard Janicki (1)
  Jetty Kleijn (2)
  Maciej Koutny (3)
  Łukasz Mikulski (4)
  
  1. Department of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1, Canada
  2. LIACS, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
  3. School of Computing Science, Newcastle University, Newcastle upon Tyne, NE1 7RU, UK
  4. Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, Toruń, Poland
  
• 刊物类别：Computer Science
• 刊物主题：Logics and Meanings of Programs
  Computer Systems Organization and Communication Networks
  Software Engineering, Programming and Operating Systems
  Data Structures, Cryptology and Information Theory
  Theory of Computation
  Information Systems and Communication Service
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0525

文摘

In the classical Mazurkiewicz trace approach the behaviour of a concurrent system is described in terms of sequential observations that differ only with respect to their ordering of independent actions. This paper investigates an extension of the trace model to the case that actions can be observed as occurring simultaneously. Thus observations are sequences of steps, i.e., sets of actions. This leads to a step trace model based on three relations between events: simultaneity, serialisability, and interleaving. Whereas the underlying causal structures of traces are based on dependencies between actions leading to a partial order interpretation, more general causal structures are needed to describe the invariant relationships between the action occurrences in a step trace. We present a complete picture including dependence structures extending dependence graphs, and a characterisation of step traces in terms of invariant order structures. Keywords Trace Step trace Causality Independence Simultaneity Serialisability Sequentialisability Interleaving Extending concurrency alphabets Dependence graph Dependence structure Invariant order structure