Top

Published in:

2020 | OriginalPaper | Chapter

Conditional Bigraphs

Authors : Blair Archibald, Muffy Calder, Michele Sevegnani

Published in: Graph Transformation

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Bigraphs are a universal graph based model, designed for analysing reactive systems that include spatial and non-spatial (e.g. communication) relationships. Bigraphs evolve over time using a rewriting framework that finds instances of a (sub)-bigraph, and substitutes a new bigraph. In standard bigraphs, the applicability of a rewrite rule is determined completely by a local match and does not allow any non-local reasoning, i.e. contextual conditions. We introduce conditional bigraphs that add conditions to rules and show how these fit into the matching framework for standard bigraphs. An implementation is provided, along with a set of examples. Finally, we discuss the limits of application conditions within the existing matching framework and present ways to extend the range of conditions that may be expressed.

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

next chapter Confluence up to Garbage

Bigraphs are not a full category as composition is not defined for non-disjoint supports. We do not discuss support here.

The definition of solid for bigraphs with sharing differs slightly, see [17, Defn 3.6.1].

Bigraphs allow the use of an instantiation map \(\eta \) [15, Defn 8.3] that specifies a mapping of sites in the left-hand side to those in the right-hand site. We do not consider instantiation maps here.

Available, along with the example models of Sect. 5, at www.dcs.gla.ac.uk/~michele/bigrapher.html.

Standard bigraphs are output-linear.

Alrimawi, F., Pasquale, L., Nuseibeh, B.: On the automated management of security incidents in smart spaces. IEEE Access 7, 111513–111527 (2019)CrossRef

Archibald, B., Shieh, M., Hu, Y., Sevegnani, M., Lin, Y.: BigraphTalk: verified design of IoT applications. IEEE Internet Things J. 7(4), 2955–2967 (2020). https://doi.org/10.1109/JIOT.2020.2964026. ISSN 2372-2541CrossRef

Baeten, J.C.M., Bergstra, J.A., Klop, J.W., Weijland, W.P.: Term-rewriting systems with rule priorities. Theor. Comput. Sci. 67(2&3), 283–301 (1989)MathSciNetCrossRefMATH

Benford, S., Calder, M., Rodden, T., Sevegnani, M.: On lions, impala, and bigraphs: modelling interactions in physical/virtual spaces. ACM Trans. Comput. Hum. Interact. 23(2), 1–56 (2016)CrossRef

Bruggink, H.J.S., Cauderlier, R., Hülsbusch, M., König, B.: Conditional reactive systems. In: FSTTCS, pp. 191–203 (2011)

Calder, M., Koliousis, A., Sevegnani, M., Sventek, J.S.: Real-time verification of wireless home networks using bigraphs with sharing. Sci. Comput. Program. 80, 288–310 (2014)CrossRef

Ciancia, V., Latella, D., Loreti, M., Massink, M.: Specifying and verifying properties of space. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 222–235. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44602-7_18

Conforti, G., Macedonio, D., Sassone, V.: Spatial logics for bigraphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 766–778. Springer, Heidelberg (2005). https://doi.org/10.1007/11523468_62

Ehrig, H.: Bigraphs meet double pushouts. Bull. EATCS 78, 72–85 (2002)MathSciNetMATH

10.

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2CrossRefMATH

11.

Habel, A., Heckel, R., Taentzer, G.: Graph grammars with negative application conditions. Fundam. Inform. 26(3/4), 287–313 (1996)MathSciNetCrossRefMATH

12.

Habel, A., Pennemann, K.-H.: Nested constraints and application conditions for high-level structures. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling, Essays Dedicated to Hartmut Ehrig on the Occasion of His 60th Birthday. LNCS, vol. 3393, pp. 293–308. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31847-7_17

13.

Krivine, J., Milner, R., Troina, A.: Stochastic bigraphs. Electron. Notes Theor. Comput. Sci. 218, 73–96 (2008)CrossRefMATH

14.

Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. Theor. Comput. Sci. 96(1), 73–155 (1992)MathSciNetCrossRefMATH

15.

Milner, R.: The Space and Motion of Communicating Agents. Cambridge University Press, Cambridge (2009)CrossRefMATH

16.

Muffy, C., Michele, S.: Modelling IEEE 802.11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing. Form. Asp. Comput. 26(3), 537–561 (2014). https://doi.org/10.1007/s00165-012-0270-3. ISSN 0934-5043

17.

Sevegnani, M.: Bigraphs with sharing and applications in wireless networks. Ph.D. thesis, School of Computing Science, University of Glasgow (2012)

18.

Sevegnani, M., Calder, M.: Bigraphs with sharing. Theor. Comput. Sci. 577, 43–73 (2015)MathSciNetCrossRefMATH

19.

Sevegnani, M., Calder, M.: BigraphER: rewriting and analysis engine for bigraphs. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9780, pp. 494–501. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41540-6_27

20.

Sevegnani, M., Kabác, M., Calder, M., McCann, J.A.: Modelling and verification of large-scale sensor network infrastructures. In: ICECCS, pp. 71–81 (2018)

21.

Sobociński, P.: Deriving process congruences from reaction rules. Ph.D. thesis, Aarhus University (2004)

22.

Tsigkanos, C., Kehrer, T., Ghezzi, C.: Modeling and verification of evolving cyber-physical spaces. In: ESEC/FSE, pp. 38–48 (2017)

Title: Conditional Bigraphs
Authors: Blair Archibald
Muffy Calder
Michele Sevegnani
Publisher: Springer International Publishing
Book: Graph Transformation
Print ISBN: 978-3-030-51371-9

Electronic ISBN: 978-3-030-51372-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-51372-6_1

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