{"entities":{"Q1182431":{"pageid":1193180,"ns":120,"title":"Item:Q1182431","lastrevid":66440751,"modified":"2026-04-12T10:05:20Z","type":"item","id":"Q1182431","labels":{"en":{"language":"en","value":"Some effects of Ash-Nerode and other decidability conditions on degree spectra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 31202"}},"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":"Q1182431$8B354137-EFDA-46AF-BEB0-4D6BFB608608","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6997e7edf736d21b5eda1e1f7ae7346bcc3c3ee6","datavalue":{"value":{"text":"Some effects of Ash-Nerode and other decidability conditions on degree spectra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1182431$3ABD306D-C1DA-4FF6-9A03-BA76512AE6BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01d1e5a1fd98e6d5939fc5d9f5cead273cf27354","datavalue":{"value":"0756.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$0222FFAD-6E72-438E-8B8A-494F47E718F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5f9ddea4e240c7cb6ce4cd753a4082011ca72cf1","datavalue":{"value":"10.1016/0168-0072(91)90097-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$FD8E5F8F-5B50-4EE7-85A7-817CFE15A36F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ec221a2b73dcf6fb94011fc6c6f693afff39c1c","datavalue":{"value":{"entity-type":"item","numeric-id":636348,"id":"Q636348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$826FD221-03A9-4D4A-8D7E-4CACAC7B7893","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$8927ECEE-54A8-4CCE-9595-193AE8B380DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1182431$3FA43F4F-E4A9-4EC6-B771-9E6E516B5629","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9f02793618f1441e01cb17c91f129d16f6a0c37","datavalue":{"value":"Many examples in recursive algebra/model theory/combinatorics can be viewed as asking when it is possible to find in the isomorphism type of a recursive model \\(M\\) with a recursive \\((\\Sigma_ n\\), \\(\\pi_ n\\), etc.) relation \\(R\\) a recursive copy of \\(M\\) with the image of \\(R\\) failing to be recursive (resp. \\(\\Sigma_ n\\), \\(\\pi_ n)\\). This question has been extensively studied by Ash, Knight, Moses, Goncharov, Nerode and others. \\textit{C. J. Ash} and \\textit{A. Nerode} [Aspects of effective algebra, Proc. Conf., Monash Univ. 1979, 26-41 (1981; Zbl 0467.03041)] gave syntactic conditions, which, subject to certain decidability conditions, classified when the answer was ``yes'', i.e., when the relation was ``intrinsically recursive''. Here the author contributes to these studies by a partial classification of the degree spectrum of a relation \\(R\\). That is, the collection of degrees that can be realized as the degrees of images of \\(R\\). The author establishes that while it is possible for a recursive nonintrinsically \\(\\Sigma_ 1\\) relation to be a two-element degree spectrum, a nonintrinsically r.e. relation \\(R\\) that satisfies the Ash- Nerode decidability condition has an infinite degree spectrum. The first result is shown to follow from the difficult construction of \\textit{S. S. Goncharov} [Algebra Logika 14, 647-680 (1975; Zbl 0367.02023)] and the second combines an Ash-Nerode construction with a Friedberg-Muchnik one. The author gives a number of examples as to the range of the degree spectrum (particularly in the setting of linear orderings).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182431$F4A95663-45F5-444F-A960-BF3866AB44ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$EFAFD537-F756-4998-9377-899156C31AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$A93C6363-4F53-4CA9-8259-3F38EB9174A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00031bc1c95a0c5e1187a89103d779f10b0942ca","datavalue":{"value":"31202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$734E5969-2F2F-4DEE-BD66-CCAD5A263815","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b11d01f155b9d799c8ffe1fc5e6a1e5d8ab6a63","datavalue":{"value":"recursive model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182431$D7D0147B-8B43-43BF-A43F-C0B4A622F265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3f1533e6eb998645565c910946a01c73aa4eea6","datavalue":{"value":"degree spectrum of a relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182431$57C9DD9A-CAF7-4E92-9E89-B566B005EE7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"984691da0d5181d222896ab91dcd3a072d09f433","datavalue":{"value":"Ash-Nerode decidability condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182431$07ADC0BD-540B-4B71-9685-5A9D219A8445","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8055ef4c08baf7aae068108b5a3771ed10ad54de","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$821F60F7-A467-47F2-A5A6-A7E4D419F442","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":"Q1182431$9E44BB44-918C-4860-A090-8AB980A6CBCB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"482d9ac5092859357d401b489c761bd8d38dcdca","datavalue":{"value":"https://doi.org/10.1016/0168-0072(91)90097-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1182431$C19FC225-520D-47D1-A324-4A955F968002","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19cb5ec969af6f1bdc2b6d34a06bd3a9467b354f","datavalue":{"value":"W1975720205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182431$CE2D1CEF-94B6-48BB-939B-7F36CE681740","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b74f13816a6e3afc695f2afd3830e3fc4ee05fe","datavalue":{"value":{"entity-type":"item","numeric-id":3919698,"id":"Q3919698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$0C7991E8-7618-4E87-B8FE-CC3CB2B0D861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc472c4006d08ec38c269978e89f0714a413eb9c","datavalue":{"value":{"entity-type":"item","numeric-id":1247964,"id":"Q1247964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$AF7B8B3C-5AB2-42AF-9854-F0D9576F8598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f3d3c22d16b59f85df7281ce9f77fe30deb97c4","datavalue":{"value":{"entity-type":"item","numeric-id":1050980,"id":"Q1050980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$67AF0EB8-837B-4475-AE00-B97B28102ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7326762699e9101e0f0b14c3d6655cb2b160cfe","datavalue":{"value":{"entity-type":"item","numeric-id":3931264,"id":"Q3931264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$28ACCAE9-F4D8-46A4-9169-EF7238E65272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"889f3996a3ccc577e577189324c66bf212472b18","datavalue":{"value":{"entity-type":"item","numeric-id":3331204,"id":"Q3331204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$FB08AA3D-A8F7-40DA-AC06-8817CFA843C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3c8cd4690daf1479ca00ef64fa528a05f589c3a","datavalue":{"value":{"entity-type":"item","numeric-id":1182483,"id":"Q1182483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$164BB740-DB9D-46A3-BBB3-322034F9923B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbef6bbbe60bfce0721481461ecfc4b8834e00f9","datavalue":{"value":{"entity-type":"item","numeric-id":5595155,"id":"Q5595155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$06005BE4-B4FE-4C09-A21B-32214FDE6706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76f10b4d88e93baca28a79f2b36e81db13dcb827","datavalue":{"value":{"entity-type":"item","numeric-id":3869329,"id":"Q3869329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$9E5A6C5F-32E3-4FB6-A644-079791177A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182431$DF376F71-F9C8-4BEF-8C07-46C98846F5E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa75d8fd27f0f69d888396c277705b78232b625a","datavalue":{"value":{"entity-type":"item","numeric-id":1595518,"id":"Q1595518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a651f5b862de92dd744a4fb0edc32fb90d2e274","datavalue":{"value":{"amount":"+0.86318874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$C50728F0-1204-4758-8C57-9C4589865AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"925e396a5e579284923c0ab0ef7d4e0b2d35d82e","datavalue":{"value":{"entity-type":"item","numeric-id":2909622,"id":"Q2909622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be98478206abaf9e5af1c69a7a90faa502007a7b","datavalue":{"value":{"amount":"+0.8400694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$226B343F-2C8A-4B73-A033-CA81D8D59577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d965cd3e6431b7db323f3a2057c582a750b467","datavalue":{"value":{"entity-type":"item","numeric-id":1612487,"id":"Q1612487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dcdffc6b2c8501a7533dc000c3519f716842351","datavalue":{"value":{"amount":"+0.83461267","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$085DCEBE-7A55-4E3B-805E-578392B286BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b093c8d8a2fa9b81d8bfb1324e22a164bed00adb","datavalue":{"value":{"entity-type":"item","numeric-id":3701394,"id":"Q3701394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b42bff67fa4813bbe2177445eca2abcfef7ff14","datavalue":{"value":{"amount":"+0.8320571","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$FC99ECAD-AA10-41EC-AB65-779196AEF9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91e0d451ab743ffe8d2817c58c49f4ded9c484e0","datavalue":{"value":{"entity-type":"item","numeric-id":4508282,"id":"Q4508282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caaa0a2e8252803d49139f84e8dc6784a5b4d63e","datavalue":{"value":{"amount":"+0.8305141","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$E094FC36-14D2-4F7C-AFDB-EF10948F4FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efee1c5130ee7ad141a99d61090429128bb24bcd","datavalue":{"value":{"entity-type":"item","numeric-id":3323918,"id":"Q3323918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9df2d94cce7677808c31e66858826a41af8d4b10","datavalue":{"value":{"amount":"+0.8301318","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$A0963F73-B1F0-48BB-AF1A-CA5CEC57519F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3522d99d1e1bd4f90d22c08d7b08d05285a5f7c7","datavalue":{"value":{"entity-type":"item","numeric-id":3487331,"id":"Q3487331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9add04cd2ef6755173fea2fd60494297a142ad8","datavalue":{"value":{"amount":"+0.8275104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$459E8E0A-0E9D-4AF2-9875-E22A55D82723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3ac92668705e15728aec5820789db143895a767","datavalue":{"value":{"entity-type":"item","numeric-id":3446491,"id":"Q3446491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"357eecaeb61d61b8f68c1ef48285ae8e3fe110af","datavalue":{"value":{"amount":"+0.8252257","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$DBA2EC88-5B88-4CF0-AD09-FB66650563C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"773bda0b7eb6c80b103406465b5e50ec62322651","datavalue":{"value":{"entity-type":"item","numeric-id":3650323,"id":"Q3650323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94fc003ca6c416dde76680be8883b3eaa38d8529","datavalue":{"value":{"amount":"+0.8204511","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$4590E5BF-A5E1-4FD0-9C43-9082EC10AE96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d1d1e9b1943b5d33332b382c9c0fed484f8e2f6","datavalue":{"value":{"entity-type":"item","numeric-id":3149990,"id":"Q3149990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9312dad780fafb61126e5e32a6484b6bc0412c39","datavalue":{"value":{"amount":"+0.81953686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182431$B299E86B-5459-4212-8B97-2F3D4A4BD91D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some effects of Ash-Nerode and other decidability conditions on degree spectra","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_effects_of_Ash-Nerode_and_other_decidability_conditions_on_degree_spectra"}}}}}