Top

Published in:

2020 | OriginalPaper | Chapter

Confluence up to Garbage

Authors : Graham Campbell, Detlef Plump

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

The transformation of graphs and graph-like structures is ubiquitous in computer science. When a system is described by graph-transformation rules, it is often desirable that the rules are both terminating and confluent so that rule applications in an arbitrary order produce unique resulting graphs. However, there are application scenarios where the rules are not globally confluent but confluent on a subclass of graphs that are of interest. In other words, non-resolvable conflicts can only occur on graphs that are considered as “garbage”. In this paper, we introduce the notion of confluence up to garbage and generalise Plump’s critical pair lemma for double-pushout graph transformation, providing a sufficient condition for confluence up to garbage by non-garbage critical pair analysis. We apply our results to language recognition by backtracking-free graph reduction, showing how to establish that a graph language can be decided by a system which is confluent up to garbage. We present two case studies with backtracking-free graph reduction systems which recognise a class of flow diagrams and a class of labelled series-parallel graphs, respectively. Both systems are non-confluent but confluent up to garbage.

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 Conditional Bigraphs

next chapter Computing Embeddings of Directed Bigraphs

Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)CrossRefMATH

Bak, C.: GP 2: efficient implementation of a graph programming language. Ph.D. thesis, Department of Computer Science, University of York, UK (2015). https://etheses.whiterose.ac.uk/12586/

Bakewell, A., Plump, D., Runciman, C.: Specifying pointer structures by graph reduction. In: Pfaltz, J.L., Nagl, M., Böhlen, B. (eds.) AGTIVE 2003. LNCS, vol. 3062, pp. 30–44. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-25959-6_3CrossRefMATH

Berstel, J.: Transductions and Context-Free Languages. Vieweg+Teubner, Stuttgart (1979). https://doi.org/10.1007/978-3-663-09367-1CrossRefMATH

Campbell, G.: Efficient graph rewriting. BSc thesis, Department of Computer Science, University of York, UK (2019). https://arxiv.org/abs/1906.05170

Campbell, G., Plump, D.: Efficient recognition of graph languages. Technical report, Department of Computer Science, University of York, UK (2019). https://arxiv.org/abs/1911.12884

Caron, A.-C.: Linear bounded automata and rewrite systems: influence of initial configurations on decision properties. In: Abramsky, S., Maibaum, T.S.E. (eds.) CAAP 1991. LNCS, vol. 493, pp. 74–89. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-53982-4_5CrossRef

Courcelle, B.: The monadic second-order logic of graphs: definable sets of finite graphs. In: van Leeuwen, J. (ed.) WG 1988. LNCS, vol. 344, pp. 30–53. Springer, Heidelberg (1989). https://doi.org/10.1007/3-540-50728-0_34CrossRef

Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303–318 (1965). https://doi.org/10.1016/0022-247X(65)90125-3MathSciNetCrossRefMATH

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.

Ehrig, H., Kreowski, H.-J.: Parallelism of manipulations in multidimensional information structures. In: Mazurkiewicz, A. (ed.) MFCS 1976. LNCS, vol. 45, pp. 284–293. Springer, Heidelberg (1976). https://doi.org/10.1007/3-540-07854-1_188CrossRef

12.

Ehrig, H., Pfender, M., Schneider, H.: Graph-grammars: an algebraic approach. In: Proceedings 14th Annual Symposium on Switching and Automata Theory, SWAT 1973, pp. 167–180. IEEE (1973). https://doi.org/10.1109/SWAT.1973.11

13.

Farrow, R., Kennedy, K., Zucconi, L.: Graph grammars and global program data flow analysis. In: Proceedings 17th Annual Symposium on Foundations of Computer Science, SFCS 1976, pp. 42–56. IEEE (1976). https://doi.org/10.1109/SFCS.1976.17

14.

Fradet, P., Métayer, D.L.: Structured gamma. Sci. Comput. Program 31(2–3), 263–289 (1998). https://doi.org/10.1016/S0167-6423(97)00023-3MathSciNetCrossRefMATH

