{"entities":{"Q794169":{"pageid":796017,"ns":120,"title":"Item:Q794169","lastrevid":48710839,"modified":"2026-01-05T16:43:39Z","type":"item","id":"Q794169","labels":{"en":{"language":"en","value":"Two-dimensional alternative Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3858414"}},"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":"Q794169$12787170-0641-430F-A3EE-FA7DE67686CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5eaa5fff532518090c6631cc870999a4db9581a1","datavalue":{"value":{"text":"Two-dimensional alternative Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794169$0BF597E1-8FCC-4544-8067-248FF6A094B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7505f734f7f442f55ab7bd58a5c558095404e0d","datavalue":{"value":"0539.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$0D860CDD-830E-442D-8FEA-97AF82E6B068","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35e00fe0f11444b80605b68c28e30b32679c47db","datavalue":{"value":"10.1016/0304-3975(83)90093-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$CB7C7427-4B83-4B32-9633-98689A242859","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31bccc448a658f3cebcea86acdb202419da8ddc4","datavalue":{"value":{"entity-type":"item","numeric-id":235704,"id":"Q235704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$5ED9B06A-15F4-4A24-991B-67F453D42B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7ca1ef17249af5269bfc02ced493a4476940cd","datavalue":{"value":{"entity-type":"item","numeric-id":593782,"id":"Q593782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$24E94560-389E-4F9D-9082-B71B15E2E387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"82a53663cfa905d5404409589cc6c9ad6ae3c848","datavalue":{"value":{"entity-type":"item","numeric-id":593783,"id":"Q593783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$308CA155-891E-4AEF-AE9A-DB477482B4CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$DC9CF5B4-1FAE-4F0F-BB46-4A6C19F9834C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q794169$55E4C1C2-AA0D-449B-9E6A-C266CBD45E26","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa38103b904de7d89ba4d390d25f04193671849b","datavalue":{"value":"A two-dimensional alternating Turing machine (2-ATM) M is a natural extension of an alternating Turing machine to two dimensions. It has a read-only rectangular input tape with special boundary symbols, one semi- infinite storage tape, a finite control, an input tape head and a storage tape head. A step of M consists of reading one symbol from each tape, writing a symbol on the storage tape, moving the input and storage heads in specified directions and entering a new state in accordance with the transition rules. Similarly, a three-way two-dimensional alternating Turing machine (TR2-ATM) can be defined. Acceptance of input tape x by 2- ATM (TR2-ATM) is introduced in a natural way.  \\[  T(M)=\\{x| M\\quad accepts\\quad x\\}.  \\]  The authors investigate a relationship between the accepting powers of space bounded 2-ATM's (TR2-ATM's) and space bounded TM's (TRTM's) and show that, for some space bounded classes, 2-ATM's (TR2-ATM's) are more powerful than TM's (TRTM's). Next, they introduce leaf-size for 2-ATM (TR2-ATM) on a given input as the number of leaves of an accepting computation tree with fewest leaves and provide a spectrum of complexity classes based on leaf-size bounded computations. Finally, they investigate recognizability of connected patterns by 2-ATM's (TR2- ATM's) and formulate some open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$4CCDC9B6-D01F-4B40-B434-624F6E1039FD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"81f6c4acc14213666fc75fd9b7e3778359d51d7e","datavalue":{"value":{"entity-type":"item","numeric-id":593721,"id":"Q593721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$3D5BB17B-D418-41E4-A33E-0DFBF09D34B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$3BE9CB29-8E6C-452A-B361-B741384ED579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$49AA2C05-DBDE-489A-A2A1-9AA15B0DD8B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c714108e0e771fcd382eb6103032e74b27a37400","datavalue":{"value":"3858414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$E0BFCC59-F4E5-40A5-B19E-6D2019D66407","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa0e2388c8e3a79e9b7ba1fcca39fdd718f3ddb7","datavalue":{"value":"space bounded Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$F1158F3E-A6C6-44F7-8380-7470D7F6E19A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1bac7ccf4627d13404ea88f372e6009b64bdd77","datavalue":{"value":"accepting power","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$481C910E-EAFC-4F35-A35F-277BFFA1DDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74fd6cab38a4fe863514477cdea74db06fabbe7d","datavalue":{"value":"two-dimensional alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$E9C2FC9D-11A5-4ADD-AE0B-336BAB48956B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6834df05b67bb082de1ad36e25129375460a861","datavalue":{"value":"three-way two-dimensional alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$EE62C7CC-1B18-4179-8D5A-FA07F185677C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$95B96AD9-315F-4A6A-B3C1-648F617475D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a99cd56ddb60189a7df4b1b9ecf795775814f38d","datavalue":{"value":"leaf-size","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$A41173BE-F8B8-4D2A-AAF3-01973E7936F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a29953e7ce676d7e017019f6014f0e697747b78","datavalue":{"value":"recognizability of connected patterns","type":"string"},"datatype":"string"},"type":"statement","id":"Q794169$80D51A88-3B4F-4057-812F-A4070E8B5802","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":"Q794169$62CBDB1B-9EC2-4D87-8A19-520B57665492","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18444b29535a3d83523a415d3a08b709f1da072b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90093-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q794169$668340EC-2835-4399-BECA-DF386BD32F7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d5238b06407284a7bd8183a7a4edc760bf79f6d4","datavalue":{"value":"W1967725522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794169$B8D5D72F-DF7E-48BC-85E8-F51DA50F1BEB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a48351eb9ce98139556478b870511c74c7f43f4","datavalue":{"value":{"entity-type":"item","numeric-id":3926078,"id":"Q3926078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$C2845D1B-5710-4379-915D-0D633F7D2A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ef7bd7394b9409f78a70f5079209997174566e6","datavalue":{"value":{"entity-type":"item","numeric-id":1143799,"id":"Q1143799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$0AC60119-A61E-46E3-99EE-99C9D44CAC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c176415183c1e77fe1c010e0980a5409e1dfd1","datavalue":{"value":{"entity-type":"item","numeric-id":1244324,"id":"Q1244324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$52266A97-29B2-4401-80BE-35E93AA2D7C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3624b66ba6cd2234f5abfe88bc5b9034ae99a075","datavalue":{"value":{"entity-type":"item","numeric-id":1140989,"id":"Q1140989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$2EC6FC2A-3BA3-4795-A541-3F25F10D728A","rank":"normal"},{"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":"Q794169$1E2309DE-C526-4EFB-B791-36CE79A1538C","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":"Q794169$9B33B9A8-4068-4863-A58B-386CD1E8F9D8","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":"Q794169$020560E4-5D96-4D74-8FC4-1BDF7BC779A5","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":"Q794169$30EA1962-99C6-47B3-AAF9-55AFFCF78459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$CAFA6D46-2A97-4050-B0F1-FF27994FAFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a589b2b8385ccd4be46b5ea02a14f7621bb80bc","datavalue":{"value":{"entity-type":"item","numeric-id":1141480,"id":"Q1141480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$33C9C73B-0AA8-4602-96AE-B8B3246C63F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fd15c28f5ef520130bce603b2250150839dfad6","datavalue":{"value":{"entity-type":"item","numeric-id":1146515,"id":"Q1146515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$B2296B4B-CA4E-4EE5-A649-7D5DDFE42189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1306ccc0966d1a78a1cf952019aaa3d39c3785e8","datavalue":{"value":{"entity-type":"item","numeric-id":5661163,"id":"Q5661163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$7BD8CB1A-E678-4F7E-853C-5233BE1179DB","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":"Q794169$8BFD770A-EB05-45AD-9A8D-1CFC8B3D02B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b29697d8f3dda53db49300c16b49a4c72896f8e","datavalue":{"value":{"entity-type":"item","numeric-id":3221411,"id":"Q3221411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794169$573A6B3C-F55C-4B11-BC7C-281973CF3F70","rank":"normal"}],"P1643":[{"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":"8bcde0764122fa2393cd1f1825e1ff26ad3744ae","datavalue":{"value":{"amount":"+0.8848118782043457","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":"Q794169$189C7CDE-4CE2-4575-A416-6AF666A76298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be94e4faf40150e94493f80c5ee6a67dc33147f","datavalue":{"value":{"entity-type":"item","numeric-id":3221411,"id":"Q3221411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5ec2fead795c06c3de225e53fb8fbe2d53ee055","datavalue":{"value":{"amount":"+0.8337258696556091","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":"Q794169$57CBCF41-DF8F-44FF-99C4-31566FF53BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94269aaf2431d9f23bc197e46731f853b198bd4b","datavalue":{"value":{"entity-type":"item","numeric-id":3785943,"id":"Q3785943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88146c636c30bec9646980b61c1292fabb1284bd","datavalue":{"value":{"amount":"+0.8295556306838989","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":"Q794169$CBA1D662-7B4E-4CBE-AE04-17349046D617","rank":"normal"},{"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":"2ba4970d168b5f3c1a0e1bd5221995634b9b9b20","datavalue":{"value":{"amount":"+0.8213218450546265","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":"Q794169$F49B5C5B-653E-455A-A0AB-F77A1A1ED30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"272b28d0646a09668c88da5432117faa77b0d716","datavalue":{"value":{"entity-type":"item","numeric-id":1822969,"id":"Q1822969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39467c92fee7dc25df502a59a1206d702bfb8e45","datavalue":{"value":{"amount":"+0.8159560561180115","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":"Q794169$B5F3B474-B42B-49A9-8050-F926F95BFD8E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794169","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794169"}}}}}