{"entities":{"Q1759151":{"pageid":1769893,"ns":120,"title":"Item:Q1759151","lastrevid":72468123,"modified":"2026-04-14T05:06:48Z","type":"item","id":"Q1759151","labels":{"en":{"language":"en","value":"On the synthesis and complexity of formulae with bounded depth of alternation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6108668"}},"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":"Q1759151$BBBAC1EB-82C4-4A9D-B37D-562D96F0AEB2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91e95aeebc86b8d824eee28471cad0695c08be40","datavalue":{"value":{"text":"On the synthesis and complexity of formulae with bounded depth of alternation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759151$C3F190F5-C292-49BD-84A0-5812DECDBE0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39e9b9af9954d5406ff74e161bfd73e26e77c6c1","datavalue":{"value":"1258.94054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759151$C4516B1E-5455-4ED7-87CA-9E6B6DBF30FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36d923c805942c99b8137e83084c59ae3b1d4187","datavalue":{"value":"10.3103/S0278641912020021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759151$41879351-E3B5-4B7A-AC7F-9E9475E686D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dcf8b29f998e6586890411a08c34f70ea4883f1","datavalue":{"value":{"entity-type":"item","numeric-id":1717924,"id":"Q1717924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759151$6DB06E1D-A0A8-4A90-81AF-AFE292CEB9B0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"aa4e0e353121dae82cdaefca14a62dc9d4bb34af","datavalue":{"value":{"entity-type":"item","numeric-id":163582,"id":"Q163582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759151$7CB527EF-69D7-482D-87B9-BAB6D9DA0EC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5cb1220cb4e1c4c12c8a88a3866d2c74b4982dfc","datavalue":{"value":{"time":"+2012-11-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759151$3AEBAA7E-B58A-4ECE-B22D-3B1508F35AC3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"82f7215e2d41353abe3422fde1222658ff4cf167","datavalue":{"value":"In this paper networks and formulae in a standard basis of the functional elements \\textit{and}, \\textit{or} and \\textit{negation} with a weight of 1 that implement Boolean functions are considered. The alternation depth of the formula considered as a particular case of a circuit of functional elements is equal to \\(a\\) if the maximum number of variations of the gates' types on sequences, each being a path and not containing negations connected to the inputs, is \\(a-1\\). For any \\(a\\) (\\(a\\geq 2\\)), the complexity \\(L^{(a)}(f)\\) of the function \\(f\\) is the minimum complexity of the formulae that compute it and whose alternation depth is not greater than \\(a\\) and the Shannon complexity \\(L^{(a)}(n)\\) is the maximum complexity \\(L^{a}(f)\\), where the maximum is taken over all functions \\(f\\) of \\(n\\) Boolean variables. Lupanov proved that \\(L^{(a)}(n)\\) is asymptotically equal to \\(2^{n}/\\log n\\) for any \\(a\\geq 3\\). The main result of this paper is that, for any natural number \\(a\\) (\\(a\\geq 3\\)), the following asymptotic estimation is true: \\(L^{(a)}(n)=\\frac{2^{n}}{\\log n}(1+(\\log ^{[a-1]}n \\pm O(1))/\\log n)\\), where all logarithms are binary and \\(\\log ^{[a]}n\\) is the \\(a\\) times iterated logarithm of \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$A11B9C26-56AA-45D4-B511-2F97CE8089D9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759151$23EE38DD-36B9-4D9D-9906-242F46CADA0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759151$DE043E29-B378-4B2D-A6B6-F1BFDE265B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759151$3004FE4E-4454-4F87-B829-A56DCAF0A676","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8faea1dd6f932e14c1f6c520a642be33387a060a","datavalue":{"value":"6108668","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759151$E4A78C59-5B10-4E7E-A50F-5B74AF5A434E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$EEBB6415-B437-4825-9CEB-009D178A7CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c28c97778fbb68f4b3d21d002e4e8a64c7d17bf","datavalue":{"value":"Boolean formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$D0CB54E3-5FA5-4594-BA9B-CF4E80D27796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5674049a21699c95339876a18dcbec49efa34a47","datavalue":{"value":"standard basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$BCDE2CF9-E37B-46BD-90B8-F85650E73146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$096385B5-874F-4E3A-935F-58110FCBC6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb9e18c62f2f4a2437afa221fb38ed7474bbd807","datavalue":{"value":"Shannon function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$99BF5011-A747-49F7-842C-6D8BDDFC7A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20f69780dd0403b2f15687345c8e40eae9af343e","datavalue":{"value":"high-accuracy asymptotic bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$90C63C3E-127F-482E-AA13-5C119CE3C2B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdfcdf00c2b018a9c79f427df1b2783729abb256","datavalue":{"value":"formula complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759151$4F108118-8A49-406B-BD60-80593586207E","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":"Q1759151$7C0D1B9C-C9BD-44CC-8C2B-551AAC578BAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9996649bb5fe0450d43e84ecb1265ae9933e5203","datavalue":{"value":{"entity-type":"item","numeric-id":3615217,"id":"Q3615217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759151$F0E3F066-6C41-4453-8AB4-17FE6D288ED4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fab7e75b2a9776cd1828fbce1cd7d8858bed1b72","datavalue":{"value":{"entity-type":"item","numeric-id":2332856,"id":"Q2332856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5833c3d525481d131525007c841c04d532f77d1","datavalue":{"value":{"amount":"+0.8346171379089355","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":"Q1759151$C79CC3A7-AC84-4099-937E-1693BC6373EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a13c0faba558e45816ebdb83cd42c2d5ce0fb91","datavalue":{"value":{"entity-type":"item","numeric-id":2018028,"id":"Q2018028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3c1a09c7bb6cfe0b5e791a18c00e1fcdb642c05","datavalue":{"value":{"amount":"+0.8311814665794373","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":"Q1759151$E20AA9D8-B06E-4383-863B-4A919A9E6DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f48d606164ce66d4dcea4f83d393786ca6672e9","datavalue":{"value":{"entity-type":"item","numeric-id":3312197,"id":"Q3312197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"109425a6e4cd3514de505c2bb83f538c54f54d18","datavalue":{"value":{"amount":"+0.8267806172370911","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":"Q1759151$092F01AB-94F5-4E49-A3B1-9AF1B0A8195A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"338c11a728d0487bcf6e42fce5e2d8da0de520d6","datavalue":{"value":{"entity-type":"item","numeric-id":3541513,"id":"Q3541513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37080c6313674da57d5148621c9ce1d6e799359c","datavalue":{"value":{"amount":"+0.8028571605682373","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":"Q1759151$7B3EEB71-A17A-48FE-8F44-3E812CD5B712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8333ff0e36c58e5b686eaeebf2bdafbc72aa1b32","datavalue":{"value":{"entity-type":"item","numeric-id":3815357,"id":"Q3815357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7cd560653487c494ca179fc0c99d30da6cd357c","datavalue":{"value":{"amount":"+0.7930557727813721","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":"Q1759151$F20981AE-871D-4D64-A20E-94C05D0D4153","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the synthesis and complexity of formulae with bounded depth of alternation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_synthesis_and_complexity_of_formulae_with_bounded_depth_of_alternation"}}}}}