Top

Published in:

2018 | OriginalPaper | Chapter

Modeling Operational Semantics with Interval Orders Represented by Sequences of Antichains

Author : Ryszard Janicki

Published in: Application and Theory of Petri Nets and Concurrency

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A representation of interval orders by sequences of antichains is discussed and its relationship to the Fishburn’s representation by sequences of beginnings and endings is analyzed in detail. Using sequences of antichains to model operational semantics of elementary inhibitor nets is also discussed.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Pattern Matching in Link Streams: A Token-Based Approach

next chapter One Net Fits All

‘Operational semantics’ is not a generally agreed concept, in this paper this will be just a collection of all system runs (i.e. executions, observations) [3, 11, 15, 19]. A different meaning is used in for example [4].

For uncountable X it is additionally required that the equivalence relation \(\sim _<\) defined as \(a \sim _<~\!b \iff \forall c\in X. (c<a \Leftrightarrow c<b) \wedge (a<c \Leftrightarrow b<c)\) has countably many equivalence classes [6]. But in this paper we need only a simpler version for countable X, cf. [11].

Inhibitor arcs allow a transition to check for an absence of a token. In principle they allow ‘test for zero’, an operator the standard Petri nets do not have. They were introduced in [1].

Agerwala, T., Flynn, M.: Comments on capabilities, limitations and “correctness” of Petri nets. Comput. Architect. News 4(2), 81–86 (1973)CrossRef

Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26, 832–843 (1983)CrossRef

Baldan, P., Busi, N., Corradini, A., Pinna, G.M.: Domain and event structure semantics for Petri nets with read and inhibitor arcs. Theor. Comput. Sci. 323, 129–189 (2004)MathSciNetCrossRef

Bidoit, M., Hennicker, R., Wirsing, M.: Characterizing behavioural semantics and abstractor semantics. In: Sannella, D. (ed.) ESOP 1994. LNCS, vol. 788, pp. 105–119. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-57880-3_7CrossRef

Cormen, T.H., Leiserson, C.E., Rivest, D.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)MATH

Fishburn, P.C.: Intransitive indifference with unequal indifference intervals. J. Math. Psychol. 7, 144–149 (1970)MathSciNetCrossRef

Fishburn, P.C.: Interval Orders and Interval Graphs. Wiley, New York (1985)MATH

Grabowski, J.: On partial languages. Fundam. Inform. 4(2), 427–498 (1981)MathSciNetMATH

Hopcroft, J.E., Motwani, R., Ullman, J.D.: Automata Theory, Languages, and Computation. Addison-Wesley, Boston (2001)MATH

10.

Janicki, R., Kleijn, J., Koutny, M., Mikulski, Ł.: Step traces. Acta Inform. 53, 35–65 (2016)MathSciNetCrossRef

11.

Janicki, R., Koutny, M.: Structure of concurrency. Theor. Comput. Sci. 112, 5–52 (1993)MathSciNetCrossRef

12.

Janicki, R., Koutny, M.: Semantics of inhibitor nets. Inf. Comput. 123(1), 1–16 (1995)MathSciNetCrossRef

13.

Janicki, R., Yin, X.: Modeling concurrency with interval orders. Inf. Comput. 253, 78–108 (2017)CrossRef

14.

Kleijn, J., Koutny, M.: Process semantics of general inhibitor nets. Inf. Comput. 190, 18–69 (2004)MathSciNetCrossRef

15.

Kleijn, J., Koutny, M.: Formal languages and concurrent behaviours. In: Bel-Enguix, G., Jiménez-López, M.D., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications. SCI, vol. 113, pp. 125–182. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78291-9_5CrossRefMATH

16.

Nielsen, M., Rozenberg, G., Thiagarajan, P.S.: Behavioural notions for elementary net systems. Distrib. Comput. 4, 45–57 (1990)MathSciNetCrossRef

17.

Rozenberg, G., Engelfriet, J.: Elementary net systems. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 12–121. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_14CrossRef

18.

van Glabbeek, R., Vaandrager, F.: Petri net models for algebraic theories of concurrency. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds.) PARLE 1987. LNCS, vol. 259, pp. 224–242. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-17945-3_13CrossRef

19.

Vogler, W.: Partial order semantics and read arcs. Theor. Comput. Sci. 286(1), 33–63 (2002)MathSciNetCrossRef

20.

Wiener, N.: A contribution to the theory of relative position. In: Proceedings of the Cambridge Philosophical Society, vol. 17, pp. 441–449 (1914)

21.

Zuberek, W.M.: Timed Petri nets and preliminary performance evaluation. In: Proceedings of the 7th Annual Symposium on Computer Architecture, La Baule, France, pp. 89–96 (1980)

Title: Modeling Operational Semantics with Interval Orders Represented by Sequences of Antichains
Author: Ryszard Janicki
Publisher: Springer International Publishing
Book: Application and Theory of Petri Nets and Concurrency
Print ISBN: 978-3-319-91267-7

Electronic ISBN: 978-3-319-91268-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-91268-4_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner