{"entities":{"Q792758":{"pageid":794606,"ns":120,"title":"Item:Q792758","lastrevid":64375839,"modified":"2026-04-11T19:26:43Z","type":"item","id":"Q792758","labels":{"en":{"language":"en","value":"The complexity of monadic recursion schemes: executability problems, nesting depth, and applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3854412"}},"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":"Q792758$25E95460-DB84-4D1E-914A-5DA5E4EE1F3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b7a09256928b4b619230fda87c718dd95a76fdd","datavalue":{"value":{"text":"The complexity of monadic recursion schemes: executability problems, nesting depth, and applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792758$8C88A0D8-A1A1-4C78-BEE7-F7D9D1F7CEEA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"80ebbb15781652fb47ab1d9d8ee3554c7e432663","datavalue":{"value":"0537.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$603493EA-2F8B-4704-8FCE-9276316DFF46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"952b2f12f3c5861671f8e33436616d59efd634ec","datavalue":{"value":"10.1016/0304-3975(83)90091-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$2D27D26F-D474-41E7-B013-CAC93F07CA84","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792758$909440E6-4DD1-4D85-ACAF-BAF4DF038FD2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q792758$085E82DB-BAA7-4013-81FC-C4043E64E97C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8ef93c6cfbc669054331b11c778a6aa0c688245b","datavalue":{"value":"Die Arbeit befa\u00dft sich mit der Komplexit\u00e4t des executability- Problems von Rekursionsschemata. Die erforderlichen Definitionen des ''monadic recursion scheme'' einschlie\u00dflich der Interpretation, bzw. der Herbrand-Interpretation, der ''configuration'' und ''computation'' finden sich im zweiten Abschnitt ebenso wie eine Zusammenstellung von damit zusammenh\u00e4ngenden Entscheidungsproblemen (executability, totality, divergence, computational identity (weak/strong) equivalence (weak/strong), isomorphic). Im dritten Abschnitt werden m\u00f6gliche Reduktionen solcher Entscheidungsprobleme aufeinander, insbesondere das executability-Problem, behandelt, sofern sie in Polynomzeit m\u00f6glich sind, und zwar f\u00fcr verschiedene Arten des Rekursionsschemas (allgemein, total, linear). So ist z.B. das executability-Problem auf das non- divergence-Problem zur\u00fcckf\u00fchrbar. In diesem Abschnitt werden 11 S\u00e4tze zur Reduktion der Probleme zusammengestellt. Im vierten Abschnitt werden drei Ma\u00dfe (ND-, EP-, Max-nesting depth) f\u00fcr die Tiefe (nesting depth) eingef\u00fchrt und worst-case-Betrachtungen angestellt, deren Ergebnisse in Tabelle 1 zusammengestellt sind. Dabei ergeben sich f\u00fcr das allgemeine Schema exponentielle Schranken (EP, Max), f\u00fcr das totale bzw. lineare Schema Polynomschranken. Theorem 4 z.B. sagt aus, da\u00df die ND-nesting depth gr\u00f6\u00dfer ist als \\(2^{cn}\\) mit n als L\u00e4nge des Schemas und \\(c>0\\), Theorem 11, da\u00df f\u00fcr ein totales Schema die EP-nesting depth gr\u00f6\u00dfer ist als \\(cn^ 2\\) mit \\(c>0\\), in beiden F\u00e4llen f\u00fcr unendlich viele n. Im Abschnitt 5 werden die Ergebnisse der Abschnitte 3 und 4 benutzt, um Aussagen \u00fcber Entscheidungsprobleme zu machen und entsprechende Algorithmen beispielhaft zu entwickeln. In Theorem 5.2. wird angegeben, f\u00fcr welche ''monadic recursion scheme'' (allgemein, linear, total) es ''nondeterministic polynomially time-bounded'' Algorithmen gibt, um die angef\u00fchrten Entscheidungsprobleme zu l\u00f6sen, und zwar f\u00fcr 12 F\u00e4lle, basierend auf den Komplexit\u00e4ts\u00fcberlegungen.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792758$ABAA4001-36A5-4676-A818-1D9FD71275DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$2CF115BB-A3F5-4405-B28D-9FB4118EE25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$1BD97CE0-2093-4DD1-BDB1-2D73237C1A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$1B415A0E-BEE7-496C-B518-706A8E5C4ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$D6BE35A7-F30B-4382-90BF-45B3E9EC050C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"38f07481b73d87806f9b8d93fc4cf73b58ae6389","datavalue":{"value":"3854412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$1D181A53-EF75-48DB-80A4-B5F8C11C0215","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"685efb8534091d63b5a5b491f805d8e4eff2c0ca","datavalue":{"value":"monadic recursion schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q792758$8D58A9A6-1B2B-4828-A387-090EDB38B61C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9264ba9bd1d67ffa8c9f85bb32a147a81c5a9cc8","datavalue":{"value":"executability problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q792758$04E46E86-F526-4690-89DB-184AFEC5CCA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84eaeaa21f664f66e1da49f0596e885115497974","datavalue":{"value":"complexities of decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q792758$397EF240-9D4E-481A-9805-D9A5A57B8273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c9db421c366b528b07bacbff7f4640b23c82c6e","datavalue":{"value":"maximal possible depths of nesting of function calls","type":"string"},"datatype":"string"},"type":"statement","id":"Q792758$93FD1A1A-7ADF-4566-A024-A3CD243B0F1B","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":"Q792758$2E9E6CF8-18EC-45A6-83BF-C680367D7099","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":"Q792758$05B4CECE-6230-4859-A233-299EC217D880","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":"Q792758$289AB0E6-626C-42AA-9F7B-CB71C2726A84","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"391464912a51455fe52117f9d6eaffce07b47d88","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90091-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q792758$37431A63-AC95-499B-8874-A4D92DE62F63","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51f3a017517ab4bde995a0031dff88f310e185f4","datavalue":{"value":"W2085033370","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792758$EED9D5FB-F33D-40DD-AF14-F663D6BD9033","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792758$DAB83DBE-E08D-41E3-8878-EE661A19BA77","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":"Q792758$4F7E031D-9883-4A0F-B24F-E2B11B379ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5647bdb24911b4708fca5d64089ca879c561bdce","datavalue":{"value":{"entity-type":"item","numeric-id":3923599,"id":"Q3923599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792758$474AF993-D833-4AF6-90B4-599F62C8AFA8","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":"Q792758$28922123-A260-4866-8FFB-1169885C75B7","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":"Q792758$D4039DD9-7D96-4EF1-9282-860CEB1E659B","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":"Q792758$4C0C67D0-BE5E-421C-A030-148B88DEE679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"163e69448d39ad531e4cc97f8ffafd03a99ce660","datavalue":{"value":{"entity-type":"item","numeric-id":1393937,"id":"Q1393937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792758$36CD2EE5-756A-4382-9C37-D505AE651C18","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":"Q792758$EA1E544B-415B-425E-9986-18F6A9DB87B2","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":"Q792758$8B873F18-7326-4972-AD68-8B63CDD356FB","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":"Q792758$77799FFA-7D56-4B5D-BE0B-94E956CC8C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792758$89B40CA8-D5B1-4479-9E31-82F739210516","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of monadic recursion schemes: executability problems, nesting depth, and applications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_monadic_recursion_schemes:_executability_problems,_nesting_depth,_and_applications"}}}}}