{"entities":{"Q2805414":{"pageid":2816152,"ns":120,"title":"Item:Q2805414","lastrevid":52527728,"modified":"2026-01-22T21:23:41Z","type":"item","id":"Q2805414","labels":{"en":{"language":"en","value":"Bases for \\(\\mathrm{AC}^{0}\\) and other complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6579327"}},"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":"Q2805414$FF881A06-E235-4EAC-B11B-8FC85ECD69DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bcfef31353b273463be80bc8fa748886f2a29ed6","datavalue":{"value":"1348.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805414$895ED288-30C3-4FDA-B349-23F1686415EE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9f2d91b744a86ccb242259b26f20c05137d3ae6","datavalue":{"value":"10.3233/FI-2015-1165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805414$D6174FFC-B65E-4241-A2CD-A52E2F011813","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1529db038bde6a8aed76ac5e8432917aee1a9200","datavalue":{"value":{"entity-type":"item","numeric-id":2803574,"id":"Q2803574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805414$DA1955EE-056C-42C4-B490-E020555C93C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39aa9fdf5ab62c801ce885c7d8f139e97b3cfa9f","datavalue":{"value":{"time":"+2016-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2805414$C339693E-CBE1-4DC0-ACAA-03A652D45B85","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805414$FAB8FC69-BB45-4E2A-9A5A-0F48856B6C4E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"098e7058a093a35f92a68d9e37dd2b3f4297d8c8","datavalue":{"value":"6579327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805414$063A6233-49B1-48C9-B95D-B56715E67B68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"822c378a6b1eddebf6af6dc68c2fa88735e06352","datavalue":{"value":"concatenation recursion on notation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805414$52AF53A9-E929-4816-BEF3-DD36A82972B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dab62c83ccc45b9b1fe81954f29cfa9601f555f7","datavalue":{"value":"substitution closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805414$B39EC162-33B8-4C51-9C5F-5DBF45BBE115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb6918c0338a517bb805652f66773bc8ff8db971","datavalue":{"value":"substitution basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805414$2EFB7AD9-46CD-43BD-A7D3-1D3463EE17C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8db1726c03c7059c08d69b8aca64a6baa1151a9","datavalue":{"value":"complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805414$90E1954E-9CB9-4F70-9AA7-D26D7AB9D7F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26a317fd60e70e233c239ff7a7887169a825aff3","datavalue":{"value":{"entity-type":"item","numeric-id":342701,"id":"Q342701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805414$9985BC93-973A-46C7-BD85-0645D66F5DE0","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":"Q2805414$A5E821A1-B335-4C8C-ACBB-C43402263AF1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9ff06d89261ab8cab8e51751a9d4276726b4d5c9","datavalue":{"value":"https://doi.org/10.3233/fi-2015-1165","type":"string"},"datatype":"url"},"type":"statement","id":"Q2805414$B346C6F5-49F7-428C-8A52-5842F8DD61B3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a5ef5c32a8a543d8a9e84a37d55dce8b6bfe2480","datavalue":{"value":"W1617132762","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2805414$949493C7-B97A-4D23-9DBC-207D0DACB5FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"875ac78432489875fd763eef3815ed1f4e743c0a","datavalue":{"value":{"text":"Bases for \\(\\mathrm{AC}^{0}\\) and other complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2805414$308C76CE-6E43-4EBE-92EA-28BCA4694887","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16a446cb24e6da516cb709641008d72f53f65d6d","datavalue":{"value":"A finite function set \\(F\\) is a substitution basis for a function class \\(G\\) if \\(G\\) can be defined using only the functions in \\(F\\), the projection functions and the substitution operator. In this case \\(G\\) is called the substitution closure of \\(F\\). Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Previously [Fundam. Inform. 120, No. 1, 29--58 (2012; Zbl 1260.03076)], the author showed that a function class closed with respect to substitution and concatenation recursion on notation admits a substitution basis, provided it contains integer division. In the paper under review, the author improves the techniques and results of this paper. For instance, the existence of a basis for a function class is stated without assuming that the division operation is in the class.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2805414$E7EBA1C0-2B91-45D5-A1D8-4DC394C4EF08","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2805414$24617E38-DBA9-4BCB-87FD-BD78CE9F9D8A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"233e763fcea288f6f3ef5eb9e2abb6ba587c3893","datavalue":{"value":{"entity-type":"item","numeric-id":5112387,"id":"Q5112387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72b05e7efb98d3a89fd82f96e28a9893d40b2386","datavalue":{"value":{"amount":"+0.9037626385688782","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":"Q2805414$1062822E-9C2A-4D69-89A1-85417F2BE8ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"797026dd054ff82cc71113fa92ccc67507367ba5","datavalue":{"value":{"entity-type":"item","numeric-id":5402505,"id":"Q5402505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2b7f6687c5ffb3a70da33b0f2063d8e0781f953","datavalue":{"value":{"amount":"+0.8582615256309509","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":"Q2805414$6B0EEA6B-0015-45CC-82B9-318DCDD3961F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9a64a8ce87469f05dd9c8dfef4c10e9c4a629d","datavalue":{"value":{"entity-type":"item","numeric-id":3168519,"id":"Q3168519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbf72bf36e6390ce34b5decd5182b8a87376a330","datavalue":{"value":{"amount":"+0.8565427660942078","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":"Q2805414$DD745D9A-FC1C-40B2-A794-12FC0BBD722E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f16d9b5507c1ace1fc05034dd368f552a6668634","datavalue":{"value":{"entity-type":"item","numeric-id":4858828,"id":"Q4858828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52d77f47ca7d41a47bd7eece51bf7e32dd95d2d7","datavalue":{"value":{"amount":"+0.7638135552406311","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":"Q2805414$0E2CE38F-35FA-43C2-B72C-BADF9C7C08E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03999060b47a8c7f99ee59e17eed3ee331fae4b3","datavalue":{"value":{"entity-type":"item","numeric-id":4522865,"id":"Q4522865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc6f4ab2f14126d5b8e0be8de41de1e4090e3846","datavalue":{"value":{"amount":"+0.7578619718551636","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":"Q2805414$886E557A-97E5-4234-8CC3-A3A90A22299F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2805414","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2805414"}}}}}