{"entities":{"Q1209328":{"pageid":1220077,"ns":120,"title":"Item:Q1209328","lastrevid":66353364,"modified":"2026-04-12T09:31:35Z","type":"item","id":"Q1209328","labels":{"en":{"language":"en","value":"NP-completeness of \\(k\\)-connected hyperedge-replacement languages of order \\(k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167740"}},"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":"Q1209328$181A0066-2A44-426D-9E9D-ABADD72BA9D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4776479bb0038c98249ddc36c7c6746e0cd82245","datavalue":{"value":{"text":"NP-completeness of \\(k\\)-connected hyperedge-replacement languages of order \\(k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209328$78177CAD-4CF7-40FC-B1DE-3E5BF9175A17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd287f812fed764b7aada3f4d8851b98549dffed","datavalue":{"value":"0795.68094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$681112D6-45AD-4C3D-BF25-AFB4D4663446","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a774a2f6aa0936073cba191971e8511d543b1743","datavalue":{"value":"10.1016/0020-0190(93)90221-T","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$77207FA4-C0F4-4ECE-9E06-2474FDDEE5FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"682e36db539370b8b27b5fe80871658238c85e6d","datavalue":{"value":{"entity-type":"item","numeric-id":493118,"id":"Q493118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$ABF0AD9C-B40D-4DE9-8B0F-991936D487C1","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":"Q1209328$73E02191-2BF0-44BD-8179-EA60DF143203","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1209328$24207E45-C50D-4E22-A7B6-C647AD482FC0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$733D909E-C48B-4068-A754-1FFBC01AC113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$AC7FD3F0-35C2-46DC-A998-B9BE7BB68E66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71002b0699ac82d59071d498e2300adf018edf8c","datavalue":{"value":"167740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$79414C62-B945-4856-AB09-C1ABDA42BA93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a76b7c508e87ec06a0a9745793b57a51d5cbcc25","datavalue":{"value":"hyperedge-replacement grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209328$FA927565-4109-454B-BF6C-043CA6A7A437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209328$6D7BCDF2-651C-418C-9F08-381BEC8E0E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"932b6682ce2c6c9dd2fb0583fc208c494132f317","datavalue":{"value":"\\(k\\)-connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209328$A3873625-B2A2-43CB-B928-A20D24D691A7","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":"Q1209328$1991CD15-DBCB-43A6-B842-F171A533989C","rank":"normal"}],"P223":[{"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":"Q1209328$467EB539-2082-490B-A458-E34D751A2C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b0768a48a3af6a2344c40720d67b58bb50a5bd","datavalue":{"value":{"entity-type":"item","numeric-id":1176232,"id":"Q1176232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$66D597C3-F309-4656-AA9D-AD0CD019DAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b2807f3350c9e524cc27528b7acc65cf07c4cab","datavalue":{"value":{"entity-type":"item","numeric-id":685463,"id":"Q685463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$8110D29E-7CDB-4BB6-ACAD-D6F04F80FDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80a176baa2614833dd16169dd2f3bb6bb0e14443","datavalue":{"value":{"entity-type":"item","numeric-id":4037291,"id":"Q4037291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$F6F0FCF8-FC11-4A7C-AA36-DBB6400D90EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$1C7446A8-0454-4347-8DB0-D6BADBFA0AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f9918dd24d68d6a8b0715c23196dc11eb6c8fa","datavalue":{"value":{"entity-type":"item","numeric-id":684560,"id":"Q684560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$B4A1C5CC-CAC3-4119-A467-902B19A86700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"070db90fb7cca5e46644b5c2f053363ea038bfd4","datavalue":{"value":{"entity-type":"item","numeric-id":2277851,"id":"Q2277851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$4BCB2137-7A9B-47A2-989F-A75769AEB05B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24938b6848c4eabdd4779f4e20b48136a3e8c536","datavalue":{"value":{"entity-type":"item","numeric-id":1089809,"id":"Q1089809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$132E29D4-D730-4A9A-9519-BDBB1ECEFB4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb612c1a3bf5ccc5b198a869649c3067be7c64a9","datavalue":{"value":{"entity-type":"item","numeric-id":4037335,"id":"Q4037335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209328$E25A89FF-A9CA-4093-87AD-9F55D30F6034","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a76137fd3ff6fb65417a474b5d71844f3df8644","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90221-t","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209328$9EB543BB-2CB2-48CE-B1A5-FA69BD6FD6D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d4732a739138bc058ebab5c57a70ab2cf3654440","datavalue":{"value":"W2012843178","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209328$2345F4AC-F07F-4555-A84F-D7D72F013B57","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c5540c18f26c011fa65ef07f72ca46aae6183d3","datavalue":{"value":{"entity-type":"item","numeric-id":685463,"id":"Q685463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e23f786efd5d873fe661c058119a2018a4bf6cf","datavalue":{"value":{"amount":"+0.8319913148880005","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":"Q1209328$B5FB8D6E-2A17-4C26-B833-A31F374EB4BF","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":"97d8def78411f790a9d6ea1d7e8b03c8e1bb0381","datavalue":{"value":{"amount":"+0.8319910764694214","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":"Q1209328$A435A7FC-9E95-432A-863A-109FBED68434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18addbd4391d503cf9e191df1012aa17831c6d61","datavalue":{"value":{"entity-type":"item","numeric-id":2277851,"id":"Q2277851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b81f978f9af887c36cd2495e041fa001e34c74f8","datavalue":{"value":{"amount":"+0.830227255821228","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":"Q1209328$4C6F758C-F720-4623-83EC-D2F1E5165619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"944ac686e66cc34faf36d1d0a4c6533e93b89421","datavalue":{"value":{"entity-type":"item","numeric-id":1854438,"id":"Q1854438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b105e9e83a7e5d82b56f2bb1c974d550456f734d","datavalue":{"value":{"amount":"+0.7794009447097778","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":"Q1209328$D2EB9C11-AE34-47C3-A201-7C0C04F93138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4fd5267b969672e86cf09076893bbedaec40b14","datavalue":{"value":{"entity-type":"item","numeric-id":1333400,"id":"Q1333400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f746827f18e43a42bcdf8a113c40e7aa7fd5d4fe","datavalue":{"value":{"amount":"+0.7721046805381775","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":"Q1209328$D71EEBF2-AC75-40B0-BEC6-CF71DF52CAA0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NP-completeness of \\(k\\)-connected hyperedge-replacement languages of order \\(k\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/NP-completeness_of_%5C(k%5C)-connected_hyperedge-replacement_languages_of_order_%5C(k%5C)"}}}}}