{"entities":{"Q2639637":{"pageid":2650380,"ns":120,"title":"Item:Q2639637","lastrevid":49458211,"modified":"2026-01-07T04:57:09Z","type":"item","id":"Q2639637","labels":{"en":{"language":"en","value":"Self-reducibility"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4185028"}},"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":"Q2639637$70E492A3-6DC0-4901-A384-3C5DB638FF4C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea7523cf91751171090e12df6df26a9ca33b0764","datavalue":{"value":{"text":"Self-reducibility","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2639637$8BC523BE-0C85-48F8-A260-7C9E911B8B1E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"46e60f9d5b0a261240a351bb77b92b8138732b01","datavalue":{"value":"0718.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$F49594DF-6CE9-441E-9D6D-3F00FCD0059C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b78f6b465dbfc17827c9ec358523d024d24b41a6","datavalue":{"value":"10.1016/0022-0000(90)90025-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$061ECA88-280C-4E95-A6E0-47AB2E8FB44C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"387251027f7a6e047be71bdb6ddf8e33740cddeb","datavalue":{"value":{"entity-type":"item","numeric-id":415620,"id":"Q415620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$9CEB7212-18AF-45E9-8191-55673D5318C7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$A8C980D6-E306-49E0-9833-185C2717054D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2639637$E777E804-2EA0-4EB2-BAE4-133303DBAD7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"35434245faf444762011ab20267877a89ff119ca","datavalue":{"value":"In the paper the ldq-self reducibility, wdq-self reducibility, and logspace self-reducibility are defined (ldq stands for length-decreasing queries and wdq for word-decreasing queries). The properties derived from the definitions regarding the interconnection between uniform and nonuniform complexity classes are used to prove known results and to obtain new ones regarding deterministic time classes, nondeterministic space classes and reducibility to context-free languages. From new results obtained here, we remark the following:    i) Let A be a logspace self-reducible set. If A \\(\\in NLOG/\\log\\) then A \\(\\in NLOG;\\)    ii) Let M be a pushdown automaton with no \\(\\lambda\\)-transition which accepts by empty store. There is a set A \\(\\in LOG(CFL)\\) which is logspace self-reducible such that L(M) \\(\\in DLOG(A)\\). Furthermore, if M is deterministic then A \\(\\in LOG(DCFL)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$D32DB0E4-4D97-4D3D-B897-B2F219E64DA7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$39E11CCA-3B77-442B-BBB7-0DBC30D34261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$8B267A92-444C-40AA-86AA-A48695604025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$B714D554-13CC-4421-B67C-3FEDCF0D6905","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e9fe7c0ff95ab8d2a9b16b5268fb2c6346f9a746","datavalue":{"value":"4185028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$E21836B1-9914-49C2-AAB6-5687B58F2277","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bf39ff67c734ccef72308ae15736ee44ba84c0c","datavalue":{"value":"self-reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$8B8D58EF-0706-45E0-9C61-491C6A060E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$0B5AA3C1-77ED-42BA-9EBA-B8188201B592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"758c2d629296a78dc01564f56b989c7aa0681633","datavalue":{"value":"oracle Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$9B861F45-28B0-48F9-9DCA-2F34D747EA1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc14c918aaabdd88608475468949fd305227884b","datavalue":{"value":"deterministic time classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$08723298-8D83-4D71-85F9-2F652763356B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7fd929aa74969ddbda826107f41ca5a421ba780","datavalue":{"value":"nondeterministic space classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$34C680AB-380B-48A8-9E95-E7C8A11F657D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4c7798fabe567c02d1f38b084e67aaf82fca47b","datavalue":{"value":"reducibility to context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639637$2D99F224-86AF-47C1-AC51-BA1B24FD44F3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c03730668db67f2f0525cd022cd794bdf73f905","datavalue":{"value":{"entity-type":"item","numeric-id":916649,"id":"Q916649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$AF0193A1-20D7-4798-A22A-056CB685A97D","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":"Q2639637$ADACF9D1-D9D3-4031-87A1-3889C318BF7A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1102363b9c9d008d886a3d89c5a75b77c6d2469f","datavalue":{"value":{"entity-type":"item","numeric-id":5672196,"id":"Q5672196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$3EA25A65-CC7F-4C68-9CCA-4EA99564ED77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20dbb88399b28648dc9d78bc8b7f00777d16b9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$1953FD38-3BB2-4CF0-8B1D-59123B3F0E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ae69f8ff95a1054d345672afc2549299a932f6","datavalue":{"value":{"entity-type":"item","numeric-id":3692867,"id":"Q3692867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$F73FE25B-240C-48AF-AF65-3EC1C74D35AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4553a412b4b55bb167272479a5aca159281f2c2","datavalue":{"value":{"entity-type":"item","numeric-id":4160434,"id":"Q4160434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$570E025E-677F-48EB-926A-6E7CBED2A476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$35643DA4-7FBE-4754-999F-3D9727B85AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$47A946FC-20DE-48D6-ADD3-466F644CD62D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cd3656cf316bb6b47d075cb851e6ca065390824","datavalue":{"value":{"entity-type":"item","numeric-id":3051374,"id":"Q3051374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$DECFC726-ADA8-4631-8695-A5310DBF28F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$B25F2AFB-3573-4E81-9688-1C34D4FC0CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$A1A8FAF1-5F70-4CAD-BBFB-3EC66FF6F8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$BA9BEAA4-5CCC-4A2D-8438-BEEB8D5F5E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cded707123398ff6798a322d45de37a4390f5b2","datavalue":{"value":{"entity-type":"item","numeric-id":787674,"id":"Q787674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$A7E4E3EE-4B12-4F81-8B06-12FCDA2AEC76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$23E24FCC-8A14-4E2E-AEF0-ED520B8C75A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$B038F60C-D3D1-4971-95ED-96AA086F6761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8194b210616a81519a29e9c197fab619e01f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1062759,"id":"Q1062759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$4B705F31-8F28-4AEC-9B62-ACA924C1AB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59a71ee27fc06ad3b0b4b92d7dad58a5649789e7","datavalue":{"value":{"entity-type":"item","numeric-id":4158497,"id":"Q4158497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$699A4C59-3ACF-452B-8DFA-905E4491F066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639637$9E1278CB-867A-4DC6-BC96-BBC6AF2153DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"07fda802d85ac96e2add52d9b0d7406d258d58e1","datavalue":{"value":"https://doi.org/10.1016/0022-0000(90)90025-g","type":"string"},"datatype":"url"},"type":"statement","id":"Q2639637$4D4266F1-61D8-4935-AF86-2790AFF14CED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a9561d0e6068372c3c20a271c390b2d13f8d08ca","datavalue":{"value":"W70814323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639637$3833847E-74FC-4942-9848-D7CE26FAE14D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7e5fe6bdf43cc55045c1121334ce8d348521d39","datavalue":{"value":{"entity-type":"item","numeric-id":3765251,"id":"Q3765251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de2fab5dc84b77a615d037c73dfc7654b10a5093","datavalue":{"value":{"amount":"+0.8642114996910095","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":"Q2639637$8D5978C3-7C9E-4C0A-9D54-3DE505627E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf102d8b18f5917a74c27b88aa373640eabb50da","datavalue":{"value":{"entity-type":"item","numeric-id":3210176,"id":"Q3210176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42c62cc8f8ea173a792f0dd750a19d8ab2df1507","datavalue":{"value":{"amount":"+0.8081005811691284","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":"Q2639637$7A46653A-2EA4-4D47-9B9D-9C7B41DCF7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"762f764aba4e743b1e95274db89089b2e0502b4f","datavalue":{"value":{"entity-type":"item","numeric-id":5492867,"id":"Q5492867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30a724ab6c345ed3d6b6fc80af736a946d7d86fb","datavalue":{"value":{"amount":"+0.806052029132843","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":"Q2639637$75D67FFB-3DD0-42B4-82FE-37E9FDDC8D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60d373f1db83223e32cd8f46381b4db692c11d0c","datavalue":{"value":{"entity-type":"item","numeric-id":3816974,"id":"Q3816974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4614ef504d6f987a10f48c49851674654af14fd6","datavalue":{"value":{"amount":"+0.7916868329048157","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":"Q2639637$83444BDF-6B9F-4F16-8101-D82D80F67F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4671e20e55fd66149796a8476cb163b99fb1f344","datavalue":{"value":{"entity-type":"item","numeric-id":3682474,"id":"Q3682474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b6aeb48de1029079b41ba8b8cfe241669d4357a","datavalue":{"value":{"amount":"+0.7910376787185669","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":"Q2639637$2781DA98-0157-4276-B61E-76818D48EE64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2639637","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2639637"}}}}}