{"entities":{"Q1104746":{"pageid":1115495,"ns":120,"title":"Item:Q1104746","lastrevid":66725877,"modified":"2026-04-12T12:26:10Z","type":"item","id":"Q1104746","labels":{"en":{"language":"en","value":"Geometric problems on two-dimensional array processors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4056998"}},"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":"Q1104746$8F00E440-ECF8-4696-B47A-A485FD872912","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5bf7fb3c72a15ef93ac27fb11f73755e8b4ea57c","datavalue":{"value":{"text":"Geometric problems on two-dimensional array processors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104746$FECB1A67-93BC-4EAB-A8ED-C3653E96092C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dcf3701329fedffa92c174da667f8edac0aac2f","datavalue":{"value":"0647.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$DE228799-4FBF-4153-A5DF-67CE23520577","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25567960d79ae87529e5434ce8ad9cb3b450bb40","datavalue":{"value":"10.1007/BF01602097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$7BF289C4-B2BF-4A2D-B2BB-C8BA58E30C60","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c884c24dfeef58490468e4a31b3d5a83bd656d75","datavalue":{"value":{"entity-type":"item","numeric-id":671388,"id":"Q671388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$6FEA1F8A-1579-464E-B3B4-4B2B609650E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb4e70dad0d94959eb3446d58cc402c772bcea11","datavalue":{"value":{"entity-type":"item","numeric-id":818671,"id":"Q818671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$7C55B47A-C72A-4074-8491-49C272579B6B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"25364cb6f58b827e4119f8c3b4fe4fd58b63c477","datavalue":{"value":{"entity-type":"item","numeric-id":163034,"id":"Q163034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$8F34F2FC-6973-43A9-8CF6-98F6F2C10DF5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1104746$7C571393-A25B-41DD-B957-D9901611C571","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c82139cec710f0b77049353ccee9d7272cdb7002","datavalue":{"value":"Parallel algorithms for solving geometric problems on two array processor models - the mesh-connected computer (MCC) and a two-dimensional systolic array - are presenteg n) space.    Theorem 3. If an \\(\\omega\\)-language is not recognizable by a FDA then it cannot be recognized by a 2-way TM in o(log log n) space.    Furthermore, theorems 1-3 show that there are complexity gaps between regular and non-regular languages. It is proved that for probabilistic TM there is no complexity gap between regular and non-regular languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$B9CAE913-F9B5-4728-8D84-45E1C7605DF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$3806286D-7A03-4108-B0D4-C50B49E68EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$A4256472-0ABE-47D2-8994-5D71ED03C6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$968C7C85-83AA-4C62-9E5F-22B48714CBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$EE86530A-C021-4541-8A13-5D1634573317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"285204a08721302d6c82239ec503b2c6e51ce0f3","datavalue":{"value":"62-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$6A72998F-E620-4B40-B550-8E35C0CA7326","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c6a02b43a83b2d40852c3aa860feff0bd8d69a4","datavalue":{"value":"4056998","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104746$93493BD2-86E1-430E-B46F-E39BB5A3859E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e63305dac19ff8dc197cda884cf509dfbf6b7c4c","datavalue":{"value":"Parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$0E124B63-2682-40EE-ADC0-204B476FB3A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"959c05b8564cf93be76a3b4dae24ecf8967c84ff","datavalue":{"value":"geometric problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$7D39DCCE-0B88-456C-8F60-2053C960A86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e87534b6ec6cc09f6ba0a85eae2ffe0a3c0a3e46","datavalue":{"value":"two array processor models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$3BA55C69-8C2B-4219-AABE-D6A463B7CE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19142d21a0cb43adf1e10464d990d4090c454a8a","datavalue":{"value":"mesh-connected computer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$0748DAA5-A6CF-4960-B60C-FE55142275F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcb15d2c6fe2a815c47abfe250dcbae7998ed35d","datavalue":{"value":"two-dimensional systolic array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$EEA9484A-E2EE-46F0-9206-BD372094B57F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$631E4212-57A6-4B7C-B651-D84EBE6E880B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32e6e5c3ebfef789bac653a3f6b64becba826d6e","datavalue":{"value":"non-regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104746$F5AEEBFE-6CCD-4303-8BD9-BAF11F1C88F1","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":"Q1104746$1FD280E4-8D76-4126-B809-EC34D83DDE73","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b93cbcfe92914798c52148f95cc353b5e256c5a","datavalue":{"value":{"entity-type":"item","numeric-id":2552382,"id":"Q2552382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$07DA5D2E-1ECE-48CE-ACA2-6854E104B3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2034f32ee69a3f9f5b46504a02acb33a9c9b33","datavalue":{"value":{"entity-type":"item","numeric-id":5375460,"id":"Q5375460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$28398F89-141F-4730-AA24-0E57BCE90213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1346a1b8f009aadd7187cdea6573007a5e3859ad","datavalue":{"value":{"entity-type":"item","numeric-id":3914895,"id":"Q3914895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$145A7791-F819-454D-9145-005832DD0CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fdc1b1213cadf6ec10af2b6b120336877933090","datavalue":{"value":{"entity-type":"item","numeric-id":3684051,"id":"Q3684051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$58C380AE-3332-4532-924C-CCBBFD20B98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8f18ea1af35e16f8b078e128f38839dcba5c2a1","datavalue":{"value":{"entity-type":"item","numeric-id":4120129,"id":"Q4120129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104746$2DA62A72-F113-446B-97E6-0949A2505300","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54c60a42b0b97f577c00f9a3d78a5e67bf20bbf3","datavalue":{"value":{"entity-type":"item","numeric-id":808271,"id":"Q808271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56324a326694ba52aaaad455058f29d567460879","datavalue":{"value":{"amount":"+0.7296537756919861","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":"Q1104746$22DA6D40-3D44-4BF4-9D8A-04885274A16A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5ceb2f1b329832f304220e982b8248b791b1e97","datavalue":{"value":{"entity-type":"item","numeric-id":3792243,"id":"Q3792243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c7d4b17928be8558cabbaab8c7d5d5de221b8ee","datavalue":{"value":{"amount":"+0.7296427488327026","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":"Q1104746$DEDDF06D-386C-4434-98C3-BD4CF20F2AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e9d8006f0f161903eb2abe83342f6410f9aef48","datavalue":{"value":{"entity-type":"item","numeric-id":3976039,"id":"Q3976039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7b9fcd0bc262e6e99d7c6f227d789c3880a26d","datavalue":{"value":{"amount":"+0.7274093627929688","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":"Q1104746$02A0CC5C-5B02-4D46-A862-A83A45C1928D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e570a0609ba590cdb49ceb14506077ad9acbeaf","datavalue":{"value":{"entity-type":"item","numeric-id":3773378,"id":"Q3773378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faca0eb4302663a57593c10204fc2ad5110ab86f","datavalue":{"value":{"amount":"+0.7266466617584229","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":"Q1104746$C7B1E1C4-7276-418D-A410-1CD5D1F7C039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdd6924b70ba014e6ec7f6df27f06f52dfbd8979","datavalue":{"value":{"entity-type":"item","numeric-id":1062464,"id":"Q1062464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1496167df135a1026757740b0f00e3f1349523b7","datavalue":{"value":{"amount":"+0.7254311442375183","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":"Q1104746$BCB284D4-96A2-4F76-80A2-013C14EC0A9C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Geometric problems on two-dimensional array processors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Geometric_problems_on_two-dimensional_array_processors"}}}}}