{"entities":{"Q1326952":{"pageid":1337702,"ns":120,"title":"Item:Q1326952","lastrevid":70149924,"modified":"2026-04-13T12:46:39Z","type":"item","id":"Q1326952","labels":{"en":{"language":"en","value":"Logic and \\(p\\)-recognizable sets of integers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 589785"}},"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":"Q1326952$7C4C6E39-6309-4F27-ABBD-83932C18C096","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2327d3761a44358d57caa44864b0268c40be9af5","datavalue":{"value":{"text":"Logic and \\(p\\)-recognizable sets of integers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1326952$30127687-D8D1-4798-9D3B-D3FDA3DEDC4D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28cbb24b5c6b76d5baa35e4f442e1d1d32246198","datavalue":{"value":"0804.11024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$EA57798C-523D-4456-9E6E-B990FB18B20A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"99844aba0deee409850cec53537867a00f71d64b","datavalue":{"value":{"entity-type":"item","numeric-id":213200,"id":"Q213200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$FA99D0F1-B71C-46C0-9D6B-A33C1688754E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3994b899c3b70eb5eb85227ae910a470b174035","datavalue":{"value":{"entity-type":"item","numeric-id":804716,"id":"Q804716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$705B25B5-1124-4955-BA5D-911B999C86A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3684a3460666f284ed8323854830b824c056e5e9","datavalue":{"value":{"entity-type":"item","numeric-id":1023051,"id":"Q1023051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$2B98774C-75E6-47BE-933F-1C899DC90616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c186a04078a731a143e84fed0c0fb4e1fa5caa0","datavalue":{"value":{"entity-type":"item","numeric-id":420851,"id":"Q420851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$1F3D34E1-16D9-430F-9953-E8AB4DD4C413","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f16ddc5cdb18d4f4fb3ee6d704d6609c3404ba","datavalue":{"value":{"entity-type":"item","numeric-id":223802,"id":"Q223802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$7F24F7DE-906E-4CBB-866F-70C45FA0EBF3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"17c276cba776869618bd87a010a36eac54c31a8e","datavalue":{"value":{"time":"+1995-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1326952$58A4B345-BEA3-4DE1-BC48-2BAFA5854190","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"71fcbe045d9a673c0eec7e325068ecb67778a317","datavalue":{"value":"https://eudml.org/doc/232407","type":"string"},"datatype":"url"},"type":"statement","id":"Q1326952$D0A8ECCF-0E4A-471F-B9CB-625D14D3615B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7aff8daa1176920f6b2e067aedd582b895032743","datavalue":{"value":"A theorem of \\textit{A. Cobham} [Math. Syst. Theory 3, 186--192 (1969; Zbl 0253.02029)] asserts that if \\(p\\) and \\(q\\) are two multiplicatively independent integers (i.e. \\(\\log p/ \\log q\\) is irrational), then a sequence both \\(p\\)-automatic and \\(q\\)-automatic is necessarily ultimately periodic. The proof given by Cobham is rather intricate and many works have been devoted to simplify it. One of them, due to Semenov, uses arguments from logic to prove a multidimensional version of Cobham's theorem and... is not particularly simple.   In the extremely interesting paper under review the authors give a very general and complete survey on these results (as well as the relationship with algebraic formal power series on a finite field and the Christol, Kamae, Mend\u00e8s France and Rauzy theorem). Furthermore they give and simplify a proof of the Cobham-Semenov theorem, originally due to Muchnik. An essential result is that a sequence is \\(p\\)-automatic if and only if it is (first-order) definable in \\(\\langle \\mathbb{N}, + ,V_p \\rangle\\), where \\(V_p(n) = p^{v_p(n)}\\) and \\(v_p(n)\\) is the largest \\(\\alpha\\) such that \\(p^\\alpha\\) divides \\(n\\) (here \\(p\\) is prime). Note that in the case \\(p=2\\) B\u00fcchi stated the result but used \\(P_2\\) instead of \\(v_2\\) where \\(P_2(x)\\) is the unary relation ``\\(x\\) is a power of 2''. MacNaughton noticed that the proof was wrong and the correct formulation and proof with \\(v_p\\) are due to the first author in her ``M\u00e9moire de fin d'\u00e9tudes'' written in 1985.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$051825BB-F9AE-495E-A292-9B70B9C3AF82","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1d3e055a17ce7fb6036131cf10d782136e2d9314","datavalue":{"value":"11B85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$16C7AFCD-F172-4499-95D8-C9E786E8E977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$B19D33D3-51FE-4BFE-A55E-8590A10D299C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$57FE2DC1-357B-458A-8998-45F77C043B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$79ED113A-67AB-4DCE-A4FE-C96AB01FF176","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5021eabfb11bbed16f05cbc431729d6c1397600e","datavalue":{"value":"589785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326952$0E09BB63-C85E-4351-9EA4-E28AB91C5B04","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91bf40d767c64624931b686e81b905c7b43bef72","datavalue":{"value":"infinite words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$58A0E578-FD07-489E-97B7-FA6252072C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5999504a1ca3002850ad464721891025d91e90d2","datavalue":{"value":"\\(p\\)-recognizable sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$62335FA3-3E0B-4DAF-8983-CCA7870E32B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$9E1C0373-6BDD-4FD3-9943-3B52BC366EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f736d02e86573c887541b685d4ac9ad40d12259b","datavalue":{"value":"first-order definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$F36C869F-CEC7-4A38-965E-7980EB7BDC11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421a43f4b0e8832a026eaa34353c95869f115bee","datavalue":{"value":"survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$643C83C3-56DC-4424-9A17-EA55D9CB9DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3590eb8b47f26c41d61639b5166afe44752133e","datavalue":{"value":"formal power series","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$506EBC41-3207-44C8-9A84-32FB1C6264F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6785e79d6cfe6a520405d67b137337ed5efa6fd3","datavalue":{"value":"Cobham-Semenov theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326952$C749BB96-3466-4254-8AA0-A9CDC41F7F10","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"845abdf0c3e7df8eeaf94dc258fde16321cf5952","datavalue":{"value":{"entity-type":"item","numeric-id":187638,"id":"Q187638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326952$5FD33E37-6EF8-4CDD-A0D4-C59898C62DE9","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":"Q1326952$B733E66F-0EF9-4B14-B1A8-270214F86FCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"314737d1b405a30d519811f6e5be420e919f1b55","datavalue":{"value":{"entity-type":"item","numeric-id":4682402,"id":"Q4682402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8bd15e17ad0568eab4f9a9ea6b5afdb850a70f0","datavalue":{"value":{"amount":"+0.7909904","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":"Q1326952$DC23D3C9-6CA1-4BE3-9AA4-B7C7AB6E83FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e0bd0a2d55017679f5da117219a09a879ba3a4","datavalue":{"value":{"entity-type":"item","numeric-id":3023976,"id":"Q3023976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e70ff4b634c64d11a629ee4b2920a5dbd484dbe","datavalue":{"value":{"amount":"+0.7804119","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":"Q1326952$C612F369-2FAB-4ABC-93BB-1AC6703CE261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1654823de6c14a194637fcace3f0ca533bfb3813","datavalue":{"value":{"entity-type":"item","numeric-id":4427624,"id":"Q4427624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b36475c22354e5e210d940e9629e28fe6ad739b","datavalue":{"value":{"amount":"+0.77585316","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":"Q1326952$AFF87DCC-CC22-4E6E-BD48-3094F7545E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"699fd18f11c2798402281e0045dc96507397644b","datavalue":{"value":{"entity-type":"item","numeric-id":4314601,"id":"Q4314601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bbc6c4553d283ddc168359b69cc0a347e124832","datavalue":{"value":{"amount":"+0.7537079","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":"Q1326952$B28A0F11-F379-47F0-960F-D28E7EE570AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14ada57de05465a32ebc75a17582dc7874d91624","datavalue":{"value":{"entity-type":"item","numeric-id":1311046,"id":"Q1311046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f8bbcf811fcc3f9c74edc457f2aa9f6686711aa","datavalue":{"value":{"amount":"+0.7385093","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":"Q1326952$EFFF7DD7-ECEC-4856-BD9D-E64B815C7E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dba98ce297ee7c04a75830f4bac948d4792ee1f","datavalue":{"value":{"entity-type":"item","numeric-id":3803206,"id":"Q3803206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"340b8b7f848208699a5d267d2b5a176ee7e032da","datavalue":{"value":{"amount":"+0.73663557","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":"Q1326952$7DB06B29-1D48-4DDA-85C6-FF75C0B7880A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5899c60553304bd15734365d61320ed34f78511e","datavalue":{"value":{"entity-type":"item","numeric-id":2244820,"id":"Q2244820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75ccd11fc994a05af2471b77bdd1d7a3525377f9","datavalue":{"value":{"amount":"+0.7362948","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":"Q1326952$C33B2B14-C548-4E3B-A1EC-658BC311948C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0977b767f03b0e1ac11926ce12283aeaf96395a","datavalue":{"value":{"entity-type":"item","numeric-id":2121041,"id":"Q2121041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9441510fe4361013fc399503ce027100c592ba7a","datavalue":{"value":{"amount":"+0.7338956","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":"Q1326952$8F6A9CDD-524D-4291-939B-E6C3840DB547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9088df4e07b903f853962bba22a11b60ff2d78","datavalue":{"value":{"entity-type":"item","numeric-id":3469154,"id":"Q3469154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cd1ff8a969a6e7c6bf32b833a34e0c13de5a23b","datavalue":{"value":{"amount":"+0.7279669","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":"Q1326952$95B209D9-9D75-49CA-A840-8B62BAE0B7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a8326de1224e217cfaddde61d8119d8a95bd260","datavalue":{"value":{"entity-type":"item","numeric-id":3129965,"id":"Q3129965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a16c996c624cf520dcd3fbc3743d8bf2704b369","datavalue":{"value":{"amount":"+0.7246875","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":"Q1326952$E4D6F858-1524-4A64-AB1F-A20D8B6CEA35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Logic and \\(p\\)-recognizable sets of integers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Logic_and_%5C(p%5C)-recognizable_sets_of_integers"}}}}}