{"entities":{"Q1083202":{"pageid":1093954,"ns":120,"title":"Item:Q1083202","lastrevid":48991774,"modified":"2026-01-06T10:28:32Z","type":"item","id":"Q1083202","labels":{"en":{"language":"en","value":"Unbounded fan-in circuits and associative functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976337"}},"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":"Q1083202$74107DCE-F999-4743-8C22-19D1EC64B4B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bfe6b6680270405e5892d1d260f9060374eeb63c","datavalue":{"value":{"text":"Unbounded fan-in circuits and associative functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083202$C8CB35D3-A35C-4344-A82A-8A456BA405F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cc7cc9904b2f1109942847670c854b19793bbfb1","datavalue":{"value":"0604.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$A917BEC5-F1FC-41C0-B3B3-68B6AE4DBCDD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf1ba20d0d997bae31b936fff056d29bef59d71b","datavalue":{"value":"10.1016/0022-0000(85)90015-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$42807790-FF23-4117-A7FE-92DA33CAEC11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37f94e219c650c0af69779700675fb4fbdc2fbc1","datavalue":{"value":{"entity-type":"item","numeric-id":913503,"id":"Q913503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$02959B74-77C8-4B46-BAAD-83E28D85907F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b779bfddc87d776c9165e959ef074321b953112","datavalue":{"value":{"entity-type":"item","numeric-id":494073,"id":"Q494073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$4E2D8F4E-82E5-45C1-861F-9D4311D23627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4efc08bcb427d9602fc487f25b09b09349687cb3","datavalue":{"value":{"entity-type":"item","numeric-id":181990,"id":"Q181990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$1219DF39-2F17-4FD7-8EA7-0B456D766836","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":"Q1083202$0208A1E8-8AF8-4592-B685-3FE2ADB21A6A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1083202$3D206278-84B7-4D19-AF21-9A2B5D0E914F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"47bc17133bbbb7d80edfda87a5f2d10ac09d8bd2","datavalue":{"value":"The computation of finite semigroups using unbounded fan-in circuits is considered. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size \\(O(nf^{-1}(n))\\) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$5060DA47-BA59-4AD7-B368-14D548F660B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$D550FB38-2B15-40E4-8A80-A963B935A68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$1CA2898A-14B6-485E-A80F-6A7AD9BF90B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$792C0F1B-39B6-47F5-B422-A7907DACF967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$7EC0DE4D-B3C7-4640-81A2-10B756945D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$C9D25E93-235D-436B-A7DC-617705784051","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d32e8cf0e317d8f730a8bfa0ac17bc5e7674ba09","datavalue":{"value":"3976337","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$666E69D8-A31C-4C2C-A6CE-8B086CE641FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$6B0A817F-2065-4B25-8274-436DD6B9CC40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$9DFF54B0-F1C4-4CD4-95F7-656B51E27E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa23db05154d55892ed7ba111a7a3b8302eba420","datavalue":{"value":"computation of finite semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$4356B30E-9A2A-44F8-BC3D-5DFDD1A9890E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1360a367b0eb227addd1d243fc98100cfdf7e94","datavalue":{"value":"semigroup product","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$01375BD6-1227-40DF-AF03-61D2788D793E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fac50ec2c362ec49670e8e90e0f9b972fb59ccb9","datavalue":{"value":"primitive recursive function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083202$5DDD5109-96E9-400A-9E32-381FC16AEFC3","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":"Q1083202$69D2FADD-03DB-4536-80EB-450B7619D1E2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f82edc3048aa303eb8cbb0be89e1f583aca99e7","datavalue":{"value":"https://doi.org/10.1016/0022-0000(85)90015-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1083202$BB4E0B09-29D6-414F-AFE5-85A4C3C2F71E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08c78e6a40c1cff0300ac608b287143024a83160","datavalue":{"value":"W2031713274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083202$7FF431FC-46EA-44E8-A928-9304EADDDE41","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"03665630069e3257497d45ce7d1b04ab8e8ea70d","datavalue":{"value":{"entity-type":"item","numeric-id":3321475,"id":"Q3321475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$501D2229-FD59-416A-B43A-CFCE8AB041BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$FBF7754E-3557-46B8-9A73-952538FFCBE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$E0708CB8-CF15-4EE3-8987-8904F845307E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dd225cb7a1f1b5d01838e5961bac1df864370d","datavalue":{"value":{"entity-type":"item","numeric-id":5641083,"id":"Q5641083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$43697DC2-D472-4BD5-B2F8-97223B4B8691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7e469a8fa14b237d73aa7dbd98d094baae506d","datavalue":{"value":{"entity-type":"item","numeric-id":3719831,"id":"Q3719831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$F4BA327A-3BBD-4C2A-AE90-9BF269DFB682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$86AD2675-62C7-4809-B34E-F4DA6D70D191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dbbc886fb1fa28cd3956328dc50daec2972480e","datavalue":{"value":{"entity-type":"item","numeric-id":4074359,"id":"Q4074359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$83E06E30-5BFF-4D5B-89FF-D5E37C9A977E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ca3e015d5a9a71c43e5d072fe10aa2d6bf2145","datavalue":{"value":{"entity-type":"item","numeric-id":4747506,"id":"Q4747506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$D478E650-F302-4D2A-877C-014D494FCB39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d53db4e61bfa2d597f0a53da172502701ac0503","datavalue":{"value":{"entity-type":"item","numeric-id":5402545,"id":"Q5402545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083202$8382F146-89E5-4A67-A41B-62BBB38F4DEE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45ec79da457ecd5b747b78eae31b317b50fa5875","datavalue":{"value":{"entity-type":"item","numeric-id":3471696,"id":"Q3471696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ece010aec437b41dcf23d79d9dee227fa7433b4c","datavalue":{"value":{"amount":"+0.788361132144928","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":"Q1083202$E9639782-17D3-4C32-B5FA-DE4ABF0186B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fe297fe667c032d63a4c0c51e72baa2de00bbca","datavalue":{"value":{"entity-type":"item","numeric-id":4016932,"id":"Q4016932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0493ac9b3db432b216af3491055a29add2c6f74e","datavalue":{"value":{"amount":"+0.7427160739898682","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":"Q1083202$61A45C0D-226E-4BB0-B8F8-626ACE044DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c5b30f5bfa198639f0b3b275ac0c207e416af94","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28bef390ab44d642c199f6c6236a5ca7202bbc85","datavalue":{"value":{"amount":"+0.7395066022872925","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":"Q1083202$DD6F8517-0A41-41EA-BB86-F3B689084F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69671066a33dca3253947a26b424c4d949f8baa1","datavalue":{"value":{"entity-type":"item","numeric-id":3745780,"id":"Q3745780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3835ed1159641ede3c202612d76a44cfee93c12","datavalue":{"value":{"amount":"+0.734801709651947","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":"Q1083202$646D1DE4-6CF4-457B-B0F3-1FA2281C3761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9df9e8ca948d5a674a0ff1f841eb890e745f2f1","datavalue":{"value":{"entity-type":"item","numeric-id":3321475,"id":"Q3321475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f35b432e39d61ef90e910ee67bfaa96716027b","datavalue":{"value":{"amount":"+0.7343389391899109","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":"Q1083202$D9F271D0-45B2-4549-9EAA-121C54A1A73C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083202","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083202"}}}}}