15.

Habel, A., Müller, J., Plump, D.: Double-pushout graph transformation revisited. Math. Struct. Comput. Sci. 11(5), 637–688 (2001). https://doi.org/10.1017/S0960129501003425MathSciNetCrossRefMATH

16.

Hristakiev, I., Plump, D.: Checking graph programs for confluence. In: Seidl, M., Zschaler, S. (eds.) STAF 2017. LNCS, vol. 10748, pp. 92–108. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-74730-9_8CrossRef

17.

Huet, G.: Confluent reductions: abstract properties and applications to term rewriting systems. J. ACM 27(4), 797–821 (1980). https://doi.org/10.1145/322217.322230MathSciNetCrossRefMATH

18.

Knuth, D., Bendix, P.: Simple word problems in universal algebras. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp. 263–297. Pergamon Press, Oxford (1970). https://doi.org/10.1016/B978-0-08-012975-4.50028-XCrossRef

19.

Lambers, L.: Certifying rule-based models using graph transformation. Ph.D. thesis, Technical University of Berlin, Elektrotechnik und Informatik (2009). https://doi.org/10.14279/depositonce-2348

20.

Lambers, L., Born, K., Orejas, F., Strüber, D., Taentzer, G.: Initial conflicts and dependencies: critical pairs revisited. In: Heckel, R., Taentzer, G. (eds.) Graph Transformation, Specifications, and Nets. LNCS, vol. 10800, pp. 105–123. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-75396-6_6CrossRefMATH

21.

Lambers, L., Ehrig, H., Orejas, F.: Efficient conflict detection in graph transformation systems by essential critical pairs. In: Proceedings Fifth International Workshop on Graph Transformation and Visual Modeling Techniques, GT-VMT 2006, Electronic Notes in Theoretical Computer Science, vol. 211, pp. 17–26. Elsevier (2008). https://doi.org/10.1016/j.entcs.2008.04.026

22.

Lambers, L., Kosiol, J., Strüber, D., Taentzer, G.: Exploring conflict reasons for graph transformation systems. In: Guerra, E., Orejas, F. (eds.) ICGT 2019. LNCS, vol. 11629, pp. 75–92. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23611-3_5CrossRefMATH

23.

Lawler, E.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2, 75–90 (1978). https://doi.org/10.1016/S0167-5060(08)70323-6MathSciNetCrossRefMATH

24.

Monma, C., Sidney, J.: Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4(3), 215–224 (1979). https://doi.org/10.1287/moor.4.3.215MathSciNetCrossRefMATH

25.

Newman, M.: On theories with a combinatorial definition of “equivalence”. Ann. Math. 43(2), 223–243 (1942). https://doi.org/10.2307/1968867MathSciNetCrossRefMATH

26.

Plump, D.: Hypergraph rewriting: critical pairs and undecidability of confluence. In: Sleep, M.R., Plasmeijer, M.J., van Eekelen, M.C. (eds.) Term Graph Rewriting, pp. 201–213. Wiley, Chichester (1993)MATH

27.

Plump, D.: Computing by graph rewriting. Habilitation thesis, Universität Bremen, Fachbereich Mathematik und Informatik (1999)

28.

Plump, D.: Confluence of graph transformation revisited. In: Middeldorp, A., van Oostrom, V., van Raamsdonk, F., de Vrijer, R. (eds.) Processes, Terms and Cycles: Steps on the Road to Infinity. LNCS, vol. 3838, pp. 280–308. Springer, Heidelberg (2005). https://doi.org/10.1007/11601548_16CrossRef

29.

Plump, D.: Reasoning about graph programs. In: Proceedings 9th International Workshop on Computing with Terms and Graphs, TERMGRAPH 2016, Electronic Proceedings in Theoretical Computer Science, vol. 225, pp. 35–44. Open Publishing Association (2016). https://doi.org/10.4204/EPTCS.225.6

Title: Confluence up to Garbage
Authors: Graham Campbell
Detlef Plump
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_2

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