{"entities":{"Q579950":{"pageid":581717,"ns":120,"title":"Item:Q579950","lastrevid":62944941,"modified":"2026-04-11T09:09:29Z","type":"item","id":"Q579950","labels":{"en":{"language":"en","value":"The bounded degree problem for NLC grammars is decidable"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016215"}},"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":"Q579950$4AE404DC-5E13-4D7C-9C54-086A9B593E7B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ddb588a675c9040c934dc9f4185f40979511f4a","datavalue":{"value":{"text":"The bounded degree problem for NLC grammars is decidable","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579950$E22673BC-C337-468F-8D91-913FA7935B6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9a8fc03e74fca65d9a2db53652a17dce7457192b","datavalue":{"value":"0625.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$424E62D6-D3A4-4915-A790-CCB2DC919A48","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f4be34e593860584ad380d8edb9339edb6ac2e17","datavalue":{"value":"10.1016/0022-0000(86)90060-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$87F98EC6-C5A1-4783-A8C1-2F78963BE467","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46258099fcdf6970a7ace1aa1032bd68914ad03e","datavalue":{"value":{"entity-type":"item","numeric-id":579949,"id":"Q579949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$531D2281-59A2-4DAD-9A49-E422BC469FFD","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":"Q579950$6E13A951-DB29-47E3-9664-3291FFFE22E8","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":"Q579950$A1CFE770-B0DF-403A-947A-439566FAAE6E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$ED576C1D-01BD-433F-891B-DFF08C6A0737","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q579950$7D20397C-2D33-49EF-A43A-A79B162345DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"39b7b47eeec0ff4fd6f743c52d7a14d74a8e986b","datavalue":{"value":"The degree of a graph H is the maximum among the degrees of its nodes. A set of graphs L is of bounded degree if there exists a positive integer n such that the degree of each graph in L does not exceed n. We demonstrate that it is decidable whether or not the (graph) language of an arbitrary node label controlled (NLC) grammar is of bounded degree. Moreover, it is shown that, given an arbitrary NLC grammar G generating the language L(G) of bounded degree, one can effectively compute the maximum integer which appears as the degree of a graph in L(G).","type":"string"},"datatype":"string"},"type":"statement","id":"Q579950$1727F083-9660-4A85-9F57-59BA9A88BB22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$1FC5B969-EFC6-4311-B300-BE9F59B65D5B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c14bad30e8b9aa7403a9078383041ffd222356d","datavalue":{"value":"4016215","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$53D15779-FB6E-48CA-B6E6-548B2A1E089A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26c8447b75a74a92e6693bf549619c29a60e23c4","datavalue":{"value":"node label controlled graph grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q579950$BB79FA98-A559-4EE5-A381-6A17DDB12F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q579950$0FFB320A-DB6E-469E-887D-F958E3B6CF18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff8bc6c35701a8864f72aba6f0d24e628673e1ca","datavalue":{"value":"degree of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q579950$2F27C8A0-2408-4DDD-BDC1-99DBD11C89E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad842ad959da83378064b3e3e21d1fa80e76ac0","datavalue":{"value":"bounded degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q579950$C416A455-81C7-4DF9-AED8-2CBA25BDA428","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6b71099f2eac1de08bf345340ecf676eaeda75ea","datavalue":{"value":"Q54309924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$62A28466-C9DF-4880-9A2F-5AC730AD1A28","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":"Q579950$1C5353AD-4885-40B6-902A-FA3CC60F785B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a78e34924378c940d342395b19ced57e9c87a0df","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90060-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q579950$1E9D9FC8-3748-45FF-A7EF-88EDD8FAC7DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"487c77ba311b4091d3d7ef897cd740e54ccfadd7","datavalue":{"value":"W2041168908","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579950$0BF96A68-0485-4C9B-BB7B-3E7EC9258192","rank":"normal"}],"P223":[{"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":"Q579950$C8270DCB-8FDC-4EB1-A945-7401FDF66216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"516ac2ad86e13d550936e07d981599a34562d039","datavalue":{"value":{"entity-type":"item","numeric-id":3904060,"id":"Q3904060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$9318EBAF-75D7-4644-9984-B303888CE573","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":"Q579950$2FD11CBB-4A98-41FD-9771-9D0731DDD88E","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":"Q579950$8C3050F7-56FF-470A-B39D-C23090202663","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":"Q579950$A37EA3AF-F70C-445C-92BE-50B3DDB21353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95eb261a48a0729cb618bbd951bb1c22e052b409","datavalue":{"value":{"entity-type":"item","numeric-id":1154289,"id":"Q1154289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$E6FDF82C-59A2-4076-A56B-FD2E2C75EDDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8782b9475c4a7888413a447d886143beb63d25c","datavalue":{"value":{"entity-type":"item","numeric-id":1219692,"id":"Q1219692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$BEFE0A26-28B0-47E2-85EB-FF11BDE26499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9500e19069722efa256e9656f8110bdcd87d826","datavalue":{"value":{"entity-type":"item","numeric-id":4140407,"id":"Q4140407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579950$4B46E1F4-552D-425D-91D1-E879E0924464","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":"Q579950$AE94926E-B64E-4A90-9406-C03A9E4A01C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6e8411d8cdb1b52b307a4be5d832dca01f22cd6","datavalue":{"value":{"entity-type":"item","numeric-id":1363781,"id":"Q1363781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b93cc624f13080ca897ed605aad4de0685c66f8a","datavalue":{"value":{"amount":"+0.8355938196182251","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":"Q579950$79AA2463-5A09-4D20-A79B-7E4F03F31252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adfde2b890f528ea9773d1892c91d366cfc6bc27","datavalue":{"value":{"entity-type":"item","numeric-id":4645278,"id":"Q4645278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45cd3f023d008a2e4e9f94c7591b60ae7b7d5e92","datavalue":{"value":{"amount":"+0.7875543832778931","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":"Q579950$93AB3AC4-A0A5-4A41-8530-960FFAD5FAEB","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":"5242550cb6e5ced2341ceadd61dc57acf77a2c5d","datavalue":{"value":{"amount":"+0.7851693630218506","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":"Q579950$82FCF790-4481-4C29-8917-60A2AB2BEB53","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":"d90ff1173babc12195b64c705ed00010eaba7254","datavalue":{"value":{"amount":"+0.7774637937545776","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":"Q579950$D6E13D1F-B2CC-4B51-B32D-E323EEAEDCAC","rank":"normal"},{"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":"5f180937ffa01f3158bb61e606ddb3498a8f3249","datavalue":{"value":{"amount":"+0.769287645816803","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":"Q579950$4F158DD3-074D-4CB0-91E3-FCE67C4ED20A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The bounded degree problem for NLC grammars is decidable","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_bounded_degree_problem_for_NLC_grammars_is_decidable"}}}}}