{"entities":{"Q4968744":{"pageid":6998323,"ns":120,"title":"Item:Q4968744","lastrevid":91840649,"modified":"2026-06-05T00:12:24Z","type":"item","id":"Q4968744","labels":{"en":{"language":"en","value":"Optimal state amalgamation is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7077689"}},"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":"Q4968744$BF9FB657-6030-43B7-A1D8-58F3A2CCBD10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b1f44d027801a91686ee3e7d0e4775f7ebcc0f0","datavalue":{"value":{"text":"Optimal state amalgamation is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4968744$C2D76F6D-09DA-429B-A9E6-92E9AC48FC18","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2084dcde2d23078482949ecdabdfdb4fc4f5c7f0","datavalue":{"value":"1420.37006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$7C044D63-655D-4255-84CA-D483CFC4B072","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"99442f66939e315e7ccd2754c0403bbae45d3979","datavalue":{"value":{"entity-type":"item","numeric-id":2023450,"id":"Q2023450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$A04FF0BB-1C02-4842-B30F-78DD31B3B38E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6ee128f44ab6649bf8f88b399c729fa445b5433e","datavalue":{"value":{"entity-type":"item","numeric-id":2709586,"id":"Q2709586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$1CC89873-6821-4234-8A53-B4BDA28885AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19203015c5ae8999881faf8ed980e2f57e43af95","datavalue":{"value":{"time":"+2019-07-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4968744$97BA0232-E2F6-4FB0-8E45-FF9412FE6B7B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf529d0083899ec8216fc61a03b117d808faad5d","datavalue":{"value":"https://semanticscholar.org/paper/ed971a0ce3a30b5f2d3c8648bfef70870a32b43f","type":"string"},"datatype":"url"},"type":"statement","id":"Q4968744$04821F45-E8A5-4D16-BD9D-B9A9B43ED7AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b559307b5b2969939e6945d65ee127220f8f6f4b","datavalue":{"value":"37B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$1CA4EE12-9765-421E-92B8-D22F0AB1399D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b9ca13b65dfaefefd0c02f3f6d7e1635431e9adc","datavalue":{"value":"37B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$F6B71DAA-E31B-4694-8F82-081E5CA65974","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5b773c66ea5e726efe1ed2b46492dda51a7ff93","datavalue":{"value":"7077689","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$C130ACFC-D777-4822-8DF3-894DB2DD1E21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"001761d70988821ac402d2bf60499c84214e22b7","datavalue":{"value":"subshifts of finite type","type":"string"},"datatype":"string"},"type":"statement","id":"Q4968744$A1A77F90-0004-4BDD-9850-AB7EBFC5D19D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fccb19bde191b3d4cb60ffaaf1d6345fcbcda2e4","datavalue":{"value":"conjugacy","type":"string"},"datatype":"string"},"type":"statement","id":"Q4968744$AF7C0192-6E9B-493B-9402-B1E7ACCDE56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a718378fce98318a1719ba415f380da2d155a5e","datavalue":{"value":"state amalgamation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4968744$8F57C1CB-1569-4037-9389-2B324E20EF75","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":"Q4968744$37D19179-D01D-4F93-B96E-AC018E969882","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dc8e056fb2120018f209d1179ac6f63152ee4b56","datavalue":{"value":"W2767222152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$95B68B5F-8223-4924-AFC0-12FB9496D623","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee0226813201cdbae6de7507fed9be433cdb152","datavalue":{"value":{"entity-type":"item","numeric-id":4383200,"id":"Q4383200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$71DE05B5-F9F1-44C6-9C48-D99BF931925A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67304e11849d33fd06f64677cce3692c8bf50b75","datavalue":{"value":{"entity-type":"item","numeric-id":5569245,"id":"Q5569245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$B889F92B-0621-4DA6-8602-93FBA03AA990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7286a7172b6924ec33ee89b09eceafc7e8f68f8","datavalue":{"value":{"entity-type":"item","numeric-id":1758160,"id":"Q1758160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$E001BABB-F465-4C07-A9B8-720D7895B5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3e0bf6d66ae7c4b6b46e88d6d5b96072d8e8fa","datavalue":{"value":{"entity-type":"item","numeric-id":5597521,"id":"Q5597521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$96F7E622-3BD6-4B84-ACC0-4872FC919272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3006e0669c72796d2f6beb32650d4c05f10227f0","datavalue":{"value":{"entity-type":"item","numeric-id":5610308,"id":"Q5610308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$95B883DF-40E4-442D-AE9C-CAEB30CD2EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be0e7e376995dd653d62b263eb50409e3d8e57dc","datavalue":{"value":{"entity-type":"item","numeric-id":3545300,"id":"Q3545300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$DBC1F68D-2DFD-492A-9BD7-2987BFB140F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7c799623c4b66af60a041ac848a3d10a9048afc","datavalue":{"value":{"entity-type":"item","numeric-id":3744432,"id":"Q3744432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$6DC96221-8E3C-4039-8812-240CBA61E6CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20f232fcd0378e45dd2949a43ee5cfb5be258b1e","datavalue":{"value":{"entity-type":"item","numeric-id":1181316,"id":"Q1181316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$9F61C088-DC76-4F49-A6A0-7FF81DA08119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f21fc0c049fe005433501e9f9999bb3074bba78","datavalue":{"value":{"entity-type":"item","numeric-id":3624492,"id":"Q3624492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$B712CE1E-E7A1-4E34-844E-13773C6F35D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a312e4457ce24823d78a6c0f467639d9459cf475","datavalue":{"value":{"entity-type":"item","numeric-id":5958128,"id":"Q5958128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$7BE14D24-FC1B-4231-A8BE-25C4E4EC9B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4f0732f471883320ebec889a518f3eaf523eadd","datavalue":{"value":{"entity-type":"item","numeric-id":5900112,"id":"Q5900112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$848F5BB2-E28D-42DE-A8CD-94C91A471C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6245d4b3f334b71c689095b4d80c79d574627b2","datavalue":{"value":{"entity-type":"item","numeric-id":4663997,"id":"Q4663997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$882C2180-CDD2-4401-A8EF-6D07952D6252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba6262c247b0eefb5f0793844714a87aab33088","datavalue":{"value":{"entity-type":"item","numeric-id":494068,"id":"Q494068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$69A1188E-0DA6-429E-9029-4A7C85D8DA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7712254d1976bceac1ace08a0a503367328dfac8","datavalue":{"value":{"entity-type":"item","numeric-id":4235564,"id":"Q4235564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$4D67AE0C-FBF0-4273-A6FE-044FBB2901F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"274e7455901a0e9af0fc071cc118c2781f92ed0a","datavalue":{"value":{"entity-type":"item","numeric-id":1351451,"id":"Q1351451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$67BB3976-FCE0-4217-8E8D-E6010A4FD72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33bc8328c0e7b9a05dbd6858f99412be5208fd3c","datavalue":{"value":{"entity-type":"item","numeric-id":4850282,"id":"Q4850282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$DFDDD0A2-BF36-410D-8A6A-A5BA168EABAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$443DCD59-4C1D-4516-8EE1-4ABE6F08C994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6026c7a98cf28cdf5539ab30d14108333c76eb6e","datavalue":{"value":{"entity-type":"item","numeric-id":4373838,"id":"Q4373838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$6814DCA6-9BE7-4121-B168-41E48405B6B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"022732c04cdc552e968c6b6efd98aabacc7fcc0b","datavalue":{"value":{"entity-type":"item","numeric-id":3977342,"id":"Q3977342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$218C0945-42F4-4CDA-9135-418D230D5E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71de3f2ea38d5907966f1c5de4845c210a2e2d80","datavalue":{"value":{"entity-type":"item","numeric-id":1376246,"id":"Q1376246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$C1BC0B8A-6CDB-4B07-BD53-8E31DA1BC72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93c253900e4829cb5d0d6d60e214b68399dc4e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4856597,"id":"Q4856597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$9FF4604D-674E-4BDE-A402-7FD7E5138DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c04a1a68725257e1587ae3a340f8303d1542d037","datavalue":{"value":{"entity-type":"item","numeric-id":2776514,"id":"Q2776514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$F4E3B57D-D818-4DA3-8E8D-10675483CAE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6a48c4d2a17c691b4afb71668f6a076769b0237","datavalue":{"value":{"entity-type":"item","numeric-id":2535143,"id":"Q2535143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$3DF18FFB-1230-4D27-80CC-DBE5301E6114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9030da75814affaf32545053edd030fae7243fbe","datavalue":{"value":{"entity-type":"item","numeric-id":2538784,"id":"Q2538784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$A8D4EE65-6FBA-41D4-AED2-BCDD90BC607A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a8e786b483833affc512f813f9fe3020558e27d","datavalue":{"value":{"entity-type":"item","numeric-id":5251243,"id":"Q5251243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$81C93E8C-F493-48FE-95A4-987533F160F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d84d2e6a8301b2588d88e8d81aeab835a6cf462c","datavalue":{"value":{"entity-type":"item","numeric-id":5941276,"id":"Q5941276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$C6C1B42C-EC35-40F7-A051-22CB9481DFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09f2ace7b839b3d529d46c96ee967961bf8f5339","datavalue":{"value":{"entity-type":"item","numeric-id":5615935,"id":"Q5615935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$7410CE9B-096F-499F-8EE9-3F35F8E0FA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003961228078b0c11edfaf7a8dc0ec4da8ff739f","datavalue":{"value":{"entity-type":"item","numeric-id":1844005,"id":"Q1844005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$89DE2F7A-2577-4DB7-894C-7872234FE490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"291758ae2a7326b6ae2e83a863d9731611597816","datavalue":{"value":{"entity-type":"item","numeric-id":2442483,"id":"Q2442483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4968744$62898294-0BB6-4AC2-A4EB-790A82531082","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08d89a6e08b4932b31c1b680362e7241c6f702eb","datavalue":{"value":"10.1017/ETDS.2017.105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4968744$150347B3-8B0C-447D-A011-D5F5BC0FD025","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63c34d0539af4519aa8517c09aadd0a492fe15d5","datavalue":{"value":{"entity-type":"item","numeric-id":2219057,"id":"Q2219057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3161b696346a05988d24ec1bc703ea76bfc0ead7","datavalue":{"value":{"amount":"+0.7142006158828735","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":"Q4968744$B1D12CBE-9A34-4A45-B8C3-B72A17C713E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c905ceea9e2dd811c428fb9f7cbbbc96a886f61b","datavalue":{"value":{"entity-type":"item","numeric-id":494068,"id":"Q494068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d2be43e3b97899f55b294e6a508c71c28e15bec","datavalue":{"value":{"amount":"+0.7039316892623901","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":"Q4968744$C1DA0089-A6D4-4535-BCAD-54D555B801B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ebfdf69e6b9581ca75de6bbf3e1bbb31dc3a08","datavalue":{"value":{"entity-type":"item","numeric-id":3502829,"id":"Q3502829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44c342b2147a1dcf9e7190214f8d5d34c44f10bb","datavalue":{"value":{"amount":"+0.6767839193344116","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":"Q4968744$CB671E02-406B-4115-ACEC-4E920E435798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2402a9f13ba3afc50d984f154afcb9e57906f628","datavalue":{"value":{"entity-type":"item","numeric-id":355379,"id":"Q355379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89367936e6f187a16206f8d5261a4bb4ad3dc7fb","datavalue":{"value":{"amount":"+0.6648642420768738","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":"Q4968744$5154F3EF-21DF-4324-9ED1-552322112446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9b0a892ffee3bbecc2e84d389ebcb706d2d0cc5","datavalue":{"value":{"entity-type":"item","numeric-id":2957910,"id":"Q2957910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"666fb609b5a1d5a263062a56c0a063cc9dbdef75","datavalue":{"value":{"amount":"+0.6627790331840515","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":"Q4968744$71DE91B1-F7EF-4984-BF17-59F3724475B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal state amalgamation is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_state_amalgamation_is_NP-hard"}}}}}