{"entities":{"Q1898479":{"pageid":1909221,"ns":120,"title":"Item:Q1898479","lastrevid":71730483,"modified":"2026-04-14T00:10:20Z","type":"item","id":"Q1898479","labels":{"en":{"language":"en","value":"Recursion theoretic properties of frequency computation and bounded queries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 797319"}},"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":"Q1898479$9B556600-B790-4BDF-BD10-FC5F6F4433C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"401c1c25a3203612a02b02e5e935c4e8c57dae55","datavalue":{"value":{"text":"Recursion theoretic properties of frequency computation and bounded queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898479$4560DB92-3BE3-4308-8429-5EC9CA77EEEF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1af96ce2113edde838d34eb126df0062ddf96bc3","datavalue":{"value":"0836.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$342C3C89-1E1C-4414-8E11-6AB201F4555B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26c4cd22843016572b2c49bdfd7bf76a192b6c2a","datavalue":{"value":{"entity-type":"item","numeric-id":960465,"id":"Q960465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898479$2EFF6AF0-6378-47CF-9380-B0A9DF40ECD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a56bc7b07f95b5885e3133c205b9456af5cfa030","datavalue":{"value":{"entity-type":"item","numeric-id":324251,"id":"Q324251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898479$6E2745CB-03AB-4F36-82C1-C59C53E6E94B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898479$B2C62CD7-0E9C-47D2-B9E0-56F5917A0009","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9e1e5c28e67547367d3e71e19f3b7e287b30c62","datavalue":{"value":{"time":"+1995-10-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898479$A269DCFE-8FA5-4D8A-B1FB-7CCDC05E91CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"73a99f335673147d2812f8e13117d7192abda2c1","datavalue":{"value":"A set \\(A\\) is called \\((m,n)\\)-recursive (in short \\(A \\in \\Omega (m,n))\\) if there is a recursive function \\(f : \\omega^n \\to \\{0,1\\}^n\\) such that for all pairwise distinct numbers \\(x_1, x_2, \\dots, x_n\\),  \\[ f(x_1, x_2, \\dots, x_n) = (b_1, b_2, \\dots, b_n) \\Rightarrow \\biggl |\\bigl \\{i : \\chi_A (x_i) = b_i \\bigr\\} \\biggr |\\geq m. \\]  \\(A\\) is strongly \\((m,n)\\)-verbose (in short \\(A \\in V_s (m,n))\\) if there is a recursive function \\(f\\) such that for all \\(x_1, x_2, \\dots, x_n\\),  \\[ |D_{f (x_1, x_2, \\dots, x_n)} |\\leq m \\;\\&\\;\\bigl \\langle \\chi_A (x_1), \\chi_A (x_2), \\dots, \\chi_A (x_n) \\bigr \\rangle \\in D_{f (x_1, x_2, \\dots, x_n)}, \\]  where \\(D_i\\) is the \\(i\\)-th finite set in a canonical indexing of all finite sets. It is not difficult to see that \\(\\bigcup_{n \\geq 1, 1 \\leq m \\leq n} \\Omega (m,n) = \\bigcup_{n \\geq 1, m < 2^n} V_s (m,n)\\). This class is denoted by \\(\\Omega\\). The inclusion relations among the \\(V_s (m,n)\\)-classes and \\(\\Omega (m,n)\\)-classes have been discussed by \\textit{R. Beigel} and the authors [Inf. Comput. 118, No. 1, 73-90 (1995; Zbl 0827.68082)], \\textit{A. M. D\u00ebgtev} [Algebraic systems, Interuniv. Collect. Sci. Works, Ivanovo 1981, 88-99 (1981; Zbl 0536.03022)] and the authors [``Some aspects of frequency computation'', Techn. Rep. Nr. 21/91, Fak. Informatik, Univ. Karlsruhe].   This paper discusses widely the recursion-theoretic properties of the class \\(\\Omega\\). In particular, it is shown how well-known properties of r.e. sets as simplicity and completeness are related to frequency computation and verboseness. For example, it is shown that: There is a simple non-hypersimple set \\(A\\) which is in \\(\\Omega (n,2n + 1) \\cap V_s (1 + (n (n + 1)/2), n)\\) (Theorem 4.3); If \\(A\\) is simple and \\(A \\in V_s ((n(n + 1)/2), n)\\) for some \\(n > 0\\), then \\(A\\) is hypersimple but not hyperhypersimple (Theorem 4.7); The sets in \\(\\Omega\\) cannot be \\(m\\)- complete (Fact 5.1), btt-complete (Theorem 5.2) or \\(d\\)-complete (Theorem 5.3); There is no \\(c\\)-complete set in \\(\\Omega (n,2n)\\) or \\(V_s (n(n + 1)/2, n)\\) (Theorem 5.4); But there is a \\(c\\)-complete set in \\(\\Omega (2,2n + 1) \\cap V_s (1 + (n(n + 1)/2), n)\\) for all \\(n > 0\\) (Theorem 5.5); etc. A comprehensive summary about the related known results is also given at the end of the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898479$905733FA-9262-499F-BCF3-0D82DD97C262","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$5646C674-9C8B-4AE1-9A3E-897F3793A284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$33A1D000-4E09-4E52-8D4D-D74720828E44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bcf6f89ade16634d732b44eb13b8bfff810ab93f","datavalue":{"value":"797319","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$D28D3CB2-0B1E-4354-9026-BCA79F3B4D86","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"439c5a77983c22a007b7d189aa53114bd1131f8e","datavalue":{"value":"\\((m,n)\\)-recursive set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898479$E1A1EBBF-FF29-42D6-B6AB-4C89A6BDAACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0177ef03ec6c0bafc2fc0a879fa3a3b75f0cf27","datavalue":{"value":"frequency computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898479$3821DB4E-FEA4-4FAB-8B57-3975D6B247D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b23780ad6f7e23738af99b2af66b38b7e62a7d4","datavalue":{"value":"verboseness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898479$CA06EB67-4B83-472D-8414-B0133828C57D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dbc008852b7f12e01f50414af435612153cc55c4","datavalue":{"value":{"entity-type":"item","numeric-id":162063,"id":"Q162063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898479$6C3E1D7A-1867-4AE1-9F0C-05993B58BA28","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":"Q1898479$B20FC96E-7E24-4C5E-90A4-9442704DE55A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ca2f48d32700fbaf8372eb4377f4418dd1b32bff","datavalue":{"value":"https://doi.org/10.1006/inco.1995.1099","type":"string"},"datatype":"url"},"type":"statement","id":"Q1898479$00A54C8C-6DE8-4965-87D3-910BF098A321","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b48e4f4cd27996e5949e18d90fbd53fb34c26c30","datavalue":{"value":"W1989212933","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$19544089-C0BA-4F76-B026-566C349BB25F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7f08f008589caaf758b7504dbd8bf3b45b1b80d","datavalue":{"value":"10.1006/INCO.1995.1099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898479$A2C7076F-3E03-4DF9-BC23-5D3F4B6CE12C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a08a265ebbdb3b1b6dad75048e156a8784bea5d1","datavalue":{"value":{"entity-type":"item","numeric-id":4282611,"id":"Q4282611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef5c0f0eebe4859b7b1818af0e7f9ed154732a49","datavalue":{"value":{"amount":"+0.8596194","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$250C95F5-9F0E-4322-95D2-2E2CA1F86D77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cab42cce03b3d45b09788d53b56fb23aaa749ff1","datavalue":{"value":{"entity-type":"item","numeric-id":1407552,"id":"Q1407552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"292600d19fe37057e8055ff48af9763ace6c95a9","datavalue":{"value":{"amount":"+0.68281466","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$28728DA9-931C-4C4B-801F-23F4DCE54C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51d455493c17ac3e12a404ef399c1f86ede70f66","datavalue":{"value":{"entity-type":"item","numeric-id":4704651,"id":"Q4704651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f24f878ecc156c56754e6495b2b6e3aca01ad153","datavalue":{"value":{"amount":"+0.67655873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$F1D4040F-C634-4CA2-ABE0-BA54651A8673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c5ce4d315d3dd8963d07993c20ac8bb532257a2","datavalue":{"value":{"entity-type":"item","numeric-id":3734387,"id":"Q3734387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0a43c12371cabd3d71faae4bfe4511ce58a0982","datavalue":{"value":{"amount":"+0.6758213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$268C43D6-8991-4E47-84C8-4AD19027D812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d5f5c6284fafbde4777cee1b2c208cef154fba9","datavalue":{"value":{"entity-type":"item","numeric-id":3715103,"id":"Q3715103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc4e195b04d5e2410ce42376560341fe64f6bb94","datavalue":{"value":{"amount":"+0.674565","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$4765058E-2376-4976-B710-4315F423A48C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb31f8a8e053006f19a9aa57c2aea33fe8641933","datavalue":{"value":{"entity-type":"item","numeric-id":4205434,"id":"Q4205434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ac28bb2620afaa5526a992dbaa0273464ef8180","datavalue":{"value":{"amount":"+0.6704001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$D9CC1D86-103D-4731-9C2C-D92679248C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b16efa721a9b849da65dede4671f00a4dc08283d","datavalue":{"value":{"entity-type":"item","numeric-id":3220577,"id":"Q3220577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6851538e60c6aefc8fd8e601b348df555312abd6","datavalue":{"value":{"amount":"+0.66818213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$8AB97018-C908-446D-9625-7EBC7E502AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e56cc276cc928c3a43d55987918919264ee506d3","datavalue":{"value":{"entity-type":"item","numeric-id":3491535,"id":"Q3491535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"425d3558d8f7063621e79e08bbd0bca9ee3ee8da","datavalue":{"value":{"amount":"+0.66726553","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$89468D7F-FF24-4838-9328-3DE070123909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58942427cc7ca209c5904295046394b4a6c86696","datavalue":{"value":{"entity-type":"item","numeric-id":3480024,"id":"Q3480024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd16359f4e3bb662377f4ae5f68f93112bd09915","datavalue":{"value":{"amount":"+0.6659449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898479$676F6392-27C0-432D-856A-91B5C3EE969A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recursion theoretic properties of frequency computation and bounded queries","badges":[]}}}}}