{"entities":{"Q4028126":{"pageid":6057880,"ns":120,"title":"Item:Q4028126","lastrevid":108493058,"modified":"2026-11-06T17:08:52Z","type":"item","id":"Q4028126","labels":{"en":{"language":"en","value":"Algebraic approach to graph transformation based on single pushout derivations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 139800"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4028126$754A76ED-C53D-418E-B270-25B78D0ECCF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db77d3a1059671a3f41e3d9a088e904ab17ffbe4","datavalue":{"value":"0768.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$4BEC354D-1468-4594-A4EE-F5660ACD1FAD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53ab14c2b4ae1cc9c74b5a2d564ba1858518d75d","datavalue":{"value":{"entity-type":"item","numeric-id":631575,"id":"Q631575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4028126$2F0214D9-B4EA-4D0E-90A3-82AD6E3C0AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7932890ff79a7b196908702cdb1b3dc6a332d7d7","datavalue":{"value":{"entity-type":"item","numeric-id":171481,"id":"Q171481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4028126$CD92737E-0D38-43E4-A362-AFA5F3EDFE65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e126f0a627a644e456ce20a058877c46ad749c68","datavalue":{"value":{"time":"+1993-03-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4028126$40DCA4A7-DD8F-431C-9332-F027681C37EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$32F4E7F9-169D-49C2-8E35-8145ED72EDAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f04348da9d1ca8b015ef464713838d83a8af937e","datavalue":{"value":"18A30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$27448818-F3A0-4AC9-8196-85C2A4E195B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$9C174942-6C10-4711-AAFF-21ABE0EFF108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3d53f4f8504531dc1d4f34947ee793dc8e8b2ce8","datavalue":{"value":"08C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$9FCF1DFF-21C3-479E-B6DA-E96CE7C060A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"db2c34644f223015abe9c203f88e343dcc46a9ae","datavalue":{"value":"08A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$E1B90EDA-5F30-4644-9EB0-97B426120328","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5fc735371b00a1d2b13e57b5c6cf0f88e6e39f5","datavalue":{"value":"139800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$08A41B7F-2AC2-472B-AEA2-B94E96766ECF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10aada1bcebcea30af443e4c20bac92e26c0b2a7","datavalue":{"value":"graph grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$82C36F5F-D649-4BF0-9F3B-DB644B817653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffe802cd0c56541564b404252646a442e231b0d8","datavalue":{"value":"graph rewriting","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$9C80B10C-C2D1-4CAF-8C02-61E94D954173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c798d63ba40b6d854308344c43b3bcdfc6d2de9","datavalue":{"value":"category of graphs and partial morphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$76A2D973-EC51-482B-879E-A36524D9FD62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e34a923d04c3d7aaa253aba8d07b842d307c6a3","datavalue":{"value":"partial graph morphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$37FD06CA-886B-498D-AF53-6B6AF92FB819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b63aed76f3ca36142461e42545ec98a2a6d20c","datavalue":{"value":"asynchronous parallel derivations","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$4D198973-6C9B-409C-B55E-C4F0451EF9E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3015c04611548c11d846540947e8efa20c8ff721","datavalue":{"value":"single-pushout approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$69BFCA74-D20D-4D4A-85AD-A42FC870B805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2d9a5fefaeb77b04273828c24865f9ea2d7556d","datavalue":{"value":"categories of algebras and partial homomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$F3D065F9-888A-4EEF-95EB-DB23B9137F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"370afb08886d454ad02a3e32ab188f88b9fed55c","datavalue":{"value":"hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$1043293D-B7FF-4F3E-B7AB-09FE15674BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8809c8a95a6f9eec037ad2490d807acc804394cf","datavalue":{"value":"functional expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$2F4F66D8-EE86-48ED-8C37-6E821A5851DC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4028126$63D2F90B-179E-40A6-9CFE-8A459B171670","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9e43c02063707b3e117e56b99cb037bc6d82f30","datavalue":{"value":{"entity-type":"item","numeric-id":685460,"id":"Q685460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26d788c76e39705700c2c5b5a68eb2607a547d74","datavalue":{"value":{"amount":"+0.9816506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$7DDEC15C-B5E5-4DA5-A4EE-CEE078042FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22403b850a127b2bc48814e0a5870dd1afcfae21","datavalue":{"value":{"entity-type":"item","numeric-id":4972006,"id":"Q4972006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a1e89c7c2568bbd71e8fd9b796cf579c68539f9","datavalue":{"value":{"amount":"+0.94738907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$9A1B83D1-ECE8-47AC-B621-3BB4B53E1075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af1479ebd7a5fd135abacaa51111bf591a67cec3","datavalue":{"value":{"entity-type":"item","numeric-id":2736360,"id":"Q2736360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b289e1f77b49918881b2a662bd88c3e1f9a2b35","datavalue":{"value":{"amount":"+0.9237398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$84833DAF-72D4-4604-B0F6-836EA8D5877C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3ba736a13ff161be67d0eded0ee6bb1f2ddad93","datavalue":{"value":{"entity-type":"item","numeric-id":4415067,"id":"Q4415067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"941e00315d742bbdde3080b7487e7e45c022399c","datavalue":{"value":{"amount":"+0.8995855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$6FBBD5EA-4FFA-460A-97B7-36FDE9530F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f24658afcda2e81f49b130a787585785f0d0c5f","datavalue":{"value":{"entity-type":"item","numeric-id":2491953,"id":"Q2491953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cf0e6d0d956a3d0ce4d56f496c40a23f03d5f54","datavalue":{"value":{"amount":"+0.89821416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$B753DF26-9C1A-4A3F-AC04-C338B6275E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94e56b01caecb7108ee1db4f25e5c2a664b8e10b","datavalue":{"value":{"entity-type":"item","numeric-id":596311,"id":"Q596311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58d7ed4703865e0abe132f2173fc415d98e1f767","datavalue":{"value":{"amount":"+0.8791233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$88629D77-9216-462B-9283-5D06783EF792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4fc9d44dbf6eebe8131f1e28f9f5abe46e54a47","datavalue":{"value":{"entity-type":"item","numeric-id":5748897,"id":"Q5748897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea97b1e11a8e9415aaa1b092de25214e0914ac28","datavalue":{"value":{"amount":"+0.878917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$4D748307-0CCD-439A-8F42-971C1608436A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f591cd83df11667eeef538b988fb9fff30080a67","datavalue":{"value":{"entity-type":"item","numeric-id":5166670,"id":"Q5166670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acebf58850abd0e3255de89aa7209e99bca5b024","datavalue":{"value":{"amount":"+0.878489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$E299EA02-6450-4829-910A-BEF7C0D5923B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdfac03e65b4479b3d4288ea593ba94ee520ce61","datavalue":{"value":{"entity-type":"item","numeric-id":2762625,"id":"Q2762625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c153b1664efca6e78cacb9d59629783ebddefc35","datavalue":{"value":{"amount":"+0.86946666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4028126$AFC882BC-91A2-49FE-92A4-74C55DAC0699","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e3935d17b36264bad763e9541c66793358f0bc2","datavalue":{"value":{"text":"Algebraic approach to graph transformation based on single pushout derivations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4028126$2B372283-ACC7-45E2-9AC1-C0FB490663F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc9ebac2762b52e745dfb8035f8695f79360e8a8","datavalue":{"value":"10.1007/3-540-53832-1_52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4028126$BA6CD36F-7D51-4696-ABAC-4F38D5C42466","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a942ac0150e1ea5849e82ec795fb51499b3ca46","datavalue":{"value":"[For the entire collection see Zbl 0747.00042.] Various approaches have been proposed in the last two decades to formalize the notion of graph rewriting, which extends the theory of formal languages in order to deal with structures more general than strings, like graphs and maps. Among them, one of the most successful is the so-called ``double-pushout approach'' (shortly DPO), where a graph rewrite rule is represented by a pair of total graph morphism having the same source, and a graph rewriting step is modeled by a diagram consisting of two pushouts in the category of graphs and total graph morphisms. The paper introduces a new approach to graph rewriting (developed by the first author in his PhD thesis), based on categorical constructions in the category of graphs and partial morphisms. A graph rewrite rule is defined simply as a partial graph morphism, and, given an occurrence of the lhs of the rule in the graph (i.e., a total morphism from the lhs to that graph), a graph rewriting step is modeled by the pushout of the rule and the occurrence morphisms. It is shown that this definition of rewriting is strictly more powerful than the one of the DPO approach: as for the expressive power, it allows to model the deletion of a subgraph in an unknown context, which is not possible in the other approach. The paper shows moreover that, unlike in the DPO approach, synchronous parallel derivations increase the generative power of a graph rewriting system; that some proofs of classical results are easier due to the simpler definition of rewriting; and that asynchronous parallel derivations can be defined as well, in a natural way. In order to generalize the single-pushout approach to other kind of structures, categories of algebras and partial homomorphisms w.r.t. a given signature SIG are considered. An interesting result shows that if (and only if) all the operators of SIG are unary then the category of SIG-algebras and partial SIG-homomorphisms has all pushouts, and therefore the single-pushout approach can be extended to it. Signatures satisfying this requirement can specify graphs of various kinds, hypergraphs, and functional expressions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4028126$852471D3-3BD6-42DA-8330-4930C879E5DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4028126$528B6587-ACB8-4E56-80CA-C84ACACEECDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algebraic approach to graph transformation based on single pushout derivations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algebraic_approach_to_graph_transformation_based_on_single_pushout_derivations"}}}}}