{"entities":{"Q1822501":{"pageid":1833243,"ns":120,"title":"Item:Q1822501","lastrevid":69237717,"modified":"2026-04-13T05:40:32Z","type":"item","id":"Q1822501","labels":{"en":{"language":"en","value":"Domino-tiling games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4003530"}},"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":"Q1822501$B6AEA309-F74F-4A4C-BE94-DE9E319E61BE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c270e6481920b47db8bf6e507a05200aa4643c0a","datavalue":{"value":{"text":"Domino-tiling games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1822501$9DF4BC7A-B985-4C02-983D-CA480365EA51","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c520c1362f604df6ef98afbede9a35dbd0950bde","datavalue":{"value":"0618.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$A01968D5-BFC2-4C20-A98E-090DB0A34BC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24c7ec0a549462d9d162aa88b1753b8af2f76495","datavalue":{"value":"10.1016/0022-0000(86)90036-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$FF86F559-796F-4856-9251-0B62DB82E51A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a81ee3d22f4d6472094917e6f4d497a318f69849","datavalue":{"value":{"entity-type":"item","numeric-id":529039,"id":"Q529039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$9BC490B6-466B-475E-AA49-7C9A6ED524F9","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":"Q1822501$11F09176-7E8D-41A6-BC84-1B4F29DF4E8B","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":"Q1822501$028AF4BC-843B-4F0D-880B-73BAE5898E70","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c42e594b575d456c9966727ce32c6037d0143b10","datavalue":{"value":"The paper presents the application of the Domino Problem into the complexity hierarchy. It is well known that some infinite planar cases of the Domino Problem are unsolvable. When the game is restricted, we can obtain some complexity classes. Namely, the Square Tiling Domino Problem is complete in PSpace, while the Rectangle Tiling Domino Problem is complete in ExpTime. For some more complicated restrictions the author found a tiling problem complete in ExpSpace and another complete in 2ExpTime. The paper ends with some variants of propositional program logics and their complexities are characterized.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822501$DA7C249F-AF4C-448B-A13F-76D71D5CB87F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$EF1E2BC6-6745-4404-862C-29E8F9ED41FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$185F9303-AA5F-45BC-BD56-654482D1F511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4920bcb5055cf3da94830f00d832c01308357d4b","datavalue":{"value":"05B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$A2763F34-BFB4-4952-9B25-823521053E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5c83f057600e5614b7fec59c8e4ac61cb41ba8d","datavalue":{"value":"91A80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$64F16AFF-FD73-412B-BD5D-2BDF05D22649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$2A3D2875-7013-42AC-9AD5-9F64DC3A9B0A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c8d0abe43bd56012b9938e379ef7e271cc9ac957","datavalue":{"value":"4003530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$0C06FDA8-4592-4668-B469-7DBC84589E70","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7fd4056a0d4db9fdd2e24e5cf7d02ed6e201c3d","datavalue":{"value":"complexity hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822501$28950BFD-FA40-47DC-A276-18DE745F91A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f921a35444ea19ed1a628f794d1bf27df7b0a74","datavalue":{"value":"Domino Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822501$0E322644-8A02-4179-8EE9-145D4CE24D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0470d7a9698e5ceba3367e54959ca52af6c7553","datavalue":{"value":"tiling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822501$95F92076-7735-4C63-A719-8C2DF178E7AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7723df44e893bdb88a9f52ab419a67820f11bd","datavalue":{"value":"propositional program logics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822501$F7F7672A-AA63-462A-9D7A-30A3D4EC041C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e797ff6dfa70600e9bb936f295518376bb337227","datavalue":{"value":{"entity-type":"item","numeric-id":794424,"id":"Q794424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$121CB055-C8FB-40B0-9E5C-422747A5DDE8","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":"Q1822501$B558E34F-6EA4-4E6F-9A6E-18AFB346A0E2","rank":"normal"}],"P223":[{"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":"Q1822501$B3FD8BA7-EC7D-4962-B1E1-ACE84623D7BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$D0C3E4A7-CBDF-4677-9030-0D2B63B93A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48a859b16fe34310ce0f7bbe2e1264b8a4b3ada4","datavalue":{"value":{"entity-type":"item","numeric-id":1170028,"id":"Q1170028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$F6A8B752-6EC9-40EA-BB8A-C5977A64AF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47c57a1bc98a9d819c8c4b25347f0c45d96256b1","datavalue":{"value":{"entity-type":"item","numeric-id":1258296,"id":"Q1258296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$2CC9E29D-FF55-4DFE-AB5B-B01287ECD397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8813798412dbe58d57f2de6fe92173b4bf5c980","datavalue":{"value":{"entity-type":"item","numeric-id":1156090,"id":"Q1156090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$A2ED978A-A526-452D-89AD-1C81618DF0F8","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":"Q1822501$90B4E5D7-4391-4169-A989-D75F739754EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbf1ba170fae28e63e92407b948b3875ee6ea399","datavalue":{"value":{"entity-type":"item","numeric-id":3313253,"id":"Q3313253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$1CA5CC35-03BA-43EF-B925-AC34A1D2312B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a1abf0ec1abf337ad5daf1409b3e69fe79a4c97","datavalue":{"value":{"entity-type":"item","numeric-id":5526975,"id":"Q5526975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$BEED4DBF-F313-45CB-AAD0-CE290E5AD498","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":"Q1822501$AA6B6509-6972-4163-BB6A-62B3AFC779AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$7A00CF07-C160-484B-8EF0-69D898C9664C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eda2db14c950cfacb2d9bab387b35d1aadfc67b0","datavalue":{"value":{"entity-type":"item","numeric-id":3284606,"id":"Q3284606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$F0BE51B0-9F54-42B8-BFD1-4C2C1BC26E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f66774e18bf6d9e857072576d53e1307dde765","datavalue":{"value":{"entity-type":"item","numeric-id":4149442,"id":"Q4149442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$EF1B78A1-E7D6-476F-9B8B-8567D5AC0E8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"446f1e7359d727b7ebadf68424d4ea447292feff","datavalue":{"value":{"entity-type":"item","numeric-id":3856727,"id":"Q3856727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$DD8211F1-3F2E-4A9C-B217-BF5E7323489C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f28db7f96068e5ce3938c306e6d15e9aefa614","datavalue":{"value":{"entity-type":"item","numeric-id":3915990,"id":"Q3915990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$9D263860-D930-4356-A0C8-C1E3FACDE64A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0d71b5e1cf68927e05cce9da9c6f8031ac8361","datavalue":{"value":{"entity-type":"item","numeric-id":5186732,"id":"Q5186732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$FCD7B9B1-5510-4252-A3B6-B86F3BCA0A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$DF7F5936-289D-4BFF-B87B-65EA0134421E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc419969a8aad450cb9de70ca2e1a6cef07c697a","datavalue":{"value":{"entity-type":"item","numeric-id":1235980,"id":"Q1235980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$3A8C8A00-FD4C-4293-8E6A-9F6893109F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$0CD9B33C-67D7-4688-9411-4077F779BA57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"348ea46eb2336e82df887e43a2ff889e1f10ee80","datavalue":{"value":{"entity-type":"item","numeric-id":3854623,"id":"Q3854623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$96E735F8-77D0-4853-B3C3-9634CEFB3DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822501$F7224906-5712-4D15-BC41-836DABBA50A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4911fd46c187e8add8f9b045c40a0e8859567bd9","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90036-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1822501$A740E2B5-4644-4968-8B20-495AF3E41C20","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5174c9bb3343507fca377a1d2bc68a7571bbe9ea","datavalue":{"value":"W2030473999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822501$64CA60E1-200C-47DB-B5D1-4C1556F1E14C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ab1d52ce83b09ba416c61f6680980bc2cc0964a","datavalue":{"value":{"entity-type":"item","numeric-id":3015025,"id":"Q3015025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91a64371285b8488b09338445dfb0e97a878a12","datavalue":{"value":{"amount":"+0.8758278","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822501$814D8EAF-0F5D-4B69-930E-9D7996BE7AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36ece034953f835510446e01c8af141af86d0ce9","datavalue":{"value":{"entity-type":"item","numeric-id":6184362,"id":"Q6184362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8059604d2ff1fb11e996bb51a9d767798a007399","datavalue":{"value":{"amount":"+0.87501806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822501$A5922955-D2CC-4595-97DC-D10AD8F926A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd512981ce5b314ef9d39ef256c20ca7cc9ab169","datavalue":{"value":{"entity-type":"item","numeric-id":3495644,"id":"Q3495644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43f8f8a2f46c254f37e0e434831e9b72d3dce5b1","datavalue":{"value":{"amount":"+0.8582418","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822501$A5B1E34C-3706-489A-BA60-8FD4AA18B352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d2f6ac3e1feb879c7b5151549bfe7ab191bc961","datavalue":{"value":{"entity-type":"item","numeric-id":757389,"id":"Q757389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b5b970b71298d96cd5a816aa5c5a4dc7913da63","datavalue":{"value":{"amount":"+0.8529294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822501$F8400A0A-EEC6-4D4D-B639-E40A0FB7C3B3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Domino-tiling games","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Domino-tiling_games"}}}}}