{"entities":{"Q866541":{"pageid":868389,"ns":120,"title":"Item:Q866541","lastrevid":50030620,"modified":"2026-01-12T17:46:32Z","type":"item","id":"Q866541","labels":{"en":{"language":"en","value":"Delay optimization of linear depth Boolean circuits with prescribed input arrival times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5126386"}},"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":"Q866541$64BCD512-C15A-444C-9A58-B892CF4526F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48ebccd85d88c9139a0764e8e41981f52597790b","datavalue":{"value":{"text":"Delay optimization of linear depth Boolean circuits with prescribed input arrival times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q866541$A486DF68-6B26-41C8-862E-D713FD70FEBF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca8521b17002c055fb61ad992e30e05aeee727a6","datavalue":{"value":"1130.94338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866541$0817D6AD-E2C0-417B-A0FC-FC1A609D7BCF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a76e14dae6cbb3abcd2d6da25c84b7ddc989b2f","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$B17F5666-F696-4E72-8914-07918ED586F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a15b8489bc23e9978bfec23bf3c3944da2339ce","datavalue":{"value":{"entity-type":"item","numeric-id":732239,"id":"Q732239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$B4B57CE7-7665-4108-A7B8-3EE7FC699C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c06005b67c3d62f2dcbf2b76379e2014c091e249","datavalue":{"value":{"entity-type":"item","numeric-id":866540,"id":"Q866540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$9DDFFA57-D7C6-438A-A0F8-453D6E4F5BE6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$3D86D228-8FB8-43A5-97A6-627A2CFBDEC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a94159f4ab38d8d1a06ee095402a858d13e226d9","datavalue":{"value":{"time":"+2007-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q866541$479D4863-06F1-464F-A5AA-C74B608EE200","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d922ab6d6d5a83ef1554c42067347d8feaf9134b","datavalue":{"value":"We consider boolean circuits \\(C\\) over the basis \\(\\Omega=\\{\\lor,\\land\\}\\) with inputs \\(x_1, x_2,\\ldots, x_n\\) for which arrival times \\(t_1,t_2,\\ldots,t_n\\in\\mathbb{N}_0\\) are given. For \\(1\\leq i\\leq n\\) we define the delay of \\(x_i\\) in \\(C\\) as the sum of \\(t_i\\) and the number of gates on a longest directed path in \\(C\\) starting at \\(x_i\\). The delay of \\(C\\) is defined as the maximum delay of an input.  Given a function of the form   \\[ f(x_1,x_2,\\ldots, x_n)=g_{n-1}(g_{n-2}(\\ldots g_3(g_2(g_1(x_1,x_2),x_3),x_4),\\ldots ),x_{n-1}),x_n) \\]   where \\(g_j\\in \\Omega\\) for \\(1\\leq j\\leq n-1\\) and arrival times for \\(x_1,x_2,\\ldots x_n\\), we describe a cubic-time algorithm that determines a circuit for \\(f\\) over \\(\\Omega\\) that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$F67EFBB1-1D47-432F-AFD4-CB269CB9F075","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866541$231698F1-2C11-4F5D-82A9-BAA3A2C2BABD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4deb176377d40487b9c65e8707e968895e475879","datavalue":{"value":"5126386","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866541$FE32CD12-5C42-4167-8F75-C51FB478CF17","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcaef8b48097d50a08be2219f6311c65284708bf","datavalue":{"value":"circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$DF3DAE62-1127-484A-9E3E-A2B8A464EE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b179ff35f70d8232f04f8b97e879f244708677d7","datavalue":{"value":"straight-line program","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$A16A368C-A5F7-43FC-AB8A-F27F9E588E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd0a5d0d4cf762e7c7ba742f2943056dfb033b4f","datavalue":{"value":"depth","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$A28E006A-8081-4D47-A55A-15CC9320A93C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b76a5f96cd2aadef4a656a5e792c750f2bab46b","datavalue":{"value":"delay","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$ADF6A367-9DBC-433C-9504-0811BE97F1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33c83d5142aaa8d798578ed711216fa831c5585","datavalue":{"value":"computer arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$30311932-991C-4836-8F44-D984CDCE8814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38dd5c31d373d76e6308be0f17a0875fd182b166","datavalue":{"value":"VLSI design","type":"string"},"datatype":"string"},"type":"statement","id":"Q866541$F49BEFA8-8009-4482-BF9B-F2D6BB85559A","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":"Q866541$8993F2DA-7163-4A3B-B51A-C463FB0BF862","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67dd1fda537d1690964047addba061f32b146166","datavalue":{"value":"https://doi.org/10.1016/j.jda.2005.06.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q866541$4AC56EF9-4048-4CF8-9FA1-45D3309335FD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3cf45627f2ea7781c199c52fc45e9d95c80446f","datavalue":{"value":"W2025635553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866541$28802FA6-B6AE-420F-8780-57C98A562693","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7f5d801cceed522c3fc9ead918aaa111dc0545","datavalue":{"value":{"entity-type":"item","numeric-id":5597996,"id":"Q5597996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$3B1A1CAE-8764-42A9-BE6D-9E6E493AB0E6","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":"Q866541$699784C1-3071-482B-9667-6D4F0BCA52EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98329fbc3672cc52be017f9099bd0f4c56178210","datavalue":{"value":{"entity-type":"item","numeric-id":2370422,"id":"Q2370422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$CDE4950D-93A5-4449-9A92-A67770C7E150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d72f92e4a9629fedaa104a68de7f1e3678e9384","datavalue":{"value":{"entity-type":"item","numeric-id":4344138,"id":"Q4344138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$B5D8D364-0F9B-4EB5-A48A-0DE18523F2A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e35ce7c32098059988ea1d625f6b506427631d3e","datavalue":{"value":{"entity-type":"item","numeric-id":3999183,"id":"Q3999183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$F733D3B9-7161-4998-A5B5-04022C1FB832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$08B1714F-49EE-4579-8C18-5D650C0A4BF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b914bf5895a709c0256d74af684ac278025d1d1","datavalue":{"value":{"entity-type":"item","numeric-id":5590440,"id":"Q5590440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866541$610A6CEA-7D5C-4CC7-AE2C-161FFB3B0A0E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f4c5d980954d412b848a2e301bfcd546e375904","datavalue":{"value":"10.1016/J.JDA.2005.06.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866541$AC6BCB35-D3F3-4E2E-9C42-17D854B95053","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eb64b6099c5512fa0d8592071b3cd17b43f302e","datavalue":{"value":{"entity-type":"item","numeric-id":2370422,"id":"Q2370422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5958b4287baeff5092cee2f5863fa228b76aaf64","datavalue":{"value":{"amount":"+0.8482095003128052","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":"Q866541$E2310C38-BF1A-44ED-B12A-026F6791D973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bbfc0e5416a8726445d8264712d90d6cc5f0b1e","datavalue":{"value":{"entity-type":"item","numeric-id":4973041,"id":"Q4973041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccd86bd1700e8b22159871f65463dfcd1928cd39","datavalue":{"value":{"amount":"+0.7838261127471924","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":"Q866541$AF5C747A-9508-4820-80E1-140660AD3EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a69a9a366af038a054c49fa6bcf34c8f38ff4d1","datavalue":{"value":{"entity-type":"item","numeric-id":3184552,"id":"Q3184552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dcc5d0db105447d0ef5fe82992084f0a63d7ae1","datavalue":{"value":{"amount":"+0.7618629932403564","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":"Q866541$5279DE52-2151-4F7C-B44C-1F900A756CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8d4f297f7b47275ab3f6c407af770530b3c96cf","datavalue":{"value":{"entity-type":"item","numeric-id":5622111,"id":"Q5622111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c99b4917d35e6806d27d4ce3272fec120ef1084d","datavalue":{"value":{"amount":"+0.7406778931617737","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":"Q866541$A5F7DB47-237B-4B44-B5C3-D975478095DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d2dbcfb5a8d767a342e1b2b23510ed23d90768","datavalue":{"value":{"entity-type":"item","numeric-id":4889733,"id":"Q4889733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"698e745dc14b3bbb775d79fa440d34c799b58dda","datavalue":{"value":{"amount":"+0.7396149635314941","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":"Q866541$BFB67DCA-8F1B-46E3-98B5-406E9CD790EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:866541","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:866541"}}}}}