{"entities":{"Q804300":{"pageid":806148,"ns":120,"title":"Item:Q804300","lastrevid":64504677,"modified":"2026-04-11T20:19:59Z","type":"item","id":"Q804300","labels":{"en":{"language":"en","value":"Nonterminal separation in graph grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4201634"}},"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":"Q804300$2DD93206-4E2A-43FB-A430-E899C6581AB1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c8ccc9e51dced1f739418aaeb61e187b48740dd","datavalue":{"value":{"text":"Nonterminal separation in graph grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804300$A820C887-A2B0-41FA-BAF8-2808AB89C8A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e584bbf50350086c2d4f86d81e0fd248bb7b313d","datavalue":{"value":"0727.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$A4904DFF-BA0D-4F07-A7E5-A17A0102FC29","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4f2b90e4110ebe71ff0792fc2428872bbf5ebd3","datavalue":{"value":"10.1016/0304-3975(91)90174-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$C374EAF5-81F9-4B5D-9DC3-94E3C7FEE7AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdaa763056574d670db49d3b9b4fb6f07d823420","datavalue":{"value":{"entity-type":"item","numeric-id":255286,"id":"Q255286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$0D001903-9205-4808-8F71-E9FA127791EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b8884adabb219717ae37d79c2370cbec0d958a0d","datavalue":{"value":{"entity-type":"item","numeric-id":804299,"id":"Q804299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$AF35E097-576B-425D-BFCA-CAE758D323A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3fcef18c71a4b5df42d463ab66d395e6876189c","datavalue":{"value":{"entity-type":"item","numeric-id":537812,"id":"Q537812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$AC82A7B3-0AB6-4A61-9AA0-918E158D3569","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$E0FBF286-A5CF-4093-9461-9B6F33C8F291","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q804300$551B3D46-FCA2-4E79-8222-D065C237CB03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7aa920dedb7c3216fe43860749c3ebf4a0dc5c8b","datavalue":{"value":"The eNLCE model of graph grammars was introduced as a variation of the successful NLC model. In a NLC grammar the left hand side of a production is a single labeled node, the right hand side is a node labeled graph and the embedding mechanism depends solely on the labels of the nodes involved. In the case of eNCE grammars the embedding mechanism makes use of the identity (rather than the label) of the nodes in the right-hand side of the productions, the generated graphs have also edge labels, the embedding mechanism also uses the labels of the edges incident with the replaced node. In a previous paper the authors have shown that eNCE grammars are more powerful than NLC grammars. It also shown that boundary eNCE grammars (such that there are no edges between nonterminal nodes in any sentential form or, in other words, such that the distance between nonterminals is at least two) are confluent (namely, if two nodes in a graph can be replaced they can be replaced in any order).    The present paper investigates the general notion of distance between nonterminal nodes in eNCE grammars. An eNCE grammar is called k- separated, for \\(k\\geq 1\\), if the distance between any two nonterminal nodes in its sentential forms is \\(\\geq k\\). Having previously shown that 1- separated grammars are more powerful than 2-separated grammars, the authors prove that 2-separated grammars are more powerful than 3- separated grammars and conjecture that, for \\(k\\geq 3\\), k-separated grammars are more powerful than \\((k+1)\\)-separated grammars. Another considered restriction on graph grammars is an apex restriction. An eNCE grammar is an apex eNCE grammar if the embedding mechanism can only establish edges between terminal nodes. For apex grammars to be k- separated has no influence on the generating power, namely it is shown that each apex language can be generated by a k-separated apex grammar.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804300$112E41CF-0DD6-4C99-B65F-0206653FB1C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$944F61C2-A960-4631-8A12-366A09779D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$6388844C-E6C1-4CA1-8485-547B42ED9C88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78d014e3dc00478b1c323946805576da2fbf5f99","datavalue":{"value":"4201634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$5BA5B0C1-F35C-4DEF-A018-DFFC38BF1642","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10aada1bcebcea30af443e4c20bac92e26c0b2a7","datavalue":{"value":"graph grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q804300$44526558-057C-410A-BC23-8649C0DC0B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b16885eab3611f81a6d7dcda5801efa118d49ca6","datavalue":{"value":"NLC grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q804300$60E34101-B63C-4665-8584-4B06286C28E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d9bfcb8356e715a6ccf1ebca6921a4157a1b9e1","datavalue":{"value":"eNCE grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q804300$427FF140-43D9-4BF9-8BC9-F4CDD6C00BFD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"14df87f03128769fb7e76235928bf393d9238874","datavalue":{"value":{"entity-type":"item","numeric-id":256972,"id":"Q256972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$F48A7BA9-F2DC-45A2-9C3B-DFA4B042125F","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":"Q804300$43CD8580-3D04-4730-921B-4223779B2894","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"df339d46fcf03edbcf2f1cb39950fc86b5055035","datavalue":{"value":{"entity-type":"item","numeric-id":1160492,"id":"Q1160492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$C29AE332-1F91-43A9-AD15-0E9399AC6D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b682d03898f6354bdb4a4dc9d30d8907bc09138","datavalue":{"value":{"entity-type":"item","numeric-id":3785989,"id":"Q3785989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$CBAFA4CF-BAA6-4765-A4A2-C71B4DBABDB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9848b4fd1ef75a2a4ab651bfd989bf0b5b966f9","datavalue":{"value":{"entity-type":"item","numeric-id":1102759,"id":"Q1102759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$B3A888FC-5F36-493D-BCA4-06E91982C451","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":"Q804300$4DC1A55C-2989-43F6-917E-D7975C3FBF97","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":"Q804300$2E20D542-AC26-4D1D-B078-489D4E89A3CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6077dc9060d443e8ab8a42e49225f54055f4683","datavalue":{"value":{"entity-type":"item","numeric-id":1825679,"id":"Q1825679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$8E495323-DDAD-4405-8063-7A339ADBF910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3f194098ebef99fcd8008d11cde7c175827e52f","datavalue":{"value":{"entity-type":"item","numeric-id":3479528,"id":"Q3479528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$9D475FEF-DEAD-4F08-B5D0-0F87797D79E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a410172504998f32dad616a6c79e4759c4dfdbc","datavalue":{"value":{"entity-type":"item","numeric-id":1112623,"id":"Q1112623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$F78A6468-8BEB-4BCA-B65D-EA0564410758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"412f1e5d69c1b991a3ea0763bd7a50c2348e93bb","datavalue":{"value":{"entity-type":"item","numeric-id":3785994,"id":"Q3785994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$C4D7A34F-9020-4BD7-B46E-A0B3D4A82EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"530cf4a6d9da547b53803a2e418e382503fa8e96","datavalue":{"value":{"entity-type":"item","numeric-id":909478,"id":"Q909478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$2DFA3A5D-0852-4197-8E2C-6B4727034184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d527d23dee7163913e5f74effb7ac631aa8721d","datavalue":{"value":{"entity-type":"item","numeric-id":918718,"id":"Q918718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$BF417442-252C-495A-B768-8BF5EDB6F356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aff39c1b2290aa34005c6f3fd9e348438dfa64a","datavalue":{"value":{"entity-type":"item","numeric-id":5343340,"id":"Q5343340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$F0D61784-5B47-44C9-9F87-6F4FE6F57C50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f1611d0bccc178e7cc063bff448247b9e39487e","datavalue":{"value":{"entity-type":"item","numeric-id":1148687,"id":"Q1148687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$FD277DF3-859C-4DE1-A2F1-D1F0F848972B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e7c36b841ac15208250c2b5be973efb41da225","datavalue":{"value":{"entity-type":"item","numeric-id":1148688,"id":"Q1148688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$FB372D64-9637-4118-807B-72178DDED836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f74b5df1f366618cf26ce8d25ea6f8b57fd6b1","datavalue":{"value":{"entity-type":"item","numeric-id":1165019,"id":"Q1165019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$9A58DAB0-558B-447C-BA1C-8E226E7B508B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0744a3abc353d1c851eb82e0dc52d0e5938b1c6","datavalue":{"value":{"entity-type":"item","numeric-id":3714485,"id":"Q3714485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$393F21C4-EF5D-41D5-8993-0199C96252BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e113fa7dba6273eaa37c30e195c8c8ccb615221d","datavalue":{"value":{"entity-type":"item","numeric-id":3785990,"id":"Q3785990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$B3EAC1E2-4DBF-45B5-970E-8F4931C16E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03b3c644866cdc806076c9163dec5121eeaaf5f","datavalue":{"value":{"entity-type":"item","numeric-id":1146007,"id":"Q1146007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$EE2018E7-46EC-4B8E-8BF2-37D4BAEF1DF5","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":"Q804300$5692EE44-5FD8-43F4-904A-C330EB6E234C","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":"Q804300$FDC322DD-EB08-4B85-B9A2-A16D709A05D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfecee04fe3bf5c991f4c45714521a85c7a303d0","datavalue":{"value":{"entity-type":"item","numeric-id":1089808,"id":"Q1089808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804300$BE8E2BCF-9CD7-4442-B52F-CED2D42AA61D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7605b18a6045807021c2dbe3df47159a79590a62","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90174-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q804300$6A70F019-2755-4F13-A468-580C0B9D6F71","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d0acc6d081dff5f5bbfad7462e9c4b3bf939612c","datavalue":{"value":"W2004135004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804300$410C3F28-A99D-4E2D-B821-76540EE9B53F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e19b515cb82a9b4b529f4a04c2723b69bee4ea4","datavalue":{"value":{"entity-type":"item","numeric-id":1314371,"id":"Q1314371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd85a8e2ae9ec6eda6a3337802761f547f4e14f","datavalue":{"value":{"amount":"+0.8806008100509644","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":"Q804300$C895D2DB-F81E-45AE-B216-3156EB88ECDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f00803b231f4d7e3217b642eeea2e62354596b","datavalue":{"value":{"entity-type":"item","numeric-id":1059402,"id":"Q1059402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"873fd88dd9a0beeb978f07717ff2eb6acd176f62","datavalue":{"value":{"amount":"+0.8784251809120178","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":"Q804300$DEF14139-7676-4DD0-8E5E-4BC27D14C68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53f0a2736d0cec7944e46592b4243473ebf4ccce","datavalue":{"value":{"entity-type":"item","numeric-id":1114416,"id":"Q1114416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8525c82a1ba604903dccdb405ee1d76781eb4eb2","datavalue":{"value":{"amount":"+0.831041693687439","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":"Q804300$B7758E5F-4204-4D49-B342-92E4139CC220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df07ecad46e1b4701a71fe54178303712c5ab4c5","datavalue":{"value":{"entity-type":"item","numeric-id":909478,"id":"Q909478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2dd9f5a320b78cec223d475bd332a27bd989422","datavalue":{"value":{"amount":"+0.814915657043457","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":"Q804300$A46E2AF8-A27E-45BD-9A05-6731A1E56DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"565fbb2f2d88a2e51dd7a622c6c7bb20fc177475","datavalue":{"value":{"entity-type":"item","numeric-id":5946057,"id":"Q5946057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76036faaee593776bff5b7179f468fb88d261283","datavalue":{"value":{"amount":"+0.8053565621376038","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":"Q804300$793D2D00-018C-46E5-9ADF-E7CE0C712245","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonterminal separation in graph grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonterminal_separation_in_graph_grammars"}}}}}