{"entities":{"Q1116697":{"pageid":1127446,"ns":120,"title":"Item:Q1116697","lastrevid":69680850,"modified":"2026-04-13T08:40:22Z","type":"item","id":"Q1116697","labels":{"en":{"language":"en","value":"On three-way two-dimensional Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090804"}},"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":"Q1116697$C85D355E-877E-47B0-9A32-2EBB18700FCF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00452753383759fe373857f28b2588ac3edc7412","datavalue":{"value":{"text":"On three-way two-dimensional Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116697$77999BFA-B991-420D-B921-75CCE7D06EC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16217fba2dea9c1b274dc7ee3310e2e08aa8ac3b","datavalue":{"value":"0666.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$6E5B2CEE-B0A9-49DD-A79C-933C5C5411C4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bbc4c0f79a00946f1a520a8e74ba232efb8a72c8","datavalue":{"value":"10.1016/0020-0255(89)90010-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$EA2E729C-7D58-445F-B411-A43D205C404E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab04ccff5257bfd7d9df0e67238421f4fa3b71ef","datavalue":{"value":{"entity-type":"item","numeric-id":293472,"id":"Q293472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$BB21841E-60C0-443C-AA2D-5AA90E68CB09","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$DE9848EB-A2A4-4B7A-979F-663338BB183D","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":"Q1116697$CCC31523-00F8-4507-AB4E-11886619279D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae39bc66ac7456dccd4f21a6c4e5b82eb4662fa0","datavalue":{"value":"This paper solves several open problems concerning closure properties of three-way tape-bounded Turing machines. It is shown that: (1) the class of sets of square tapes accepted by nondeterministic three-way L(m) tape- bounded Turing machines is closed under complementation if \\(L(m)\\geq m^ 2\\) is constructible, (2) the class of sets of square tapes accepted by nondeterministic three-way L(m) tape-bounded Turing machines is closed neither under row nor column cyclic closure if \\(L(m)<\\log m\\), (3), if \\(L(M,n)=mg(n)\\) or \\(L(m,n)=g(m)n\\), then L(m,n)\\(\\geq mn\\) space is necessary for the class of sets of (general) tapes accepted by deterministic three- way L(m,n) tape-bounded Turing machines to be closed under row or column catenation, row or column closure or row or column cyclic closure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116697$F474A6CF-DDB4-4609-AABF-023E51F0488C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$34FAAA8B-058B-42B5-83C4-B6124B60695C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$5FDEADAA-505B-45C4-A88A-6F5C78809972","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf65bdcbd5608d1c8a7087fd452df33bf0a77356","datavalue":{"value":"4090804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$023447AD-3BF6-45E8-BD30-920224E57F67","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9a7b03c1290f4420f511d8fcb71a4d38b5c445b","datavalue":{"value":"closure properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116697$B54024D8-9CB2-46BD-907B-56C3626D9DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67d7b5cf5b34c7a0fed5efa9452932752fc8ee93","datavalue":{"value":"three-way tape-bounded Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116697$4F840C92-1D03-46D2-B053-9F5F40B4B458","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":"Q1116697$81BCD5CC-261E-4D33-AB30-2D1377DFFA37","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"034e0f41115caf9ebf8b4859a5a8f687a2f71ba8","datavalue":{"value":"https://doi.org/10.1016/0020-0255(89)90010-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116697$CB2E9E87-C0C4-4B4B-923D-66F5BB25F74C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aafce59142810a89a91457a0df1d6558e3084555","datavalue":{"value":"W2043305634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116697$2A6DFC2B-740C-4187-B6B4-06C2848D0A7C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"91e1d37e684bb3d2b6019796d7ad83dbf1414d87","datavalue":{"value":{"entity-type":"item","numeric-id":1143793,"id":"Q1143793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$05379299-693E-4C88-B070-F69AD4C2AF08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68238828d0b82166bcbb36333a0c671b7b5989ff","datavalue":{"value":{"entity-type":"item","numeric-id":1143794,"id":"Q1143794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$A4088DA0-7366-49B3-8FA9-7F012CF95F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d767545a253faa896d24d2e4114aa507009568","datavalue":{"value":{"entity-type":"item","numeric-id":1148677,"id":"Q1148677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$A3D96073-F69F-46E7-A3C9-E0F3DEAD7BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116697$D40EA369-0F4D-4890-BF03-912BA89A4440","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d60e7c412678949c9420e4ab955090b32cf58ee7","datavalue":{"value":{"entity-type":"item","numeric-id":1857029,"id":"Q1857029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a91eea9621c934fd8f714970e2834c1212cb609","datavalue":{"value":{"amount":"+0.8287365436553955","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":"Q1116697$9C157C34-7DC9-420A-94BB-B736E1608586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5c923984baa1ba45ca8bd1c378ab3feadb05daa","datavalue":{"value":{"entity-type":"item","numeric-id":1112612,"id":"Q1112612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7da39129bc92702341e87faa0201c6cb6d1dd0e3","datavalue":{"value":{"amount":"+0.8137859106063843","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":"Q1116697$E85D5195-4C3E-4320-927B-A9A5807D391C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e89f00f23f7e7f565cf8e400d65adc4a33787517","datavalue":{"value":{"entity-type":"item","numeric-id":1818780,"id":"Q1818780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1689ab9997dabcb90d41cde410cfabe893acc3f","datavalue":{"value":{"amount":"+0.8092696070671082","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":"Q1116697$175611F1-68D3-4ECE-A9BE-F6BB3E62A130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8496b1c7696049784e4f023ab771e84a6d4c51a5","datavalue":{"value":{"entity-type":"item","numeric-id":1129412,"id":"Q1129412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1689ab9997dabcb90d41cde410cfabe893acc3f","datavalue":{"value":{"amount":"+0.8092696070671082","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":"Q1116697$96BF8190-F29E-4385-A156-18E473EEBD7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"944bad8647a2ad95ffe60db64435a34f2c8c3fa6","datavalue":{"value":{"entity-type":"item","numeric-id":2638802,"id":"Q2638802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6288d3f04f446333b92d07b71c901846d57bb117","datavalue":{"value":{"amount":"+0.8024242520332336","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":"Q1116697$79DB52C9-6AA6-469D-894F-8F60F8857AFC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On three-way two-dimensional Turing machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_three-way_two-dimensional_Turing_machines"}}}}}