{"entities":{"Q868660":{"pageid":870508,"ns":120,"title":"Item:Q868660","lastrevid":50044861,"modified":"2026-01-12T19:08:49Z","type":"item","id":"Q868660","labels":{"en":{"language":"en","value":"Complexity of admissible rules"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5131231"}},"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":"Q868660$D8FD1F0A-5D80-47D2-94FB-73E04BDCCBB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab1aa177bd5f6a7780f21f613ce39aafabb8644e","datavalue":{"value":{"text":"Complexity of admissible rules","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868660$0B64132D-15AF-4BAB-8840-7E028CA78071","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"97a1e091ccff24bceabe6c631f1ce9be399f01dc","datavalue":{"value":"1115.03010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$7CEFA808-A416-43EE-A574-909EA686D480","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1376d5316fb71db1c6e9bf664dff79c67388b0d","datavalue":{"value":{"entity-type":"item","numeric-id":331053,"id":"Q331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$19DCDB2A-9B4C-40BE-8686-F0B5345BAB1F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a0a7cd28a9f85b9c6ad57bd5bb1ae477bfe37846","datavalue":{"value":{"entity-type":"item","numeric-id":114337,"id":"Q114337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$47EC6063-AB68-4361-AA12-5A6E890E09AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5823d03fbcff5d473b8034cff96a416b6d05e19","datavalue":{"value":{"time":"+2007-03-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868660$F2B1A103-8F97-4EA2-8A9D-DC65A16E1319","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9125480824fac219654c909a807e8dc09860eb49","datavalue":{"value":"An inference rule is admissible in a logic \\(L\\) if the set of theorems of \\(L\\) is closed under the rule. V. Rybakov proved decidability of the problem od admissibility for many modal and superintuitionistic logics. The author provides complexity estimates for this problem which are optimal or close to optimal. Admissibility in ``typical'' extensions of K4 and superintuitionistic logics is co-NEXP-complete while derivability is P-SPACE-complete or even NP-complete. A co-NEXP decision procedure is given for admissibility in a class of logics including K4, GL, S4, S4Grz and Int. Admissibility is proved to be co-NEXP-hard in all superintuitionistic logics \\(L\\) such that every depth-3 tree is an \\(L\\)-frame and in similar normal modal extensions of K4.","type":"string"},"datatype":"string"},"type":"statement","id":"Q868660$CB88850E-AE7A-4527-87F0-3A65838354E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$456529B5-16EE-4562-9913-DA5F15FF3AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"87f66489f0c14f30094b654591a05fdd61321103","datavalue":{"value":"03B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$E91BC96B-3935-4D7D-BA79-677E171F1AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$95EEF38F-9C65-461D-BBE0-5FA7F7018730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$0FBC2890-8242-4383-9EA8-7B0FC6C2BE1D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9e47cff67fe71365774288e351860c4822f8a0a","datavalue":{"value":"5131231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$7F506E06-3312-4031-A294-19A5911AF7D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"203383f5640e2b7ae9ac255db7b9410f9f3dc7ba","datavalue":{"value":"admissible rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q868660$B742D410-1E7C-40D8-931B-0CACAD5CC2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q868660$E2DE6A12-FD5E-46E9-8A1F-56C4C5FE55DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1dda010537b7b36bd45151721146f720815706e","datavalue":{"value":"modal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q868660$8838F436-BF53-4898-B8A8-89000C04417A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e20caaf0551fe84fb69eae2f4da361eb77759b92","datavalue":{"value":"intermediate logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q868660$368CFD01-1458-4C68-8C85-07A755F139D7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f67059196a9c6abd6f375f15010545c8d210e07c","datavalue":{"value":"Q56474452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$382F1BAA-C5F2-488F-AF44-8CBD6F66FA39","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f432bccb81d11b6d0c5be5373ba82abf19c1967","datavalue":{"value":{"entity-type":"item","numeric-id":454365,"id":"Q454365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$09072F42-ED2D-4F4A-8646-9787B8F106FA","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":"Q868660$1040F7AC-5AAE-4039-AE18-3AB6232114D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c6763f3d6492a2d97dbb41b2fd9d18e4c82530ba","datavalue":{"value":"https://doi.org/10.1007/s00153-006-0028-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q868660$5B9792A6-9DB9-4472-A54B-9D5CA07F1C0B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d431f01e80f14cd0841b1f4443af1bdf3bc39dd8","datavalue":{"value":"W2111570288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$ECDAE4CB-729A-4914-B873-29A5E6705EF8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc87194f53a9552766b22cbe3fffae4e25dcae6","datavalue":{"value":{"entity-type":"item","numeric-id":2744124,"id":"Q2744124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$81A952D3-0A89-4C19-B45C-B5B312E53AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fefae4aad4ffe92f5da65d23427de4252bca48f2","datavalue":{"value":{"entity-type":"item","numeric-id":5533177,"id":"Q5533177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$CE83D2E9-5C46-4A23-8BB5-7C486310B0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f718d8e8c73e0b0c970c4fe73823fad74cf6674","datavalue":{"value":{"entity-type":"item","numeric-id":4723713,"id":"Q4723713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$80E42348-100D-440C-8637-2D7AE6E704A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"414ff478075da6ed3a37a40aa68960580097e7ff","datavalue":{"value":{"entity-type":"item","numeric-id":2366361,"id":"Q2366361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$E65A97CC-8606-4AD9-BD9A-FF5995FD4FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f72c6e6f4ce6722d395e819cddc203e8d1adeec","datavalue":{"value":{"entity-type":"item","numeric-id":3128959,"id":"Q3128959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$5F5E9B16-D5FD-4D26-9963-660AAB3E7605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$41E0DD80-A3ED-44B7-B96A-7A346CFB2300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"450ff4101819de0e4417c076932f8fb04360f092","datavalue":{"value":{"entity-type":"item","numeric-id":4079563,"id":"Q4079563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$C5E1C871-8450-4B14-8CBB-521AE493C5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23c0b751d53100e5622267bb83d21d96dd380202","datavalue":{"value":{"entity-type":"item","numeric-id":4262590,"id":"Q4262590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$BB2114B1-848C-4090-A3FA-3E7C0CB74742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d86df6ede1ae2f2b3db613612faa7cf4f173a1d0","datavalue":{"value":{"entity-type":"item","numeric-id":1971794,"id":"Q1971794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$C34B87A7-6EC5-4ED6-84C4-2EBFD9B4AF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f01d004bc791b096d5f460ea55dd47f3931feec9","datavalue":{"value":{"entity-type":"item","numeric-id":3147430,"id":"Q3147430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$528A865B-2CE7-41DB-B4F4-CF1F92B3F548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07d3fe70dc62991e79e222a7fc408e5bec950513","datavalue":{"value":{"entity-type":"item","numeric-id":2732279,"id":"Q2732279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$2D81B7E8-DA23-4678-8272-BA87D9061C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"468a3a1c09b18a83961082ef93dd46e46840fb7d","datavalue":{"value":{"entity-type":"item","numeric-id":558441,"id":"Q558441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$DC47BC46-2C81-4218-AC16-C3D81F864915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64e8860a69ed37e50bd2086d4bbcfa819c116e5a","datavalue":{"value":{"entity-type":"item","numeric-id":2501166,"id":"Q2501166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$20A77CED-5858-48B6-B81A-2DF1F0DE9AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05fa13f8d08455deabdb8d53876205365d278e87","datavalue":{"value":{"entity-type":"item","numeric-id":5696300,"id":"Q5696300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$6ACDBA17-DA4F-4D06-BE61-FB746B45EC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"158780c5b17a311ed724c022ce7bd7ec55df7323","datavalue":{"value":{"entity-type":"item","numeric-id":4109648,"id":"Q4109648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$FC6B3CF0-2DA8-434D-B57C-238952AB0779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f66774e18bf6d9e857072576d53e1307dde765","datavalue":{"value":{"entity-type":"item","numeric-id":4149442,"id":"Q4149442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$AB6C9093-416E-4B3E-9D19-5A1A8EDFE41A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$28F819F9-07A5-4511-A27D-69B2A6616C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f42c62c4402b806ab53881fc2a7a5ded7808d96c","datavalue":{"value":{"entity-type":"item","numeric-id":1309039,"id":"Q1309039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$661D8D4E-EBB6-4ABE-9C5E-181F3F8BBEC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46ed020b59c477403bed93a2bd5eae02fddd49ee","datavalue":{"value":{"entity-type":"item","numeric-id":4833777,"id":"Q4833777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$E415E482-DE42-4656-9F6A-501BB14D00E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cea085d8c059c5f81ccc8c6d0a2a9f9fb30e1313","datavalue":{"value":{"entity-type":"item","numeric-id":1259589,"id":"Q1259589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$D57FF8F5-475B-4E39-9D94-DE9C6E519CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84bd6b5a534f67b6b7d4c37a09d43bc1c1517c9","datavalue":{"value":{"entity-type":"item","numeric-id":4894720,"id":"Q4894720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868660$E7FF2069-51A1-43BD-8652-2163EC3D0691","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d1aada80c7a97b6b236042a1a4a0703c9180a30a","datavalue":{"value":"10.1007/S00153-006-0028-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868660$8B4AE635-8312-4B47-9C8F-CC1A3CA3E711","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"930f741a1bd06b4da07606a475888b5429b802c8","datavalue":{"value":{"entity-type":"item","numeric-id":5300587,"id":"Q5300587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66d2a9971a07667451f9a33a39a988506beb4be7","datavalue":{"value":{"amount":"+0.8378865718841553","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":"Q868660$6BB8BB44-0200-4AC9-B068-F4AFEB89B77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ebc03e482d5f1b98817c56429a3448862d84bb","datavalue":{"value":{"entity-type":"item","numeric-id":3727965,"id":"Q3727965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1c684954767efe4620cd942c83551130747a049","datavalue":{"value":{"amount":"+0.8320795297622681","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":"Q868660$BB1F0A74-3276-4A14-BF4B-D9398FA8A637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f36600e3c654c93d5b57797cb869f58f012d5253","datavalue":{"value":{"entity-type":"item","numeric-id":1327480,"id":"Q1327480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80d79a63f21baf6305d02f2f532a50f225058d6d","datavalue":{"value":{"amount":"+0.827727198600769","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":"Q868660$38B8E6EB-B724-45D6-AEB2-60AAF11D6AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9938aea63beadaee8d43673745b5abff62807429","datavalue":{"value":{"entity-type":"item","numeric-id":1309039,"id":"Q1309039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb0067c25ab13123b08744bd7b2ea999345ec83c","datavalue":{"value":{"amount":"+0.8262608647346497","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":"Q868660$EA5447AA-A73C-494A-8595-9AA5993681B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9cd4f64baf572fcefc7b8a2490cd580d174ec88","datavalue":{"value":{"entity-type":"item","numeric-id":1023055,"id":"Q1023055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c45393f240cd82131505fca1307d3ca8b30a5621","datavalue":{"value":{"amount":"+0.8182387351989746","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":"Q868660$90338BFA-9171-485E-8609-C8959FC4B7A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:868660","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:868660"}}}}}