Operational Semantics, Interval Orders and Sequences of Antichains

• Autorzy: Janicki Ryszard , Koutny Maciej

Identyfikatory

DOI

10.3233/FI-2019-1838

• Języki publikacji: EN

Abstrakty

EN

A representation of interval orders by sequences of antichains is discussed, and its relationship to the Fishburn’s representation by sequences of the beginnings and endings of domain elements is analysed in detail. Moreover, an operational semantics based on sequences of maximal antichains is proposed and investigated for a general class of safe Petri nets with context arcs.

Słowa kluczowe

EN

interval order; operational semantics; Petri net; sequence of maximal antichains; interval sequence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 1-2
• Strony: 31--55
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Janicki Ryszard

• Department of Computing and Software, McMaster University, Hamilton, Ontario, L8S 4K1 Canada

autor

Koutny Maciej

• School of Computing, Newcastle University, Newcastle upon Tyne NE1 7RU, U.K

Bibliografia

• [1] Allen JF. Maintaining knowledge about temporal intervals. Communications of the ACM, 1983; 26(11):832-843. doi:10.1145/182.358434.
• [2] Baldan P, Busi N, Corradini A, and Pinna GM. Domain and event structure semantics for Petri nets with read and inhibitor arcs. Theoretical Computer Science 2004; 323(1-2):129-189. URL https://doi.org/10.1016/j.tcs.2004.04.001.
• [3] Bidoit M, Hennicker R, Wirsing M. Characterizing Behavioural semantics and abstractor semantics. Lecture Notes in Computer Science 1994; 788:105-119. doi:10.1007/3-540-57880-3_7.
• [4] Fishburn PC. Intransitive indifference with unequal indifference intervals. Journal of Mathematical Psychology, 1970; 7(1):144-149. URL https://doi.org/10.1016/0022-2496(70)90062-3.
• [5] Fishburn P C. Interval orders and interval graphs. John Wiley, New York 1985.
• [6] Grabowski J. On partial languages. Fundamenta Informaticae, 1981; 4(1):427-498.
• [7] Janicki R. Modeling operational semantics with interval orders represented by sequences of antichains. Lecture Notes in Computer Science vol. 10877, 2018 pp. 251-271. doi:10.1007/978-3-319-91268-4_13.
• [8] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Step traces. Acta Informatica 2016; 53(1):35-65. doi:10.1007/s00236-015-0244-z.
• [9] Janicki R, Koutny M. Structure of concurrency. Theoretical Computer Science 1993; 112(1):5-52. URL https://doi.org/10.1016/0304-3975(93)90238-0.
• [10] Janicki R, Koutny M. Semantics of inhibitor nets. Information and Computation 1995; 123(1):1-16. URL https://doi.org/10.1006/inco.1995.1153.
• [11] Janicki R, Yin X. Modeling concurrency with interval traces. Information and Computation 2017; 253(1):78-108. URL https://doi.org/10.1016/j.ic.2016.12.009.
• [12] Kleijn J, Koutny M. Process semantics of general inhibitor nets. Information and Computation 2004; 190(1):18-69. URL https://doi.org/10.1016/j.ic.2003.11.002.
• [13] Kleijn J, Koutny M. Formal languages and concurrent behaviour. Studies in Computational Intelligence vol. 113, 2008 pp. 125-182. doi:10.1007/978-3-540-78291-9_5.
• [14] Nielsen M, Rozenberg G, Thiagarajan PS. Behavioural notions for elementary net systems. Distributed Computing 1990; 4(1):45-57. doi:10.1007/BF01783665.
• [15] Rozenberg G, Engelfriet J. Elementary net systems. Lectures on Petri Nets I: Basic models, Lecture Notes in Computer Science vol. 1492, 1998 pp. 12-121. doi:10.1007/3-540-65306-6_14.
• [16] Van Glabbeek RJ, Vaandrager F. Petri net models for algebraic theories of concurrency. Lecture Notes in Computer Science vol. 259, 1987 pp. 224-242. doi:10.1007/3-540-17945-3_13.
• [17] Mazurkiewicz, A. Trace Theory. Advances in Petri Nets. Lecture Notes in Computer Science vol. 255, 1986 pp. 279-324. doi:10.1007/3-540-17906-2_30.
• [18] Vogler W. Partial order semantics and read arcs. Theoretical Compututer Science 2002; 286(1):33-63. doi:10.1016/S0304-3975(01)00234-1.
• [19] Wiener N. A contribution to the theory of relative position. Proc. of the Cambridge Philosophical Society 1914;17:441-449.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).