{"entities":{"Q1064320":{"pageid":1075072,"ns":120,"title":"Item:Q1064320","lastrevid":66663672,"modified":"2026-04-12T11:39:00Z","type":"item","id":"Q1064320","labels":{"en":{"language":"en","value":"The recursion-theoretic structure of complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3920454"}},"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":"Q1064320$7E299710-839B-4195-AD29-1DF935D5A69F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef809207b6f8cffdd4c04831e2727171a9e9edda","datavalue":{"value":{"text":"The recursion-theoretic structure of complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1064320$F8C34904-B78C-4291-83C7-48B4535B312C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c84385f0552e52bf0884c1a0dc66307537157529","datavalue":{"value":"0576.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$E6F72918-6408-42C2-A2C1-18D887CD0CDB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"219bb0a802cd71b8635edfc63a88dda3ef620419","datavalue":{"value":"10.1016/0304-3975(85)90217-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$68976CC7-0679-4C56-8E81-74892DF2AC2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3ec08c7b048461a64e91b52501e8e1af6f4af0c","datavalue":{"value":{"entity-type":"item","numeric-id":1064319,"id":"Q1064319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$94BBD461-B1D8-4B0D-856D-06B4A031320A","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":"Q1064320$96A43E23-3233-4EB1-B416-301F9EA64EC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1064320$578A1C41-6B83-4B82-8B08-A32BCBCCF3C3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52f5c28d96e0229e92af28dab57db0aaa9cc902f","datavalue":{"value":"Let A be any language. A is said to be a gap language if A is the union of the maximal subsets of A of the form \\(\\{\\) \\(w| m\\leq | w| \\leq n\\}\\) (m\\(\\leq n\\in N)\\) (intervals of A). The gaps of A are the intervals of \\(\\bar A.\\)    A class \\({\\mathbb{C}}\\) of languages is said to be recursively gap closed if for every recursive gap language \\(G_ 0\\) with infinitely many gaps and intervals, there is a language \\(G\\in {\\mathbb{C}}\\) such that \\(\\bar G\\in {\\mathbb{C}}\\) and \\(G_ 0\\) contains infinitely many intervals belonging to G as well as gaps belonging to \\(\\bar G.\\) A class of sets \\({\\mathbb{C}}\\) is recursively presentable if there is an effective sequence \\(M_ i\\) of total Turing machines such that \\({\\mathbb{C}}=\\{L(M_ i)|\\) \\(i\\in N\\}.\\)    The author shos that if \\({\\mathbb{C}}\\) is a class of recursive languages which is recursive gap closed and closed under union and intersection, and \\({\\mathbb{C}}_ 1\\), \\({\\mathbb{C}}_ 2\\) are recursively presentable classes which are closed under finite variations then \\({\\mathbb{C}}\\subseteq {\\mathbb{C}}_ 1\\cup {\\mathbb{C}}_ 2\\Rightarrow {\\mathbb{C}}\\subseteq C_ 1\\) or \\({\\mathbb{C}}\\subseteq {\\mathbb{C}}_ 2\\); and \\({\\mathbb{C}}={\\mathbb{C}}_ 1\\cup {\\mathbb{C}}_ 2\\Rightarrow {\\mathbb{C}}={\\mathbb{C}}_ 1\\) or \\({\\mathbb{C}}={\\mathbb{C}}_ 2.\\)    The article contains a series of results closely related to the one just mentioned. The complexity classes DTIME(n), DSPACE\\(_{on-line}(\\log n)\\), the class of context-sensitive languages are shown to be recursively gap closed. The class of context-free languages and hence also that of regular languages, is not recursively gap closed. The article contains a number of other results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064320$7C28D631-45DA-4F78-AE4C-458426302211","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$EA07B1B6-6902-4859-B7D9-A6900DFC80EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$E83007A5-7E4E-4482-8E74-AAF3A2AAD6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$0F3C9266-289C-48BF-ACDE-3D19AC6B7F26","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b062ba295a3f7ae3c99799f222becce13980346","datavalue":{"value":"3920454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$6340F385-C0FF-45FF-BCDC-550C39CB9312","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"382fbc84f88bb135306f240116317bfc66566716","datavalue":{"value":"gap language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064320$977FB513-3AB2-4C68-8449-594BE9C1F6CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"074bc6cb285bb787f6a8c12b4e2ac6f0fbd88ee7","datavalue":{"value":"recursive languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064320$00247307-2644-47BF-88F8-8BE23273A7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e9fadee09ea310ed913a3f846dc767f275a4647","datavalue":{"value":"recursively presentable classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064320$46490A70-B6FB-455C-AD9D-4662A5AB5FE1","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":"Q1064320$2B787841-48FC-42F9-BC52-89ED466EFD2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a534d03cafe2711f5653b3871d26c197d5210fdc","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90217-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1064320$E5AFB911-5FCD-4D5C-ADA6-6DAB80450CD2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb06f630042bfe768fdcb828e525306effc159f4","datavalue":{"value":"W2066107173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064320$985F6401-46C5-4265-99A3-E895ECF1143E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1fb329ed3fd0a0f916dbd8faa97acee5cf8861c","datavalue":{"value":{"entity-type":"item","numeric-id":5183082,"id":"Q5183082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$4D5631BD-D215-448D-9305-5EAB972E8681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a308524b150ea0978a37c4e6913368e76b231f7","datavalue":{"value":{"entity-type":"item","numeric-id":1251652,"id":"Q1251652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$F3E49D0E-39B3-48D5-8B8F-83DAC8758802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af52c66421185c07ca4d865efeb189c0dddc801","datavalue":{"value":{"entity-type":"item","numeric-id":1158964,"id":"Q1158964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$5417E784-F4E3-4439-A70B-3BF196759001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9757ce980c6f8fa87d540ce34490987cfec8474c","datavalue":{"value":{"entity-type":"item","numeric-id":1218269,"id":"Q1218269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$F5B6F26F-20ED-4E5C-A6A4-406295780040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66856e28a8d065ae00cc1eb109ee4001e24e8421","datavalue":{"value":{"entity-type":"item","numeric-id":5582355,"id":"Q5582355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$6589AA1A-4558-4301-9EA9-E929E9A31C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$F6AB9B57-7728-43DF-8C07-3E2856F90A39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$FB816D47-CB5A-41A9-A47E-E92EF3579315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ece2270b16b9fbc48e0a9ac072c1cea045ecd584","datavalue":{"value":{"entity-type":"item","numeric-id":1162811,"id":"Q1162811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$CE265E13-27C7-4234-9372-975B443FC612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5bee5357a250d05fef165e66d176475085e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":5180413,"id":"Q5180413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$F5F67DA8-DB22-48E1-8824-DB0E7C2523BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$07F98F7D-0ABB-43F5-BC89-481CA5C54B58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aba0de3b75117dfe261f81c9f5f4226509a524a1","datavalue":{"value":{"entity-type":"item","numeric-id":3312209,"id":"Q3312209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$20E3B09E-BAED-45E6-A3A3-3FBAE68FAB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$4BEC1767-62C6-4A09-8672-88A13C760191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a91a1ef633200d3b3409775b6e406f92f5e8db8","datavalue":{"value":{"entity-type":"item","numeric-id":3344189,"id":"Q3344189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$71FA790C-6645-42D2-84FF-F0544147A13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47d753588d3e15901e017390d393815c34f9ede","datavalue":{"value":{"entity-type":"item","numeric-id":5636862,"id":"Q5636862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064320$B390F77E-9088-41F0-A0B4-5A27D0CB159F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"751de868e3f18fa13820ffe8611f66d3a6f67460","datavalue":{"value":{"entity-type":"item","numeric-id":3832552,"id":"Q3832552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bfaa1adc448bf1aa64513bdde6a82521fa743c8","datavalue":{"value":{"amount":"+0.8168134689331055","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":"Q1064320$C47C13FA-DEC0-4208-8906-708799CD974D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43d5dd22cf1ed8248c69e88a336491cb01081730","datavalue":{"value":{"entity-type":"item","numeric-id":1389651,"id":"Q1389651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"166ab73701e8bbb2138c3bd5695c15c9729ee218","datavalue":{"value":{"amount":"+0.787443220615387","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":"Q1064320$9C980493-3B97-4E0D-8289-36930E704E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4542dc33a63986cbd1b9e1d2ec51a8587bf18dc3","datavalue":{"value":{"entity-type":"item","numeric-id":3344189,"id":"Q3344189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"920b424f17c18343bd9464d49a7dc3b3da7cc889","datavalue":{"value":{"amount":"+0.7681618332862854","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":"Q1064320$A847DFD0-5A74-4F40-A655-5A0D1C098479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97bf42f6aa2eb00febad6644591d5421667aacc9","datavalue":{"value":{"entity-type":"item","numeric-id":4281550,"id":"Q4281550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79fa7e20d242878abccabb0631684514d6d8ebcd","datavalue":{"value":{"amount":"+0.7437613010406494","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":"Q1064320$E454AB7A-68DD-45EB-80A5-9C22A781B563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb210b80fc589cc4d530c1290f2c8bb8865d2ebf","datavalue":{"value":{"entity-type":"item","numeric-id":4281699,"id":"Q4281699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db6f2b9597f7a76458e557308415ea8228927260","datavalue":{"value":{"amount":"+0.7421919703483582","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":"Q1064320$A4C09D54-E85D-43DF-B6C1-9EC7E7684816","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The recursion-theoretic structure of complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_recursion-theoretic_structure_of_complexity_classes"}}}}}