{"entities":{"Q908714":{"pageid":910562,"ns":120,"title":"Item:Q908714","lastrevid":65268075,"modified":"2026-04-12T01:25:45Z","type":"item","id":"Q908714","labels":{"en":{"language":"en","value":"Undecidability of the bandwidth problem on linear graph languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4135418"}},"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":"Q908714$4EB5E42A-7C3A-4682-9E8C-E4B6F4FF69E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fab9b389303e2980d5684f4788841d8b6acb0106","datavalue":{"value":{"text":"Undecidability of the bandwidth problem on linear graph languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q908714$921A20EC-F870-4678-B3EF-941B25854E08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ae1f36a9359edb1f45a16c3ddb4521d3911399a","datavalue":{"value":"0693.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$0D02A675-B9FC-4015-9A3F-236BAD04B9EF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8300ab8bb7761841252c317dbb5272cc19ed774","datavalue":{"value":"10.1016/0020-0190(89)90140-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$283BE773-A204-415D-AE73-567F3118DA36","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"685757cc2dcf96368fde81e2188c1f6604dd8766","datavalue":{"value":{"entity-type":"item","numeric-id":908713,"id":"Q908713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$FF3F2639-7594-4D59-8299-17CB648B213B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fadff73cdeb0368376f03d1a4c45191f4476dce","datavalue":{"value":{"entity-type":"item","numeric-id":261534,"id":"Q261534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$DD77B0B5-E871-48AA-9A89-F93ED0431FD7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$B8CCED29-E151-4F76-B6D9-C5D1765ADE96","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":"Q908714$528E227C-DC12-470A-A634-654BE1B0009D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f0ed8fc84a9d5b05f05c7c393a1cecbbd632685","datavalue":{"value":"Let \\(G=(V,E)\\) be an undirected graph with n vertices. The graph G has bandwidth k if there exists (1-1) mapping (k-layout) f: \\(V\\to \\{1,2,...,n\\}\\), such that \\(| f(u)-f(v)| \\leq k\\) for each edge \\(\\{\\) u,v\\(\\}\\in E\\). Let \\(\\Gamma\\) be a linear graph grammar defined as follows. \\(\\Gamma\\) consists of a finite number of labelled undirected graphs \\(G_ 1,G_ 2,...,G_ k\\) such that each of them has at most one vertex labelled with p, one vertex labelled with q (connection vertices), and one vertex labelled with \\(\\delta\\) (nonterminal vertex). Each nonterminal vertex u has exactly two neighbor vertices labelled p' and q' and some substitution rules \\(u\\to G_ t\\), \\(t\\in \\{1,2,...,k\\}\\). One of the graphs \\(G_ t\\) is the start graph. In \\(\\Gamma\\) a graph G directly derives into a graph J if G contains a nonterminal vertex u with substitution rule \\(u\\to G_ t\\) and is obtained by substitution u of a copy \\(G_ t\\) of \\(G_ t\\) with the identification vertices p and q with vertices p' and q' respectively. In \\(\\Gamma\\) a graph G derives into a graph J if there exists a sequence of graphs \\(H_ 1,H_ 2,...,H_{\\ell}\\), \\((1>1)\\), \\(G=H_ 1\\), \\(J=H_{\\ell}\\), and \\(H_ i\\) directly derives into \\(H_{i+1}\\), \\(i=1,2,...,l-1\\). The language L(\\(\\Gamma)\\) of \\(\\Gamma\\) is defined as a set of graphs that are derivable from the start graph and have no nonterminal vertices. The main result: Theorem 1. Let \\(\\Gamma\\) be a linear graph grammar and \\(k\\geq 3\\) be an integer. Then the following question is undecidable: does the language L(\\(\\Gamma)\\) contain a graph G having bandwidth k ? The proof of the theorem consists in reducing of well-known Post's correspondence problem, which is known to be undecidable, to this problem. For the case \\(k=2\\) the authors conjecture that Theorem 1 does not hold.","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$F4E6D188-8245-46F1-96BE-B2063DDE7F21","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$3854338B-68F8-4643-9D19-AD078F0076B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$EC3466B7-0D52-4737-8FED-C3ACE198C373","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3ca815aa74dd1bcd418077d5d24d5cd66b90aa41","datavalue":{"value":"4135418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$D013613E-7F81-4C3A-AC04-1ED22B4D84DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$33471C01-A0A1-4360-89F6-89644C98C10B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$F2057ABE-220D-4938-9A7C-75B53B609418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72494967642b9ea1b87091d53eb77ad552577f43","datavalue":{"value":"bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$4AF4E480-ACF0-4328-9C17-0E46BF564B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211c085a21fcd6ebc794856e642cf5ae4d9daa37","datavalue":{"value":"graph languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$52D20829-A76B-40CF-BFC0-3E2E4472231B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b99b1e01954f36b2bc8e00e08ffdc2eacfdc6f6b","datavalue":{"value":"graph grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$01587E95-11FF-4C40-BAC6-D693A8624321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"246ff3fd887061c8c3ce902c0efbb2e1b8a668ea","datavalue":{"value":"Post's correspondence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q908714$786A487D-B20C-46FD-A92A-6BCDBC5C1729","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":"Q908714$3AECF596-3ADC-44A9-B5B9-645DC9EEBC71","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78476d0202323726bf7d30851bba6a5edfb205dc","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90140-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q908714$58B56A19-67A0-46C7-A289-C1DCED6E1CB0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb93527bf453f33d56993906283bf983d20d95c8","datavalue":{"value":"W2059171004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908714$B33DA43F-C1D7-469F-A6A5-681AE1AFE0F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc69c6156e9471fec17a5d754a7b363dbf0153f6","datavalue":{"value":{"entity-type":"item","numeric-id":3812222,"id":"Q3812222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$0D99E6E6-4745-4B07-A11B-E06344062103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be3970bbeb5763bd476ec3ae32dc6811c75f4cd","datavalue":{"value":{"entity-type":"item","numeric-id":3782818,"id":"Q3782818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$C550CE50-3BEC-4592-84BA-A2D5B4EBA821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04613e27d09f9e082e14779fbb81073cab13e44a","datavalue":{"value":{"entity-type":"item","numeric-id":4205068,"id":"Q4205068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$0CB2DEA6-9D1A-4CB5-9906-17C30DDA6D18","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":"Q908714$0A120555-9432-4857-9F5E-5CEE52AEEE66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd01152085dc6c923faefae39879822e508a915","datavalue":{"value":{"entity-type":"item","numeric-id":3219762,"id":"Q3219762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$1FF0E005-D86A-468F-8932-6FD0BB0DD465","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":"Q908714$4E92E697-98E8-4258-B22C-D1E37AA3B0F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$933AE141-C07B-4DA0-81BB-BEFA7436DD3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$20051ABA-D69B-471D-96FD-28BE22B26ECB","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":"Q908714$C3B82007-E132-48CE-AEB9-81D82E50E8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2520ef212a371adad072bb863e47e3fe5bae34e","datavalue":{"value":{"entity-type":"item","numeric-id":3960121,"id":"Q3960121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908714$726F6B93-9AB3-4E76-A98E-CA1EC4369A2D","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":"Q908714$FD608DFF-4C1A-4C0C-82A3-EF74CE56C55A","rank":"normal"}],"P1643":[{"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":"d44d2beb6eedbbe4138c1a209631e00f60f6898c","datavalue":{"value":{"amount":"+0.7544705271720886","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":"Q908714$9BBAB07B-E017-44CA-8AA6-EE40D8C8F908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8ecfcd557a070b3f03a2079e7ae2a7ca69b1c55","datavalue":{"value":{"entity-type":"item","numeric-id":1583541,"id":"Q1583541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc76fff58cc92402390476939ed8cd694a86e9eb","datavalue":{"value":{"amount":"+0.7400825023651123","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":"Q908714$412D2B78-838D-40C5-B5CF-41486247B042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e306de382b944630c166d52acad0fb67d242bdf","datavalue":{"value":{"entity-type":"item","numeric-id":3597883,"id":"Q3597883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"176940495184bf298ad4fc06d77e0457b01c3a5b","datavalue":{"value":{"amount":"+0.737160861492157","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":"Q908714$CAAF7252-BE13-4019-A590-902F364B2643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c3b074efccc27c3aa25ebb2b0341556544efffc","datavalue":{"value":{"entity-type":"item","numeric-id":3803160,"id":"Q3803160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f935448282bc888cab85fd72e5c7613d3d1af448","datavalue":{"value":{"amount":"+0.7264289855957031","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":"Q908714$FAF1A6E5-3058-4995-AA19-B58A7492B34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a18e7edf2f9bec8abcaabef97c7e6faffe96402","datavalue":{"value":{"entity-type":"item","numeric-id":4321827,"id":"Q4321827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d92fff5bf96cd765ff515d0a565e220fdc15b695","datavalue":{"value":{"amount":"+0.7259607911109924","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":"Q908714$A4C5B8B8-E415-4054-A13D-E3A32473A210","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Undecidability of the bandwidth problem on linear graph languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Undecidability_of_the_bandwidth_problem_on_linear_graph_languages"}}}}}