{"entities":{"Q1121675":{"pageid":1132424,"ns":120,"title":"Item:Q1121675","lastrevid":69695754,"modified":"2026-04-13T08:46:44Z","type":"item","id":"Q1121675","labels":{"en":{"language":"en","value":"Metatheorems for decision problems on hyperedge replacement graph languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4104400"}},"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":"Q1121675$A9162224-27C4-48F0-B7DB-1035B987FCDA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"16f9215c54eb4803797d23844187c20de51494f8","datavalue":{"value":{"text":"Metatheorems for decision problems on hyperedge replacement graph languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121675$2214A0FE-3812-4094-B629-E438D7724237","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b950f5f2821a2f2f27cc9156233b2458a870fda6","datavalue":{"value":"0674.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$339FBA64-7CAA-4953-BF5E-F38B01330179","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3ff6aa2f3434f20522cf66eee5a72a24468202c0","datavalue":{"value":"10.1007/BF00288976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$21E6984E-C9A9-498C-9841-D5ABE6F8AB5B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9688c2b4abadd78a444a878d8043fe5f73058cde","datavalue":{"value":{"entity-type":"item","numeric-id":1098319,"id":"Q1098319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$D074A2FA-89E4-4EFF-A800-42959E4764CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f747afa3575ea8e92f39fe28bf85bb3ce76cb341","datavalue":{"value":{"entity-type":"item","numeric-id":396978,"id":"Q396978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$481581BD-9483-48B2-9E40-00AE5C3F3ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9d8a0330754342bf7cc054288ff91311aeb00bc","datavalue":{"value":{"entity-type":"item","numeric-id":1056223,"id":"Q1056223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$DEAA256B-68B6-42FF-9B80-38F724565EFE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$B61AEAD4-90F5-4682-8F0B-4E2ACDC2059C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1121675$F56BB6C4-F424-45D6-993E-20233500D6D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"044504fb3683eea7a3235075f426d7ec208e9559","datavalue":{"value":"If a graph-theoretical property is compatible with the derivation process of hyperedge replacement graph grammars in a certain way, the property turns out to be decidable for the corresponding graph languages. More exactly speaking, we consider two questions: (1) Is there a graph in the generated language having the property? (2) Do all graphs in the generated language have the property? In both cases, we get decidability for all hyperedge replacement graph grammars as inputs. Colorability, Hamiltonicity, and planarity are shown to be compatible so that our decidability results apply to them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121675$C12A8FDA-633C-426D-B170-A51B51223CA3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$7B085034-4CD2-4F65-9740-9962A1B81308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$354EB367-4600-40A5-9BD8-1CA8F9A69154","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85f9c978bafd00cef10db731231115c973333581","datavalue":{"value":"4104400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$45F4C178-32C3-49E2-B671-57F5E16404F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211c085a21fcd6ebc794856e642cf5ae4d9daa37","datavalue":{"value":"graph languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121675$9186195C-0744-4E29-A2DB-C6F5FD7CD4B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"deed356dae69ad9c3f2285e3ebc7403090fcc144","datavalue":{"value":"hyperedge replacement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121675$851D87FF-F87C-4B56-8BBB-C3F9132ED14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10aada1bcebcea30af443e4c20bac92e26c0b2a7","datavalue":{"value":"graph grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121675$2AE7EE65-C9CB-4624-87AB-189CB1BF2B22","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":"Q1121675$44A18660-64A7-4673-8AED-B2EA065E1CD0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"558f0ce4f975ae75a829dabb346f5be2f962b2a9","datavalue":{"value":{"entity-type":"item","numeric-id":1254289,"id":"Q1254289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$0FC17C06-1379-4640-8A9A-5A9AD9EFDD2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e557736ac81b6270b5f3aecadea4aabcc659d8e6","datavalue":{"value":{"entity-type":"item","numeric-id":3785987,"id":"Q3785987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$456847A4-30CA-45F6-BCF8-87A9EC777C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c7c33eeb134e251c185b46d445e8a2cca592b5d","datavalue":{"value":{"entity-type":"item","numeric-id":1839237,"id":"Q1839237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$EE449522-40E4-43E6-8A70-43A097B09774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a3b6b57aca8e7c38e35c3169c88b168a0503490","datavalue":{"value":{"entity-type":"item","numeric-id":1097866,"id":"Q1097866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$DDA602BB-645F-4D6E-82AF-70178ADE4AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66265f91787e12fc113183b978f33faab30b7d16","datavalue":{"value":{"entity-type":"item","numeric-id":3673131,"id":"Q3673131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$2EB98564-645E-497C-8544-1DF6E16FD26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c99f375b2f15c0c1b0a3c005b3cb0698f4883d5","datavalue":{"value":{"entity-type":"item","numeric-id":1098320,"id":"Q1098320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$7B01EA72-A82D-456D-A3F5-768754EF01A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c379a84facc4c1f6822043acb400db77a28718d","datavalue":{"value":{"entity-type":"item","numeric-id":3785988,"id":"Q3785988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$F8A655F4-111A-4C29-9DE5-1F6A84E38BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7baf863b093fb4d1a719d104d04793c3994ef02","datavalue":{"value":{"entity-type":"item","numeric-id":3774975,"id":"Q3774975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$F466047C-E162-423F-95AD-63AA47226BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8238a7273c5d8dcd98938b742ed574556abf859","datavalue":{"value":{"entity-type":"item","numeric-id":3815541,"id":"Q3815541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$F7053395-3FCD-4F10-B13B-EB9527FD84B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bca1eb9aaf703923e6b8ff723e3d12628b0bd9f","datavalue":{"value":{"entity-type":"item","numeric-id":1121675,"id":"Q1121675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$3F85A094-38CB-41F0-92CA-D5AB32DA86F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61a1dcded8ae87a40bce92ce6ec1c1e57d8303f6","datavalue":{"value":{"entity-type":"item","numeric-id":579950,"id":"Q579950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$7AB473D8-F003-4FAB-AAA0-F359D39BE6A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb538af3c092b4091c05e3418ef5ee8e7ca96406","datavalue":{"value":{"entity-type":"item","numeric-id":3789084,"id":"Q3789084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$47AB4B83-A507-4F26-A96D-E3701B0F6EDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9832541f3d56e45a1125e824fed23a54af63d6d","datavalue":{"value":{"entity-type":"item","numeric-id":3795251,"id":"Q3795251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$8773D7EE-85B6-4E69-8A28-23F2733A7E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61f90f49df14e6e6407902d63246b6e362b567fa","datavalue":{"value":{"entity-type":"item","numeric-id":3747744,"id":"Q3747744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$3824A2B4-F2FA-403E-BEED-30B6D1204DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2782452b658629470452f127d9f2f18105ab8e19","datavalue":{"value":{"entity-type":"item","numeric-id":1084870,"id":"Q1084870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$BFC03153-26AD-48D1-A736-8B6A7409A9B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9b8bc51f4e0e0529723f91ae841a5320fce1a39","datavalue":{"value":{"entity-type":"item","numeric-id":1164998,"id":"Q1164998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121675$AB23FDE6-0C74-4514-BAE0-FCA14BDC1976","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4b22cfc4d9e2955316b467e84ba35cf72509083","datavalue":{"value":"https://doi.org/10.1007/bf00288976","type":"string"},"datatype":"url"},"type":"statement","id":"Q1121675$04C3CD3B-9448-4E0E-A499-B694BD083B7E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"058ce5ef1cbcc2b1227d902c9c877e9d38ac9a6b","datavalue":{"value":"W2068755149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121675$302EE573-DA36-4B9A-97EE-2C7CDD0D34FD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdc4c43fc0374be35fb854930acb16eb5ec589d7","datavalue":{"value":{"entity-type":"item","numeric-id":3815541,"id":"Q3815541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ded0339a086557d8c0ecbe956059d4d3eb171f16","datavalue":{"value":{"amount":"+0.9045681953430176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121675$F36A7F0A-DBD2-4F63-9DDE-FB10C4152C0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"643a9e7108e5e0ec4ea306bc482ed8d39a9fcbc0","datavalue":{"value":{"entity-type":"item","numeric-id":4711083,"id":"Q4711083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ba4e614623229780eea5397e147339ae1bf4320","datavalue":{"value":{"amount":"+0.8348273038864136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121675$9CE23EFF-5766-4150-9125-5A05B73491D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35c1c23e25a016bd04f7bf06cd07b1ceab3a95c3","datavalue":{"value":{"entity-type":"item","numeric-id":684560,"id":"Q684560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67bb1230a9bc27957bacc2134839fca6fb1792b1","datavalue":{"value":{"amount":"+0.8189998865127563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121675$6039E3F2-3F6B-49A8-8B28-8F28ED8D0586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"263bf32efd8db04a94b4714ed6fd2c9a5feb4719","datavalue":{"value":{"entity-type":"item","numeric-id":4852905,"id":"Q4852905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67bb1230a9bc27957bacc2134839fca6fb1792b1","datavalue":{"value":{"amount":"+0.8189998865127563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121675$F30B1EE0-FD16-45FF-83D3-CB7F3DC27763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e9cab74c34eccd4de9e8bf9d6e7744b2bc4d767","datavalue":{"value":{"entity-type":"item","numeric-id":5096886,"id":"Q5096886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc2a0b25c979330de0b436db2321db865ba6eeb1","datavalue":{"value":{"amount":"+0.7976374626159668","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121675$100528BE-43A7-4507-B5BB-16E36CF9AD95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Metatheorems for decision problems on hyperedge replacement graph languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Metatheorems_for_decision_problems_on_hyperedge_replacement_graph_languages"}}}}}