{"entities":{"Q796301":{"pageid":798149,"ns":120,"title":"Item:Q796301","lastrevid":64405047,"modified":"2026-04-11T19:38:27Z","type":"item","id":"Q796301","labels":{"en":{"language":"en","value":"The complexity of monadic recursion schemes: Exponential time bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3864499"}},"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":"Q796301$A19B6484-4A83-48CA-9D17-560FB485CC0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fc45114cc94f37de0edb969db9d4fefdb2c7db7","datavalue":{"value":{"text":"The complexity of monadic recursion schemes: Exponential time bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q796301$2F161197-850E-46DF-98B6-E7CE7D7491BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe6113a15e9a6c9272481fa15aaee490c1a694ab","datavalue":{"value":"0543.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$1953871D-CB23-45F0-B79F-307BA3985C5B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f8eb1a42b613f95783b498aa01e6384b76d72b3c","datavalue":{"value":"10.1016/0022-0000(84)90021-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$3A543125-BD7E-429A-9947-7A189C77ED58","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":"Q796301$87ACDFDF-2072-4F56-990A-BCCC93F769BC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q796301$BEFA51D6-C005-4013-8FFD-73464020B767","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16160177001e9e377766f63eb45c2b271afbe06c","datavalue":{"value":"We study the computational complexity of decision problems for the class \\({\\mathcal M}\\) of monadic recursion schemes. By the ''executability problem'' for a class \\({\\mathcal S}\\) of monadic recursion schemes, we mean the problem of determining whether a given defined function symbol of a given scheme in \\({\\mathcal S}\\) can be called during at least one computation. The executability problem for a class \\({\\mathcal C}\\) of very simple monadic recursion schemes is shown to require deterministic exponential time. Using arguments about executability problems and about the class \\({\\mathcal C}\\), a number of decision problems for \\({\\mathcal M}\\) and for several of \\({\\mathcal M}'s\\) subclasses are shown to require deterministic exponential time. Deterministic exponential time upper bounds are also presented for several of these decision problems. The decision problems considered include the computational identity, isomorphism, strong equivalence, weak equivalence, and divergence problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q796301$CF2644A7-FDE9-4A0A-80B5-B20EB1EF6BCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$BF8C0CD4-ABD2-4862-9740-55244E34D743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$ED6C75F5-6FC2-45EB-B16C-42CC481CF075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$D711FBD1-5112-42AA-A74A-C01566AF40C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"547d3fe4926c3ab3ed492c64d32074c8b359aeba","datavalue":{"value":"3864499","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$D2013C08-DF2D-4951-9A63-C970E8BC8535","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q796301$C51A8494-AA76-4C92-9E7E-5C2B9699FF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"685efb8534091d63b5a5b491f805d8e4eff2c0ca","datavalue":{"value":"monadic recursion schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q796301$33074494-70BF-4D04-8CE3-CBE6D3F5DB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9074bd0970f3214dae9725c0a4cf63e777811148","datavalue":{"value":"executability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q796301$CA8DCA8B-581B-43F6-BC08-32FC79C76860","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5488902e73ee01b0a591b24e9f1dea0f7a9b6126","datavalue":{"value":{"entity-type":"item","numeric-id":549706,"id":"Q549706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$B57C5639-084E-4643-94D7-1E0FCB265B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c132f21e8ff85d87643618fdfbf26f24121a6ba9","datavalue":{"value":{"entity-type":"item","numeric-id":549707,"id":"Q549707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$05BDBF70-ADE2-4169-B81F-2726CD3AAEA4","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":"Q796301$231DFB04-DBED-43AD-B9C0-CD2834F13CA4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"03b437efe3736efe4c16bb74479e92957176b8ac","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90021-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q796301$BB38951F-33FD-4E54-9AD1-FDB4E94D2339","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9fbb5c9a8d5ad0f048d142af17933e84ce776d9f","datavalue":{"value":"W2013008477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796301$21933D56-6F06-4CFA-900B-A9C34A43EE93","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$426D920E-FD51-4242-8C0D-5B86E73B4627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"766193ea784b0bffcc9336764f331a23489436bf","datavalue":{"value":{"entity-type":"item","numeric-id":4041106,"id":"Q4041106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$9F73AC30-481F-4206-BF43-333CFB63B3E5","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":"Q796301$7E8A333B-1265-4ECF-B635-170DDA124225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32a2683c14499aa11e6f27fa400a157ff6431c25","datavalue":{"value":{"entity-type":"item","numeric-id":1238426,"id":"Q1238426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$985FD7B4-2920-48B4-B4AE-A384B3058E8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f1cede33249053e58f34bbfd2ab55b37b3edbdf","datavalue":{"value":{"entity-type":"item","numeric-id":1259576,"id":"Q1259576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$50359907-DE94-4D5E-8FC5-2729D52443B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd2e99a924656d0ca66fd0a901c3e99ae72e2cf9","datavalue":{"value":{"entity-type":"item","numeric-id":4057636,"id":"Q4057636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$4C0E8FE5-74A5-4254-B5F7-3D4BB0833924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112f7bbf702231dfdf6265079054edfe9355779d","datavalue":{"value":{"entity-type":"item","numeric-id":4146243,"id":"Q4146243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$5BE209F2-B187-4B64-97AA-08E8BEBD89BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$D4246E56-6934-4A68-9A55-0D7DB118BDCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62af4edc351f6914c56e200b7cbf4266e2b7ab32","datavalue":{"value":{"entity-type":"item","numeric-id":3933741,"id":"Q3933741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$7904C6F9-05C6-4818-BDB0-E5EA1A245E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd5be0fecce7c6688670776065e5263cab975f7","datavalue":{"value":{"entity-type":"item","numeric-id":3893301,"id":"Q3893301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$D5AB2504-E22C-4BB1-A715-584600B92BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"028f702fb4624648200f4a9f3005a90cf5544f4a","datavalue":{"value":{"entity-type":"item","numeric-id":792758,"id":"Q792758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$1EECCDA2-EC3C-4F38-8AE7-1E463FE6A37C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda427bf3691d6d17e30eb998c33bad84c6e4597","datavalue":{"value":{"entity-type":"item","numeric-id":5732102,"id":"Q5732102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796301$87061975-628F-463F-B667-7B2E4F93D618","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa91ab3c5152869ecd26c381408d365defb5fa9d","datavalue":{"value":{"entity-type":"item","numeric-id":3732943,"id":"Q3732943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e25b076c33573c98fe4d90bd8e18493631a71541","datavalue":{"value":{"amount":"+0.7917051315307617","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":"Q796301$AB48F0F4-C64C-406F-B54E-771B5807B8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5771d211463558f9059768007c95f170aa5b439","datavalue":{"value":{"entity-type":"item","numeric-id":4635654,"id":"Q4635654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3228bef98d63c2b5896ef6c808c8d33d76d3c5d","datavalue":{"value":{"amount":"+0.7748077511787415","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":"Q796301$0BA7CA29-A052-4334-88EA-3A108905EB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9b84eaf773193e973dfedcbc9445b6b0d883a8","datavalue":{"value":{"entity-type":"item","numeric-id":5277914,"id":"Q5277914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5003348deef05a22f930c60af36b0233c66ba9a","datavalue":{"value":{"amount":"+0.7511253356933594","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":"Q796301$08890270-5B9E-4903-86BC-59770B309E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1811b900989087071a515a60ca8d3d59894fba48","datavalue":{"value":{"entity-type":"item","numeric-id":1058305,"id":"Q1058305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8acc7435cd2852d389f86f7c8b0103a0921f2c","datavalue":{"value":{"amount":"+0.7487946152687073","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":"Q796301$E35824B1-A238-4584-AA80-EBF33ADAEB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95fecd08ae32fff5542bc4aed0604a36705e9eaa","datavalue":{"value":{"entity-type":"item","numeric-id":5902152,"id":"Q5902152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef1913d3d31e76675359fee52aab57a20dda15fa","datavalue":{"value":{"amount":"+0.7483605742454529","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":"Q796301$E703AA29-6127-4652-BA82-2BCDA269B38B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of monadic recursion schemes: Exponential time bounds","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_monadic_recursion_schemes:_Exponential_time_bounds"}}}}}