{"entities":{"Q1089808":{"pageid":1100560,"ns":120,"title":"Item:Q1089808","lastrevid":69619200,"modified":"2026-04-13T08:14:40Z","type":"item","id":"Q1089808","labels":{"en":{"language":"en","value":"Combinatorial properties of boundary NLC graph languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4005635"}},"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":"Q1089808$D4B4D667-412E-4F1C-9F88-806F4F93562F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d90afa082dc65f714c31900cf2ea1e5f42e61ba1","datavalue":{"value":{"text":"Combinatorial properties of boundary NLC graph languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089808$98BC5937-82B8-48EB-A29E-87D0302BEBD2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d0655fc2b58feb04d53b50bd299fadf6a32c276","datavalue":{"value":"0619.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$F01CC375-8B47-42B1-BF51-CDD608D34254","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f7f7242d67475bcd390c074a9239d40f92e87e33","datavalue":{"value":"10.1016/0166-218X(87)90054-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$66C515F4-BE9F-40BD-A697-1F84D8FB67AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$D7F548B0-07C0-4427-8FFA-2C6CFB3D0B4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1089808$50200C57-4FCB-42A1-9252-8BF65D99FA60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48f1ad55203f140acc6e050977aa1deedfab65d2","datavalue":{"value":"Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever - in a graph already generated - two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages.    In this paper we investigate the behaviour of graph invariants within BNLC languages. First we demonstrate that there is a dependency between the chromatic number and the clique number of graphs in BNLC languages (while this is well-known not to be true for arbitrary graph languages). Secondly, we introduce a new graph invariant, the so-called index of a graph which seems to be very suitable for describing the adjacency structure of a graph. Then we prove that every BNLC language is of bounded index (which is shown not to be true for arbitrary graph languages). Thus we exhibit properties (concerning graph invariants) of BNLC languages which are intrinsic to this class. We use them to demonstrate that certain graph languages are not BNLC languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$48DCFAF2-7BA2-4156-B0EC-7D0F66B37672","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$8AC1CE43-84A6-4CC1-A7C3-410A802FCE8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$E75AA730-44A5-4810-96ED-F72B3CC19AE5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da74ae299139bf547b05cfcad3a2aff7db28844c","datavalue":{"value":"4005635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$191BD4AB-A7A0-4E88-9B4A-AD9D11A498B4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf16b02cba9ac89eccffced0abcd0ede7b2dc419","datavalue":{"value":"node label controlled grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$D153858B-1D1B-4C76-94AC-5449C1DEE0A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10aada1bcebcea30af443e4c20bac92e26c0b2a7","datavalue":{"value":"graph grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$6A313DC9-661A-4379-9341-9EAE6AE73231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f88cc2fb2371f255bb813968be6f9959091b216","datavalue":{"value":"node labeled undirected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$32453F5F-AC60-417D-A6DB-7B09E6BDDC94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf97b14751de9b39b7a077d5a66b4624e6011788","datavalue":{"value":"behaviour of graph invariants","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$AD48208A-6EB8-42BA-8A1A-ECFB1B30825D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3884de936e74dbcae0ba6b6239721cda6e7e4de1","datavalue":{"value":"BNLC languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$6BE61B25-7B0D-475A-8C50-F1DACAB59D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$4FBE60D8-12D8-4DF9-B594-A6E958BE9841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$E5310341-B20F-4F77-8B75-77C33BA5EEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a583d3478a8d2deb9161af7d0c31c6973d33ff07","datavalue":{"value":"index of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$4ECCB306-7286-4F24-B93F-7440ACC2E133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"120075a8d4afca6e7c3232692f67b8a1673a9de1","datavalue":{"value":"adjacency structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089808$ECE2AF6B-5F92-430F-8AF3-A493C4EC3AB9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8e0ec6d1f77a26b5e3e95215446327574a42b39a","datavalue":{"value":"Q54309830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$EC0576FD-D953-4366-B87C-F432A1B5BF47","rank":"normal"}],"P16":[{"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":"Q1089808$A22C8049-CC8E-4368-9B80-7D06F6D01DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebde143434d63bb91413660f73ab09b4563fd56f","datavalue":{"value":{"entity-type":"item","numeric-id":1262764,"id":"Q1262764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$EC6C347B-639F-4687-ABF3-E50FCE0FEBD1","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":"Q1089808$B0AA3096-B764-4C67-BB3C-3EB5591F880E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$5467B37B-5106-4D7C-80C3-7A980E0C7AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1b301e0975ada79ba9e2c782ad7a944d932a650","datavalue":{"value":{"entity-type":"item","numeric-id":3321473,"id":"Q3321473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$718F5E79-884C-4AD0-A5B7-FBB1CF87CCDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"054cde9ff5bf83a62fc076d625b70d210ff5faa7","datavalue":{"value":{"entity-type":"item","numeric-id":1059402,"id":"Q1059402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$6A4E640C-E1CF-47C2-BD4B-3ED1CBA0A67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef15b3970454943801ea6f54009a29a9b0eb4583","datavalue":{"value":{"entity-type":"item","numeric-id":4194478,"id":"Q4194478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$8A6C5F0A-4BFE-4337-A148-FD25907FE3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$76A14FDC-A372-482A-8D59-B5A548D4C101","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":"Q1089808$4111D4C5-6FA1-4937-A74E-F1A5053534A7","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":"Q1089808$7F5150A8-842C-402E-AA9F-15FECC00FE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b47e8d4a47e9f8b7b05092979c0cce40c84d58f9","datavalue":{"value":{"entity-type":"item","numeric-id":1155373,"id":"Q1155373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$C8674E8E-5786-46A6-834C-96ED36CEB472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$8698A50D-65CE-402B-91DC-DD43D17E745B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8caa5b9c306a69055ac3b578a5af983545cedd42","datavalue":{"value":{"entity-type":"item","numeric-id":3049830,"id":"Q3049830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$A978BDA5-ED81-449E-BCF8-7620009989E4","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":"Q1089808$D1E21421-FF44-4925-8BD6-DFABC1E110E7","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":"Q1089808$82FAD35B-E740-412B-B618-EAF8B7965552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70e382162a17f3ea11a456841b869df7a9512a75","datavalue":{"value":{"entity-type":"item","numeric-id":3219131,"id":"Q3219131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089808$AC839E51-CF9E-4DA4-821F-EB2E82A7A1D8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1e303f4cd08965e637a3fd64ce7afd8b3b693a4c","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90054-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089808$005B4648-B6A3-465B-8878-E9DFC6113A8A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d22769d9c53da711d8105ae4090503690ff98a19","datavalue":{"value":"W2080485683","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089808$1C08C7A0-2FC6-4F7D-9A45-269CA1558AE6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"047403f0f7b51267f30a2a06c5c0445acefe9173","datavalue":{"value":{"entity-type":"item","numeric-id":1084870,"id":"Q1084870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88089048f0c21b3ab2b7cd51c8e706a9ac379536","datavalue":{"value":{"amount":"+0.909953474998474","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":"Q1089808$826E4F5D-CD58-4277-827A-7D05395750CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"386fda0bda66a33be8dbad7d8cbe46984ea4bcc9","datavalue":{"value":{"entity-type":"item","numeric-id":3347320,"id":"Q3347320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"469a9f5dad8256ba2a571893ca1ceab7d137975e","datavalue":{"value":{"amount":"+0.908822238445282","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":"Q1089808$1B284A9D-B9ED-4048-B8F8-DB273FC174A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f21c8cbeb76bdb85e516de84ab5b338cf22511c8","datavalue":{"value":{"entity-type":"item","numeric-id":3747744,"id":"Q3747744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4028dc62c2558054055b269b24d42ab040249903","datavalue":{"value":{"amount":"+0.8898027539253235","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":"Q1089808$C6242DDD-1CC2-4AA3-9671-3EB73D3689CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd28da489d1f766e253f4914fed3a270d19dc2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1338850,"id":"Q1338850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7baedff0317583cab77c84f84658cdfefbcdc36c","datavalue":{"value":{"amount":"+0.8677136898040771","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":"Q1089808$3E5F3CAB-3405-4F46-8D31-C2A4A057EB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"225cec4d0cfbc8338031653c3e50cbb6b21e0dcf","datavalue":{"value":{"entity-type":"item","numeric-id":3714483,"id":"Q3714483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f71a9a633e0700b3d3c9c3918c805bc1ad4f6fa","datavalue":{"value":{"amount":"+0.8627153038978577","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":"Q1089808$2853AEB7-944B-4A08-B687-4D2C533060ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Combinatorial properties of boundary NLC graph languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Combinatorial_properties_of_boundary_NLC_graph_languages"}}}}}