{"entities":{"Q2806555":{"pageid":2817293,"ns":120,"title":"Item:Q2806555","lastrevid":83611250,"modified":"2026-05-07T09:19:17Z","type":"item","id":"Q2806555","labels":{"en":{"language":"en","value":"On the computational complexity of finite operations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6581979"}},"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":"Q2806555$F8532398-2599-49C2-8D1A-16FC7C9DF100","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"75762caa760765bbc42e8b24c82fe980bbb60f6c","datavalue":{"value":"1347.08005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$D9602A72-51D0-487F-AF99-262C966D4093","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"beb0d439567d0c83cece639dcdb79358236b2e1d","datavalue":{"value":"10.1142/S0129054116500027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$1F3C5E2C-6507-4A74-9933-3806A7DDAF15","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"521db471eac98d2f8f52ebf056a586e720e7b58a","datavalue":{"value":{"entity-type":"item","numeric-id":1047109,"id":"Q1047109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2806555$8401FB5F-D71F-4CCE-8B0B-95056070C202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88577644764f9b9e6eb09a939a06138a2d1f8eba","datavalue":{"value":{"entity-type":"item","numeric-id":2806554,"id":"Q2806554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2806555$7625CED1-26F6-4112-AF59-44ECD3C6530A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"47adaa7123c6f3744cf7fa8eab088d52b4982295","datavalue":{"value":{"entity-type":"item","numeric-id":2703009,"id":"Q2703009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2806555$5E96E909-FEC4-43B2-9E1A-CAEA6AE77B83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"520e6f0241f1a69086f50367d5722006ec0b624b","datavalue":{"value":{"time":"+2016-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2806555$5FDCECD7-CEB7-4F97-9DA0-84802D012FF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"db9646b629f9610547672595cfcafba147500e77","datavalue":{"value":"https://arxiv.org/abs/1501.00265","type":"string"},"datatype":"url"},"type":"statement","id":"Q2806555$EE7D41DE-E089-4A5A-A267-774A3538C7C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"602d7e96b613d2f356db81712453cadad0417631","datavalue":{"value":"08A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$62A9C7D0-E385-4974-87B9-D526CBD10794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf715f882d7ad0c07303aa3e6e3ac3725da52515","datavalue":{"value":"03B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$3EDEE6AA-9C88-48DE-9F70-418ABAE61D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$410E929F-0791-4BF3-8148-5872E8341B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$1430AEF1-9913-4CAB-BEE6-C8880028AA1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb3581767fd89e97bb03245f534da87c64e57b50","datavalue":{"value":"6581979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2806555$ACAE729B-E774-40F2-B76E-DFD912D267CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57322ecd92b5c9defca9337a2977a6821b2e5795","datavalue":{"value":"ordered decision diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q2806555$BCC7C624-C43C-46F3-BEC5-561104111CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef359d59e74cb9142903f0e8e9f4e9a6db893b78","datavalue":{"value":"implementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2806555$DEAC23E9-8BA6-4E93-8878-95CCA89B73E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56327af75156516607a087318010877c781bac39","datavalue":{"value":"subfunction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2806555$213A0AA9-682F-422D-90A8-B6580016D505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17bd1fff6ab874d06f223364008dadcb2c0c7438","datavalue":{"value":"separable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2806555$A39FB878-069F-4267-A764-64E281559FBF","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":"Q2806555$80EE2230-8477-452B-A2D1-61A283AD0BA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6bcbae2cb99ca456494b5be12f10a32e8d8a72ca","datavalue":{"value":{"text":"On the computational complexity of finite operations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2806555$3AA5A4D9-52B7-490A-96F0-FD00B4E53EF0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3bcf1f1285f3965f47ec7033130efda8078523a4","datavalue":{"value":"The question on the complexity of \\(k\\)-valued functions has been studied by various authors as a contribution to the theory of computation. The present paper deals with two ways of a construction of new functions: subfunctions and implementations; decomposition trees correspond to the first one and ordered decision diagrams correspond to the latter.NEWLINENEWLINELet \\(G\\) be a transformation group acting on the algebra \\(P^n_k\\). Then, the authors introduce a \\(G\\)-equivalence of functions. For various transformation groups \\(G\\), properties of the equivalence are investigated: the number of the equivalence classes, the cardinality of the classes, a method of a classification of a function, first for a general case.NEWLINENEWLINE The last section of the paper is devoted to Boolean functions \\(f\\in P_2^n\\) (even for \\(n\\leq 6\\), very large cardinalities have been obtained and they had to be calculated on a computer).NEWLINENEWLINEThe text is enriched by a couple of illustrating examples.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2806555$D72FBD76-608F-4C3F-B1D1-D5268772424C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69b1bcb141ed2a99fdbd1cc9a0c46453e373e666","datavalue":{"value":{"entity-type":"item","numeric-id":271693,"id":"Q271693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2806555$8A784B20-9B80-4515-9053-5EB612B63048","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c8ae0c6fd5215d763b2d56c4c61851b80c64f65","datavalue":{"value":{"entity-type":"item","numeric-id":1272598,"id":"Q1272598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2d394560efbf9ef9c158aa0fd7fea7b3347877e","datavalue":{"value":{"amount":"+0.7625579237937927","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":"Q2806555$30C9E11D-942F-43E4-80BB-86851FFBFE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"365e5b3c1b212c051cba574c3bb8b7d6f1a9e73e","datavalue":{"value":{"entity-type":"item","numeric-id":1280364,"id":"Q1280364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03c7046bdfda90ef9449906b5369c77a76eaf5e9","datavalue":{"value":{"amount":"+0.7600586414337158","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":"Q2806555$14DC3679-D0D9-49ED-813E-D9A50A43CCFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db0e7dca8b654331624bd523ec9eff359015263f","datavalue":{"value":{"entity-type":"item","numeric-id":3140296,"id":"Q3140296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bae409f6ba453c015be6ac8d32eca9ba9d89c7fe","datavalue":{"value":{"amount":"+0.7571036219596863","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":"Q2806555$99D4441B-64E6-47B2-8E6C-0047F2977033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dda3c8a687f691e64cda8795e6471f617d2b01d","datavalue":{"value":{"entity-type":"item","numeric-id":3456078,"id":"Q3456078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d072d50bf780679a6abe3b49394b0aed6fdafff","datavalue":{"value":{"amount":"+0.7559892535209656","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":"Q2806555$889A2362-5ECF-4BD3-8926-C1BB9E26ADD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee6b1c16f85105046d1f0726c0764cf6625425ff","datavalue":{"value":{"entity-type":"item","numeric-id":2455087,"id":"Q2455087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faca10ca6380e0ccc65d6c6def726b48216970a3","datavalue":{"value":{"amount":"+0.7547473311424255","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":"Q2806555$0D13D2EA-4036-4227-A00C-1E35AFC3B28D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of finite operations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_finite_operations"}}}}}