{"entities":{"Q6566725":{"pageid":14177880,"ns":120,"title":"Item:Q6566725","lastrevid":103550822,"modified":"2026-06-06T07:36:02Z","type":"item","id":"Q6566725","labels":{"en":{"language":"en","value":"Groups with context-free Diophantine problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7875711"}},"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":"Q6566725$7047B043-BD6B-4D99-8478-98496E797B1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"698a35b63f158fe1529ca2a60850a6646f4162ab","datavalue":{"value":{"text":"Groups with context-free Diophantine problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6566725$2D482585-A7BC-4321-B9F2-FC41B0D7D288","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"627a6f3ddcfc576ec3c7bdf94b336bc9e08d3ef5","datavalue":{"value":{"entity-type":"item","numeric-id":6359554,"id":"Q6359554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$F89E02BA-A8E0-423A-B712-A66BE4CE79EA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0747c0fb4affe3e597a4fe69d68f3c30f5daa99e","datavalue":{"value":{"entity-type":"item","numeric-id":6566683,"id":"Q6566683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$433028FA-9BB4-4A76-9146-BF21113EA40C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4e5fd9088d0a28713c4508e54b99005eee6af7a","datavalue":{"value":{"time":"+2024-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6566725$47734E09-9550-4144-97B2-7559DF5CAEFA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b7800e012ddc523611c985511ed581ff9aad1fd6","datavalue":{"value":"Let \\(G\\) be a finitely generated group, \\(A\\) be a finite symmetric generating set for \\(G\\) and let \\(X= \\{ x_{1}, x_{1}^{-1}, \\ldots, x_{n}, x_{n}^{-1} \\}\\) be a set of formal variables and their inverses. An \\(n\\)-ary polynomial over \\((G, A)\\) is a word from \\(P_{n}(G,A)= (A\\cup X)^{\\ast}\\). A tuple \\((g_{1},\\ldots,g_{n})\\in G^{n}\\) is a solution of the polynomial \\(\\alpha \\in P_{n}(G,A)\\) if \\(\\iota (\\alpha)(g_{1}, \\ldots ,g_{n})=e\\) for some interpretation \\(\\iota: P_{n}(G,A) \\rightarrow G^{n}\\) of \\(n\\)-ary polynomials. The word problem in \\((G,A)\\) is the formal language \\(\\mathrm{Id}(G,A)=\\{\\alpha \\in P_{0}(G, A) \\mid \\iota(\\alpha)=e\\}\\).\\N\\NIt is well known that \\(\\mathrm{Id}(G,A)\\) is regular if and only if \\(G\\) is finite [\\textit{A. V. Anisimov}, Kibernetika, Kiev 1971, No. 4, 18--24 (1971; Zbl 0241.68034)], \\(\\mathrm{Id}(G,A)\\) is recursively enumerable if and only if \\(G\\) is a subgroup of a finitely presented group [\\textit{G. Higman}, Proc. R. Soc. Lond., Ser. A 262, 455--475 (1961; Zbl 0104.02101)] and \\(\\mathrm{Id}(G, A)\\) is context-free if and only if \\(G\\) is virtually free [\\textit{D. E. Muller} and \\textit{P. E. Schupp}, J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011)].\\N\\NThe \\(n\\)-ary Diophantine problem over \\((G,A)\\) is the language \\(\\mathrm{Eq}_{n}(G,A)\\) of all polynomials from \\(P_{n}(G,A)\\) that have a solution, in particular \\(\\mathrm{Eq}_{0}(G,A)=\\mathrm{Id}(G,A)\\).\\N\\NThe main result of the article under review is the following: \\N\\NTheorem 1.1. Suppose that \\(G\\) is a finitely generated group and \\(A\\) is a finite symmetric generating set for \\(G\\). Then the following statements are equivalent: \\begin{enumerate}\\N\\item The \\(n\\)-ary Diophantine problem is context-free for some \\(n \\geq 1\\); \\N\\item The \\(n\\)-ary Diophantine problem is context-free for all \\(n \\geq 1\\); \\N\\item \\(G\\) is finite.\\N\\end{enumerate}\\N\\NSimilar results are proved (see Section 3) for groups with regular Diophantine problems (they are exactly all finite groups) and for groups with recursively enumerable Diophantine problems (they are exactly all finitely generated subgroups of finitely presented groups).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$62D26A6D-12B1-401F-869C-4FA2DDFD4680","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bfd82087b720927b1a296c318191d7cfc2aac2e","datavalue":{"value":{"entity-type":"item","numeric-id":284097,"id":"Q284097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$23C198BA-E0F3-4619-A56E-901763D7BAB3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$659403D7-4FF7-4FA3-8D47-262DE2D1A14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$E3B42FBE-90BF-48F6-9FC0-668C8B6143E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$85C9B3B5-A964-4039-BA9B-41003B1CB5E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$4ED1054D-3DAF-482B-9CBB-24B00229A498","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9cd29effdc13526fbe0b44d2356e4be1f300a98","datavalue":{"value":"7875711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$118EEC18-3FD0-4D02-81F0-396C338884C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db81a61c54c9022939c42d7d85d9df56c6af0300","datavalue":{"value":"word problem in groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$66643F29-003A-4B97-A06C-D4E7715E39F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7abaea5237d52cfa2f0d2a6d4a348c18981ee34","datavalue":{"value":"Diophantine problem in groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$B4BDC776-2685-4EFE-8D8E-CAB3C296F738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b23838fa1997755a5e8d67b671135eaa04ee6f5","datavalue":{"value":"regular Diophantine problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$5990DA12-AFA3-4E94-9CE7-880A98E6F122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ae9b0269aa2f3ca413ff684e7de5b0d36cb44bc","datavalue":{"value":"recursively enumerable Diophantine problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$F089FC77-2FC6-4B30-AA95-2DF9A5BB2837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7d4836dab67ec6d377d7d3ccdb65a585787ef48","datavalue":{"value":"finitely presented group","type":"string"},"datatype":"string"},"type":"statement","id":"Q6566725$79A2CBD7-1A43-414E-BEA8-86967F570C89","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":"Q6566725$3BD2CB94-946C-4695-8A6D-083751AA9F0C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea830727e9b6bedf20862785e40529682d300fc","datavalue":{"value":{"entity-type":"item","numeric-id":5652216,"id":"Q5652216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$298ADFE4-1E17-4F9C-B3AA-3B450E1922AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83a6823e76c11ef1f853772c882ad2f84a6d8b84","datavalue":{"value":{"entity-type":"item","numeric-id":3292904,"id":"Q3292904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$A30749D0-D997-43E5-B22C-C69451C4774A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e12cc7cecacd2ea7a8aa2a7cba4bdc48ea56b2","datavalue":{"value":{"entity-type":"item","numeric-id":2821818,"id":"Q2821818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$34128B1A-CD76-4820-9B8D-C8BBBD8FA31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3d286431c0a128003d0b282a4b4a096b2390a8","datavalue":{"value":{"entity-type":"item","numeric-id":5091272,"id":"Q5091272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$07B3CD2D-DF98-466A-AD95-8CDDF606616C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47f038f190189729a61fb14e7c25099f135a0c26","datavalue":{"value":{"entity-type":"item","numeric-id":1483698,"id":"Q1483698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$8E53984F-2AF2-446E-A175-31349B58685F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf6692f4afc9013e19766fd0f32edb8e7a9b65f0","datavalue":{"value":{"entity-type":"item","numeric-id":3299596,"id":"Q3299596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$059ACFEC-F15B-455A-8353-E75CB7B085FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86cab98d6d874a4f9230534e6d0d9891c7f1180e","datavalue":{"value":{"entity-type":"item","numeric-id":4598269,"id":"Q4598269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$AB09D8BC-74C9-4611-8520-768ED151E827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320a4959b3b19951cebc6a79a1a4b49c7a726972","datavalue":{"value":{"entity-type":"item","numeric-id":3772406,"id":"Q3772406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$6713E6D3-05BF-4954-8BB3-F7B51F5CF843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee32fd238cd7aa72816d70e40416ef162832c6ee","datavalue":{"value":{"entity-type":"item","numeric-id":3288145,"id":"Q3288145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$1260FE56-7D02-4B83-9551-1BB5D36F359F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af188522ee36dfbc40e8063345c06265fc901ae","datavalue":{"value":{"entity-type":"item","numeric-id":792454,"id":"Q792454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$D83DB87E-8A1F-44B7-BFF9-9D0B0AD64198","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4b6c46f1685eb71baa1c425152bea382ec5973e","datavalue":{"value":"10.46298/JGCC.2021.13.1.7347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6566725$C372EC6D-664E-44FE-ACAD-D2AB55717DDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"449068a18cab74fd5b59feee43e44f25fec5135d","datavalue":{"value":{"entity-type":"item","numeric-id":5711963,"id":"Q5711963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca4d9a5c55ef7e319730a2d592b93ec300fa5687","datavalue":{"value":{"amount":"+0.7783394455909729","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":"Q6566725$6C030602-9F44-4224-A11F-DA7AF5B999CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd998b195bc6a32bd08c71b0a5c7cc7f20c1049c","datavalue":{"value":{"entity-type":"item","numeric-id":2249563,"id":"Q2249563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"643d4c039078face0588c1f86387fc437a224fc3","datavalue":{"value":{"amount":"+0.7739304304122925","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":"Q6566725$ABB728A5-3C6B-4DDB-8472-9BB0E60609A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9089913a0724f1d7bcdc207729fe8261f73fb4fb","datavalue":{"value":{"entity-type":"item","numeric-id":5465986,"id":"Q5465986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d645cf81462eaeed11ae42dec298bf3a6f1c3f62","datavalue":{"value":{"amount":"+0.7669627666473389","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":"Q6566725$388C235A-960E-4A1E-9C1E-9C46D19A6A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdc3e734eb2dd0b5d80d65b9fa915a61a866f954","datavalue":{"value":{"entity-type":"item","numeric-id":3146308,"id":"Q3146308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a75355e460b281a0a79109c9ebbeaa726251908","datavalue":{"value":{"amount":"+0.7667328119277954","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":"Q6566725$2E7E4126-826A-498D-A433-E249DF03C76E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"475ef3ac5f64bc201b890cc1381a2e6d9b130f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3978768,"id":"Q3978768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e0cce7d9fae7697da21fda77e2b3dc69e6f056","datavalue":{"value":{"amount":"+0.7664349675178528","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":"Q6566725$ECB92B86-6520-4200-9438-E16B12263D06","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6566725$B0D52343-15E3-488A-BD9A-679345167AD9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Groups with context-free Diophantine problem (scientific article; zbMATH DE number 7875711)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Groups_with_context-free_Diophantine_problem_(scientific_article;_zbMATH_DE_number_7875711)"}}}}}