{"entities":{"Q1091139":{"pageid":1101891,"ns":120,"title":"Item:Q1091139","lastrevid":69620181,"modified":"2026-04-13T08:15:05Z","type":"item","id":"Q1091139","labels":{"en":{"language":"en","value":"Area-time lower-bound techniques with applications to sorting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4009820"}},"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":"Q1091139$41EEECC6-1911-4E89-9F90-1045A34D79BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9341da9d2b64b05dcdf1522f717e228ff67308f0","datavalue":{"value":{"text":"Area-time lower-bound techniques with applications to sorting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091139$EE41888E-31AE-4180-9010-FE001D80F84A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e7f5479ca3cd2d0c86e64b78107151709d893ed","datavalue":{"value":"0622.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$F1EFD209-79AC-4FD8-ACF2-8B15884C2CBE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e10dfa4bf4a5700b4e89970ea0dfc2be81abdd5","datavalue":{"value":"10.1007/BF01840437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$12A72F5C-90C1-4F01-9CAC-B9314AB0556A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$82B25184-30E7-4F3A-9395-7EA6EE63E6D1","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":"Q1091139$89B48F8F-AB9E-44A9-BE31-813D43E5EF7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4a8a57cdd8b8684c860e2fd6decf53d532990e6d","datavalue":{"value":"This paper is a contribution to the problem of area-time complexity of VLSI computations. The information exchanged across the boundary of the cell of a square-tessellation of the layout is studied. Two cases are distinguished: If the information exchange is due to the functional dependence between the input and output variables on opposite sides of the cell boundary, lower bounds are obtained for the \\(AT^ 2\\) measure. When information exchange is due to the storage saturation of the tessellation cells, a new type of lower bound is obtained on the AT measure. Furthermore, a mechanism is described which is called computational friction and it is shown that the applicability of this mechanism induces lower bounds on the AT/log A measure. The lower bound techniques introduced are illustrated by applying them to the sorting problem of n keys each of k bits. It is shown that \\(AT^ 2\\), AT, and AT/log A bounds can be derived which are interesting by themselves as each of them dominates the other two in a suitable range of key lengths and computation times.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$EA228155-F885-44CB-8F10-AAE4506A7DEA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$C63889B2-363D-4F5B-B982-7F1A593E5925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$6C633E36-B851-4418-9EB1-9953A56431DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$9BE1E129-3392-426E-AC4B-80B9B667963E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94a73724451304d49da9a4c860e5cd04cbff881a","datavalue":{"value":"4009820","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091139$9C37F288-7162-4A6F-B83B-EFE08B168FEF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bac1139c3d876fb02667bc7a1fe98aa70c67782","datavalue":{"value":"area-time complexity of VLSI computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$0AAF9862-330E-44DF-B21B-4A21A0A82B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"992b8753fcfd7efda5e48ec96963b4f227cf3493","datavalue":{"value":"square-tessellation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$D0B9F484-6804-464D-A0BC-FAA8CD607108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a67d980e7e5a8c917ee75d48342cbd24ff9016fd","datavalue":{"value":"information exchange","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$590CCAAA-5381-4EC6-B890-7B40546F6565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$523164CD-251A-4EBD-95C5-F77B626A5EAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce78d084397d78fc53ef447aaad522667d6ef5c8","datavalue":{"value":"computational friction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$D5526A1D-31E6-42D8-9C28-D095D1A3A9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091139$EF405918-AE62-4C65-9FB4-288A7AE3F0AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d7ee36f4e616268c219fdfd4e2e4df98fb3f505","datavalue":{"value":{"entity-type":"item","numeric-id":386895,"id":"Q386895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$CEF1F86D-3C82-4420-9CE1-F70892AE0D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09a0d0c7c3a8cc7117eaef5e49aac31cce266126","datavalue":{"value":{"entity-type":"item","numeric-id":414867,"id":"Q414867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$4C7D3432-A833-4E25-ACF2-FDD6EEAF6E4D","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":"Q1091139$AC60C0ED-995F-4686-80BE-A022C0495944","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e8879377aad5417d67a1e6c340dc37617787edc","datavalue":{"value":{"entity-type":"item","numeric-id":1146001,"id":"Q1146001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$198A458E-DFE7-413B-8FDA-34C9EE51E437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b727fa567c94cdb3f1e3b3a5e33b6558f961596b","datavalue":{"value":{"entity-type":"item","numeric-id":3768399,"id":"Q3768399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$557349A5-79DF-47B8-B507-06A97F191602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc5a0522cb1d7b72c8a8c592e1f5e589f1cfdd8f","datavalue":{"value":{"entity-type":"item","numeric-id":3028340,"id":"Q3028340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$7783E6E3-27CA-4C57-AFF3-0F7B8ACD9F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95b43a6c4c4e31e641d94a071098874a458bb3af","datavalue":{"value":{"entity-type":"item","numeric-id":1151751,"id":"Q1151751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$5FBE01F8-350B-41C1-8012-4C98539507B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e200b91b38dcda7a6afd8fe20171560b27754991","datavalue":{"value":{"entity-type":"item","numeric-id":3912011,"id":"Q3912011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$4A3AE359-4C87-476D-9889-88EE4C9A6687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"268f9c1b9d2d2a24cd8f10f9d22d3a28e4cb08b8","datavalue":{"value":{"entity-type":"item","numeric-id":3711746,"id":"Q3711746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$25D0817A-BE32-4943-AF58-AEDA9ABD2385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$7F3CD64C-11D7-4F69-9CD3-48B981C8E102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"464b53a78f27b38e838082f899a6c8c9b52616ed","datavalue":{"value":{"entity-type":"item","numeric-id":3323284,"id":"Q3323284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$1C118710-9855-4EF2-A486-8AC4E74C241F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e67a603060068ee8ff7980bfb5820423d7b0c234","datavalue":{"value":{"entity-type":"item","numeric-id":3687730,"id":"Q3687730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$86624D6D-FACC-4DDA-81D7-8E94595222EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d3cc70248a1e64e37a5a15546ca2a27b6355fa2","datavalue":{"value":{"entity-type":"item","numeric-id":3816988,"id":"Q3816988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$8518079F-8DE7-443D-8576-54B1BCD6582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b55defd29cd77c3de9c0961af1676f1dc916da47","datavalue":{"value":{"entity-type":"item","numeric-id":3036700,"id":"Q3036700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091139$5C3DD0B1-3442-41E2-8042-A888065F31BE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2430103b127bb9115feca3562a3a111dd925cd3f","datavalue":{"value":{"entity-type":"item","numeric-id":3711746,"id":"Q3711746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a62516862b22d104bfb4d39e3d0e69c1d73bd1d","datavalue":{"value":{"amount":"+0.8655704259872437","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":"Q1091139$ACEDBE6B-C3B8-4979-BE86-B04434A07506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0961558cfa17217d535f41be44ca624211d3bda8","datavalue":{"value":{"entity-type":"item","numeric-id":3691061,"id":"Q3691061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c4e0cb74856f6eb7dcdae6e6d469073c268b4be","datavalue":{"value":{"amount":"+0.8543646335601807","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":"Q1091139$84EB96C6-8E41-4E03-9E5D-B3832E25E2A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf78bcac8b5326ba1a272170799e7f978a9b61c7","datavalue":{"value":{"entity-type":"item","numeric-id":3687730,"id":"Q3687730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08921f4caa053abf54152ec32bc64a47381676ad","datavalue":{"value":{"amount":"+0.8443052768707275","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":"Q1091139$18D7BB32-73CB-4B1F-A3BE-D34A1CD0D533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0dd7328e621a2b2ef55992c4ecbac9dab04d14a","datavalue":{"value":{"entity-type":"item","numeric-id":3219772,"id":"Q3219772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2675a381ea0b4bb43fcdf9d25cc114b8e1222187","datavalue":{"value":{"amount":"+0.8264549374580383","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":"Q1091139$0342A397-C1C6-448A-9054-A05F82E944D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44261814731d4937fcdaea35af644eb8246ff742","datavalue":{"value":{"entity-type":"item","numeric-id":5186733,"id":"Q5186733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9cefaa17de34ec9e9ee5059283dc6418e7624dc","datavalue":{"value":{"amount":"+0.8179531693458557","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":"Q1091139$27039718-27D4-4FA2-83FF-F977E9A6A5DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Area-time lower-bound techniques with applications to sorting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Area-time_lower-bound_techniques_with_applications_to_sorting"}}}}}