{"entities":{"Q1764156":{"pageid":1774898,"ns":120,"title":"Item:Q1764156","lastrevid":73857189,"modified":"2026-04-14T17:31:01Z","type":"item","id":"Q1764156","labels":{"en":{"language":"en","value":"Recursion schemata for slowly growing depth circuit classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2138077"}},"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":"Q1764156$4FE3917D-1F43-47AD-82C6-8CB9E2DB9114","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"67c0867889b10d8807179b17a952108effa899e9","datavalue":{"value":{"text":"Recursion schemata for slowly growing depth circuit classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1764156$7DE7A882-2E0C-4220-AB9B-C597CF6950D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83d9148c770e274003d772474394dc301c5f4352","datavalue":{"value":"1096.03047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$056BA1CA-261C-4181-80D3-811B308484FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb198915f0eecf0de0ba2bdc999cd6ec059e4289","datavalue":{"value":{"entity-type":"item","numeric-id":884959,"id":"Q884959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764156$BAE52510-0647-4827-BB8E-E4B581B16954","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764156$52EE2052-B327-4565-AED0-56B6C7D1C0BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f8b72aeee9429c75f6d2c214b1fe1fedeb47fc2","datavalue":{"value":{"time":"+2005-02-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1764156$F84E577A-3A73-42ED-B7DD-9DCAF85F796E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94b92c3c87e622a20af7781d30785484b93c6726","datavalue":{"value":"The author investigates iterated log depth circuit classes. The article begins with an overview of the results obtained in this as well as in closely related fields up to \\textit{A. Grzegorczyk} [``Some classes of recursive functions'', Rozprawy Mat. 4 (1953; Zbl 0052.24902)]. The author defines a class of basic functions, \\(\\text{BASE}_{i}\\), containing the 0-ary constant 0, projection functions, two successors \\(x\\rightarrow 2x\\) and \\(x\\rightarrow 2x+1\\), as well as bit operating functions \\(| x| =\\left\\lceil \\log _{2}(x+1)\\right\\rceil\\), \\(\\text{Bit}(x,i)=\\left\\lfloor x/2^{i}\\right\\rfloor \\text{mod}\\, 2\\), \\(x\\#y=2^{| x| \\cdot | y| }\\), \\(\\text{MSP}(x,y)=\\left\\lfloor x/2^{| y| }\\right\\rfloor\\). For \\(i\\geq 1\\), the class \\(\\text{LD}^{i}\\) is defined as the class of functions which are computable by \\(n^{O(1)}\\) size, \\((\\log ^{(i)}n)^{O(1)}\\) depth circuits over the base \\(\\{(\\wedge _{n})_{n\\in \\omega },(\\vee_{n})_{n\\in \\omega },\\lnot \\}\\). For \\(i\\geq 1\\), the class \\(\\text{ND}^{i}\\) is defined as the class of functions which are computable by \\(n^{O(1)}\\) size, \\((\\log ^{(i)}n)^{O(1)}\\) depth circuits over the base \\(\\{(\\wedge _{2}),(\\vee _{2}),\\lnot \\}\\). A circuit family is \\(\\text{END}^{i}\\) if there exists a constant \\(c\\) such that the \\(n\\)-th circuit in the family has size \\(n^{O(1)}\\), depth \\((\\log ^{(i)}n)^{O(1)}\\), and at most \\(c\\) levels of arbitrary fan-in AND and OR gates, the remaining levels being built from \\(\\wedge _{2}\\), \\(\\vee _{2}\\) and \\(\\lnot\\) gates. The author proves that for all \\(i\\geq 2\\) the following inclusions take place: \\(\\text{AC}^{0}\\subseteq \\text{LD}^{i}\\subseteq \\text{AC}^{1}\\), as well as the same when replacing \\(\\text{LD}^{i}\\) by \\(\\text{END}^{i}\\). \\textit{P. Clote} defined the notion of Concatenation Recursion on Notation (CRN) [``Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, \\(\\text{AC}^k\\), \\(\\text{NC}^k\\) and \\text{NC}'', in: Feasible mathematics. Prog. Comput. Sci. Appl. Log. 9, 49--69 (1990; Zbl 0765.68034)]. Let \\(i\\)-WBRN be \\textit{A. Cobham}'s [``The intrinsic computational difficulty of functions'', in: Logic Methodology Philos. Sci., Proc. 1964 Internat. Congr. 24--30 (1965; Zbl 0192.08702)] \\(i\\)-Weak Bounded Recursion on Notation. The author proves (Theorem 3.2) that \\(U_{E^*}\\)-uniform \\(\\text{LD}^{i}\\) is the smallest class containing \\(\\text{BASE}_i\\) and closed under composition, CR and \\(i\\)-WBRN operations. Using bases different from \\(\\text{BASE}_{i}\\), the author proves an exact characterization of the class \\(\\text{END}^{i}\\) (Theorem 4.4). The article contains also other results. Some open directions in the field are sketched.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764156$E60D5DCF-CC2A-422A-8714-25FA3CA644D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe64c30036b6931dfc08c246a2592bfd800c1f57","datavalue":{"value":{"entity-type":"item","numeric-id":1612485,"id":"Q1612485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764156$55B656CA-D31F-4A8D-92B1-A421682C7F3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$95E228D7-23FF-4936-83C2-3A5E0F4EBBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$F92CD72D-724B-42A7-8DA4-C86DC37B7C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$FBEF5906-FFA1-4DA0-986D-F7FA061A76B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$84879517-6AA3-4B89-BE27-608FCB347F1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ab67b7d9909651ea6105df7ed5ea89977cc1d80","datavalue":{"value":"2138077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$DD661F3B-5600-4C14-A93D-3860D104FBB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98d515096ceb2318a2b2c35b91d1ca42f0cd8bf1","datavalue":{"value":"bounded recursion schemata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764156$2D31D9EE-9998-4516-B82E-BA5D5D00A41A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b88d2b2ce7293175b5ce95822467df0ca5012","datavalue":{"value":"function algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764156$3647F021-C173-4A85-8DDD-1016745A6E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764156$73D06334-B6F1-44C1-BC82-42A43974BF0F","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":"Q1764156$AB32B091-670E-4A40-8CC9-368754FB13F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30347287f897eeb53e0141961992d4d4a93ae7e8","datavalue":{"value":"https://doi.org/10.1007/s00037-004-0184-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1764156$63A19D37-C2AF-4895-8233-0A8C5D83F4C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac9250938d6a90054c254e393dc2a752237d6977","datavalue":{"value":"W2081380488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$7A36B9C6-9901-4FA4-871C-FA987E83787F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfff8f7fea886fb390414d6f28850c5f9ce92776","datavalue":{"value":"10.1007/S00037-004-0184-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764156$6CDADA79-CD4F-4067-B672-8177271BE44F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dd12124db526dc6342586e19d1b46bd81e0dc13","datavalue":{"value":{"entity-type":"item","numeric-id":4723715,"id":"Q4723715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d9ff0f5dc65c5e8533d01022de8dc18e590c04f","datavalue":{"value":{"amount":"+0.7586003541946411","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":"Q1764156$2F2A2AFA-F8A4-475D-A9E4-97B1457001E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622ddd41bbb83191fa413a1c014f5e446378ad87","datavalue":{"value":{"entity-type":"item","numeric-id":3540170,"id":"Q3540170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a597709e2af3d7047befdc943b1037bb260007ae","datavalue":{"value":{"amount":"+0.755754828453064","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":"Q1764156$6D192EC3-6497-498F-A13C-02842CC7B642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2aca4c9e75088ef2d5332c366b461bf46addc55","datavalue":{"value":{"entity-type":"item","numeric-id":5145309,"id":"Q5145309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7299829fd70c5e45d2a7fad760bfc632bb6f772","datavalue":{"value":{"amount":"+0.7300598621368408","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":"Q1764156$3EFCD5DC-3B67-452C-A524-E3EBE806116E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42925fe12a51eb66f2ff85ca65f56327609f626b","datavalue":{"value":{"entity-type":"item","numeric-id":4035303,"id":"Q4035303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f47bc739e90691b2a98acf189ad6706f4c2426e2","datavalue":{"value":{"amount":"+0.7085884213447571","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":"Q1764156$BF1B5E9C-4B10-4AE2-B2A5-80C3B166D6BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3b34bb9d2a377ee4a9cb6a77b8dd9a28b536708","datavalue":{"value":{"entity-type":"item","numeric-id":2085583,"id":"Q2085583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b570c267ea3fb396fef697cfb2fbd49c45b587d2","datavalue":{"value":{"amount":"+0.7048932909965515","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":"Q1764156$C7F866B3-DEEE-4459-8F00-74C5F3D0F612","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recursion schemata for slowly growing depth circuit classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recursion_schemata_for_slowly_growing_depth_circuit_classes"}}}}}