{"entities":{"Q1073019":{"pageid":1083771,"ns":120,"title":"Item:Q1073019","lastrevid":48913321,"modified":"2026-01-06T04:14:07Z","type":"item","id":"Q1073019","labels":{"en":{"language":"en","value":"Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3943796"}},"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":"Q1073019$362E9DEE-7344-4D1D-88E2-F65EF3F3DA4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20cfb41a32d2ab3541ee7cbc06abb314fea426bd","datavalue":{"value":{"text":"Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1073019$3A7E199B-60D6-42B5-B304-E4CA88A64A15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1432b55bfcac7e7341b651449c691a1521ef1dcc","datavalue":{"value":"0588.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$3F844AE9-2EE7-4350-94DF-17BBEE26B694","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e14a91af6e91f3c565b42dc951ca2e60d9fb399a","datavalue":{"value":"10.1016/0304-3975(84)90018-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$465A2702-6DDE-4983-86CB-3A61C498FCAE","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":"Q1073019$30039038-C714-4A4A-B088-CD86933088FE","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":"Q1073019$9334206E-13AD-46EF-86EE-76D9F7928C28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f55189477af74f356da9c8a88fa159b7bfe6537d","datavalue":{"value":"In this paper we consider wordsequence functions, i.e., functions of the type \\(f:\\Sigma^{*^ r}\\to \\Sigma^{*^ s}\\) where \\(\\Sigma\\) is a finite alphabet and \\(r\\geq 0\\), \\(s>0\\). By starting with finite sets of basic functions and by taking the closure with respect to composition, cylindrification and iteration, we give some characterizations of primitive recursive wordsequence functions. We define some hierarchies of length \\(\\omega^ 2\\) of these functions by bounding the number of successive compositions and the depth of the nested iterations in the definitions of the functions. In such a manner we obtain refinements of the Axt, Grzegorczyk and Meyer and Ritchie generalized hierarchies of length \\(\\omega\\) of primitive recursive wordfunctions defined by \\textit{F. W. von Henke}, \\textit{K. Indermark} and \\textit{K. Weihrauch} [Automata, Languages, Programming, Proc. Symp. Inst. Rech. Informatique Autom. (IRIA), Rocquencourt 1972, 549-561 (1973; Zbl 0357.02035)]. We consider LOOP programs on words [see \\textit{G. Ausiello} and \\textit{M. Moscarini}, Informatik Fachber. 5, 148-163 (1976; Zbl 0352.68035)] by allowing more than one output register, and we prove that the class of functions computed by these programs coincides with the class of primitive recursive wordsequence functions. The hierarchies of functions induce some hierarchies of programs. For the case of functions \\(f:\\Sigma^{*^ r}\\to \\Sigma^*\\), our hierarchies are compared with the Axt et al. generalized hierarchies. We also compare our hierarchies with storage hierarchies, and we analyze the power of the LOOP programs as acceptors. Finally, we state some decidability results for the considered classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$F39681B2-A4F1-4A72-ACBC-5A4B511E9934","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$FB7CC9D2-DEC9-4393-AAEB-C1829E9AAA71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$98BBBDFD-4EA6-4CE7-80C5-F8463CC2E9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$906F7FDA-AC01-4BE2-86AE-194B035F5332","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be8443104a334ae155314b8da0a2920c55ab5d46","datavalue":{"value":"3943796","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$774563EB-2CA3-4238-BDD5-DA6AB078CCD5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d520bd9776e84c4abb9675b525b83e1c7e7e42c","datavalue":{"value":"LOOP programs on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$600EC69C-AE0D-4A53-BC1E-0D341C5DECF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67ffff1c4202d8815cb983bae2942eca04f22ee4","datavalue":{"value":"hierarchies of functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$CDFD6E7A-BB25-44AE-8D10-84B87A748FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bdd5644372f4c2859b484e16403666ba0c8e162","datavalue":{"value":"hierarchies of programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$14F1C8E7-4DAA-4AE0-A956-3C8B0939B0BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac1e440159afc55586ec0789453f86df989af570","datavalue":{"value":"generalized hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$22EB90C6-D23F-457E-9582-406411EA6921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6436accbdcdf560b1729660ed7a8889353ff6a1c","datavalue":{"value":"storage hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073019$CE038B76-3AAF-4CA6-BA72-09FF9A7588E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0285e95138d3f94700a567e14a0d50368e7038f0","datavalue":{"value":{"entity-type":"item","numeric-id":185065,"id":"Q185065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$D2CE2E25-F36D-47BE-90B2-975D830E9EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a375d8768160d412502d42bb68a0091e7125c98e","datavalue":{"value":{"entity-type":"item","numeric-id":483303,"id":"Q483303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$8109ED1B-22AE-4908-BC8C-F0D1AE12916F","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":"Q1073019$56B575CD-6063-446A-92B9-A6A88B8FA803","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"562dbefb08a5b415ae5f658e3d3323209b201ab0","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90018-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1073019$E0E4282C-1582-4BD1-88CA-C1391B6BFC5E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"06d1518313cd53ffc1b7f7d54ae4832c77a3eaf5","datavalue":{"value":"W2025998521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073019$B2F13441-F591-4004-B801-68831A2F1699","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58a4dc729dc3c5f2d6b6c92c0e41fb1c92c91ad5","datavalue":{"value":{"entity-type":"item","numeric-id":3278337,"id":"Q3278337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$58BDE5B2-7460-4749-8435-C544EAFB56B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27550fc8bbf92a8f6dbeebd1151b588c3fa1fab2","datavalue":{"value":{"entity-type":"item","numeric-id":4122773,"id":"Q4122773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$1B7E85D9-A8CE-4197-AF36-0B79A0624C0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf582196222453d3fae33c0997d846fbf49eb34d","datavalue":{"value":{"entity-type":"item","numeric-id":4138161,"id":"Q4138161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$BA800065-BBD5-4DC6-8610-4C8D1A038064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69a897724b52da261ab542d51bea9b95ecc7685b","datavalue":{"value":{"entity-type":"item","numeric-id":5612462,"id":"Q5612462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$CE3E1878-27B1-4E26-ADB3-A212F473D2A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6256dc1d7dd25bcc25b930bb42d4546024bf5eab","datavalue":{"value":{"entity-type":"item","numeric-id":4186306,"id":"Q4186306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$7D458063-2FB8-4AE9-AF1D-8272639C57E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd9bd2279836df3a72d141fc9189e71fe807f7d0","datavalue":{"value":{"entity-type":"item","numeric-id":3960678,"id":"Q3960678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$16BA5EBC-5A34-4BF0-8D95-2635147080C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211f62760e61de04b7ffecc78804e606024ef7df","datavalue":{"value":{"entity-type":"item","numeric-id":4087154,"id":"Q4087154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$29BC0168-F1FD-4903-AB14-78196EB46102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4bdc1028b5bd29b72e5d3773bc059ad70e6d128","datavalue":{"value":{"entity-type":"item","numeric-id":5521476,"id":"Q5521476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$4DBCAB9D-0C3E-402D-8406-6D473454EA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c03d920e4883aa495987d56369e2d61740c26b80","datavalue":{"value":{"entity-type":"item","numeric-id":4741702,"id":"Q4741702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$BD488518-46E0-44B5-A6F5-6BF551F19FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bd4efcb0d8a8b6bab3fa38f4314b2ff1e913145","datavalue":{"value":{"entity-type":"item","numeric-id":3947121,"id":"Q3947121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$0D8C57FD-F77F-41CA-AE0C-7CBB1C6EF2FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2caa5cb602b1bc8d590863e0b1567429d52a30c","datavalue":{"value":{"entity-type":"item","numeric-id":1221752,"id":"Q1221752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$A8A4A72D-BECD-497F-B075-888A9A622A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5b7179be4c35e5d14def99284f11ddf193fca81","datavalue":{"value":{"entity-type":"item","numeric-id":4128546,"id":"Q4128546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$4F42BDDA-A917-4874-8C53-57DF1D9CCA0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4641e81022ea0418a84eb787804d250794e3eacb","datavalue":{"value":{"entity-type":"item","numeric-id":4131620,"id":"Q4131620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073019$48A2AC79-8580-4E9E-9EC3-6A5100D1468A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"324d93e8d7d3415f1bf0bae416ea5273fdb1eb54","datavalue":{"value":{"entity-type":"item","numeric-id":4723716,"id":"Q4723716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6db313a244c60d72922eecbea02c78e4a95048db","datavalue":{"value":{"amount":"+0.8474100232124329","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":"Q1073019$BD9594AA-1405-4193-92C1-F4FBB845D96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ab1378bae05c27de498334e512af87c71bb63a4","datavalue":{"value":{"entity-type":"item","numeric-id":4336703,"id":"Q4336703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef4b585bf162b032b116c796769a44be1d7490c0","datavalue":{"value":{"amount":"+0.7791212797164917","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":"Q1073019$2BB8A778-9E2F-4E46-8C19-1BC71B62ACF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7218391af29b6655894f713db1bb7ad2a517c5c3","datavalue":{"value":{"entity-type":"item","numeric-id":4850553,"id":"Q4850553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23c9accab85c0153c9937d7657181065f9af204d","datavalue":{"value":{"amount":"+0.755706250667572","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":"Q1073019$F9FC05E9-6ABE-49C2-8386-746520E5E2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d724aa170acb7ce8cc953f4242db490deb49c88","datavalue":{"value":{"entity-type":"item","numeric-id":3358724,"id":"Q3358724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23c9accab85c0153c9937d7657181065f9af204d","datavalue":{"value":{"amount":"+0.755706250667572","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":"Q1073019$3F222740-A53C-468D-9355-E3149926EB2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6a472c39e4a07b2d01064c14b19bf526f99325b","datavalue":{"value":{"entity-type":"item","numeric-id":3802613,"id":"Q3802613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c932d20ecae535a1327dc0b923a6ceca977a3df0","datavalue":{"value":{"amount":"+0.7534148693084717","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":"Q1073019$0F0CA5A1-C3CD-4C2C-8A11-6C87AD641E82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1073019","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1073019"}}}}}