{"entities":{"Q1433428":{"pageid":1444168,"ns":120,"title":"Item:Q1433428","lastrevid":67465416,"modified":"2026-04-12T18:08:01Z","type":"item","id":"Q1433428","labels":{"en":{"language":"en","value":"On the definition of word hyperbolic groups."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2075743"}},"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":"Q1433428$39721801-C632-40ED-94EB-14BE70020645","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1a8d8ec47861ef51f9de36038c82c5bb4b053e0","datavalue":{"value":{"text":"On the definition of word hyperbolic groups.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1433428$0DDDDCD7-8909-4C98-831B-407764E04AF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"875f3886513ce288940eea6dac3505cdecf71fde","datavalue":{"value":"1047.20033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$D98159D3-1811-4756-9232-37D8C9F6CFCB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7627f4908297400f6329af6473fefd47ad5d0942","datavalue":{"value":{"entity-type":"item","numeric-id":435935,"id":"Q435935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1433428$31C387B8-E7E7-4E66-A26F-67A57282022D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dfa5bc95e1fdba4c3d3197123373583ef39a5b9e","datavalue":{"value":{"entity-type":"item","numeric-id":163114,"id":"Q163114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1433428$AB95A98C-438A-48F6-ACF9-28AD88635238","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"afbd44facac840595b2b87499dc027fedd0c6b2d","datavalue":{"value":{"time":"+2004-06-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1433428$635D2E3A-39FC-4345-B665-E39E19E2AC48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"35c9b5e7095c999e8e48257d1ed442a615c5eac0","datavalue":{"value":"https://arxiv.org/abs/math/0010123","type":"string"},"datatype":"url"},"type":"statement","id":"Q1433428$8DB61F8D-CD6C-4577-891D-1C4FFDB3B17D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d6693b3f896f40f6525c134c69392f1e962f60e3","datavalue":{"value":"Let \\(G\\) be a finitely generated group, \\(\\Sigma\\) be a finite alphabet, \\(\\#\\) a letter not in \\(\\Sigma\\), \\(\\Sigma_\\#=\\Sigma\\cup\\{\\#\\}\\), and \\(\\Sigma^*\\) be the free monoid over \\(\\Sigma\\). In addition \\(\\Sigma_\\varepsilon=\\Sigma\\cup\\{\\varepsilon\\}\\subset \\Sigma^*\\) where \\(\\varepsilon\\) stands for the empty word. The alphabet \\(\\Sigma\\) has formal inverses if it admits a permutation \\(a\\to a^{-1}\\) with orbits of length two. Formal inverses on \\(\\Sigma\\) extend to formal inverses on \\(\\Sigma^*\\) by means of the rule \\((wv)^{-1}=v^{-1}w^{-1}\\). A formal language is a subset of a free monoid \\(\\Sigma^*\\) over a finite alphabet \\(\\Sigma\\). The connection between a group \\(G\\) and languages over \\(\\Sigma\\) is made by means of a surjective monoid homomorphism \\(\\Sigma^*\\to G\\) which maps \\(w\\in\\Sigma^*\\) to \\(\\overline w\\in G\\). A choice of generators for \\(G\\) consists of a finite alphabet \\(\\Sigma\\) equipped with formal inverses together with a surjective monoid homomorphism \\(\\Sigma^*\\to G\\) which maps \\(w^{-1}\\) to \\(\\overline w^{-1}\\). Any choice of generators \\(\\Sigma^*\\to G\\) is extended to \\(\\Sigma_\\#^*\\to G\\) via \\(\\overline\\#=1\\).   The main results of the paper under review are the following. Theorem 1. Let \\(\\Sigma^*\\to G\\) be a choice of generators for the group \\(G\\). \\(G\\) is word-hyperbolic if and only if for some regular combing \\(R\\subset\\Sigma^*\\), then the language \\(M=\\{u\\#v\\#w\\mid u,v,w \\in R,\\;\\overline{uvw}=1\\}\\) is context-free.   For any combing \\(R\\), \\(M=\\{u\\#v\\#w\\mid u,v,w \\in R,\\;\\overline{uvw}=1\\}\\) is called the multiplication table determined by \\(R\\).   Theorem 2 is a variation on the main result of \\textit{D. E. Muller} and \\textit{P. E. Schupp} [J. Comput. Syst. Sci. 26, 295-310 (1983; Zbl 0537.20011)]. Theorem 2. Let \\(\\Sigma^*\\to G\\) be a choice of generators and \\(M\\) the multiplication table corresponding to the combing \\(R=\\Sigma^*\\). (1) \\(G\\) is finite if and only if \\(M\\) is a regular language. (2) \\(G\\) is virtually free if and only if \\(M\\) is context-free.   The column of \\(g\\in G\\) is \\(C(g)=\\{u\\#w\\mid u,w\\in R,\\;\\overline ug\\overline w=1\\}\\). Columns are related to the comparator automata used in the definition of automatic groups. Suppose \\(G\\) is automatic with respect to the combing used to define \\(M\\), and \\(a\\in\\Sigma_\\varepsilon\\). The binary relation accepted by the comparator automaton for \\(a\\) is \\(\\{(u,w)\\mid u,w\\in R,\\;\\overline ua=\\overline w\\}\\) while \\(C(\\overline a)=\\{u\\#w\\mid u,w \\in R,\\;\\overline{uaw}=1\\} \\).   Theorem 3. Let \\(\\Sigma^*\\to G\\) be a choice of generators. There exists a combing \\(R\\subset\\Sigma^*\\) such that \\(C(\\overline a)\\) is context-free for all \\(a\\in \\Sigma_\\varepsilon\\) if and only if \\(G\\) is asynchronously automatic with respect to a combing contained in \\(\\Sigma^*\\) and closed under taking formal inverses.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$126622AC-2317-4BBF-B713-F0A15633D63D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebb96cb004791185508e9f447d258889ef519c78","datavalue":{"value":{"entity-type":"item","numeric-id":193089,"id":"Q193089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1433428$33AB5D93-3428-42D6-B5BE-EEEB0D3BE476","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d746b8d92c753ec921d8d5d21d7a353ee19cc6b6","datavalue":{"value":"20F67","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$FE69D6AB-215A-49A6-9C50-4614311A57C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$6A4DAA49-7D75-49F6-B4AE-839B468A29AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$AC632B1E-FB42-4971-8E93-B6773587F6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$D889609A-D062-4451-AC3A-495D63AB3ABF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88197a10930bd7b0194fa22f82474a5e1e343eff","datavalue":{"value":"2075743","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$5CE73CCB-CBC3-45CE-A19A-190DD195F934","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d39cd3b62b30b19521a29630b9d18e5f8d7a97f9","datavalue":{"value":"word hyperbolic groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$2EF85D74-D2A4-416D-841D-A9069C1AF51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542470d6f63fefcd2ae937cc78d1c833a1db112c","datavalue":{"value":"finitely generated groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$DD1E2ECB-2FD6-4D10-B0F6-133FAAC0ED49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$6B4F742D-6BCB-4DAC-80BF-A66DD8E1EAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f2b7c70e8e9c8864adc67f9ec63fe09eb15f44a","datavalue":{"value":"multiplication tables","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$DC269FAA-BC95-4FFD-9FE1-95EB69EF1AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8af76bfbe81b16541cca3b1ddbd068d9d6b8d69f","datavalue":{"value":"normal forms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$C8DCF825-DEA5-44D9-8906-E73ABE1882A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b241c2e53ac9c4073e4f6a37f6442b7c79d7d","datavalue":{"value":"free monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$64FC901C-2A8F-41B5-8488-F4004C03C0C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d227622b114a413a6dfa603588e4cba8547f643","datavalue":{"value":"automatic groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1433428$048CF4DC-D895-4C75-BB4C-AB18D562E10A","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":"Q1433428$34E9462C-B917-4803-9661-02C1CBF4EF1D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5796e5dc4ed74eb73865f0f962b4de3c4f76cb4","datavalue":{"value":"W2028001482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$09499F2F-8EDB-4607-909B-228567DE5B02","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ccfdacf4d37037f8b09bae94bd9339843c09a4f6","datavalue":{"value":"10.1007/S002090100356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1433428$5B8238E6-4F87-4A20-AA64-A01474B31DDE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bf9e852d29e9c1a31a3b9e504ee7a41b6cca781","datavalue":{"value":{"entity-type":"item","numeric-id":4786246,"id":"Q4786246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ae3ec84c4a69e4e8eae4660c34e45f181f37eab","datavalue":{"value":{"amount":"+0.8375470638275146","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":"Q1433428$6A592FB2-FCF8-4027-8A88-2AC670D2C2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fda041dfc1b063ee8ca1e3ca0c94f3ceac964a94","datavalue":{"value":{"entity-type":"item","numeric-id":4819118,"id":"Q4819118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aaa77d803dded5bad262c42b2d4c8d8ac35292e","datavalue":{"value":{"amount":"+0.8203661441802979","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":"Q1433428$53545C73-428A-427A-AA2F-88805AF94905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ec6b28be7baef3eb2648d5463b0548d8b287f15","datavalue":{"value":{"entity-type":"item","numeric-id":5702490,"id":"Q5702490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0af99a96bdd1e2cef80a84c6cdab062768221537","datavalue":{"value":{"amount":"+0.8143097162246704","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":"Q1433428$23667677-958B-43E7-886B-81ED3C67183C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"359c1a032507f583dec9180b9f5bcd9e3b3c120a","datavalue":{"value":{"entity-type":"item","numeric-id":1422174,"id":"Q1422174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5286ec50a40e6ac41c1d9220d9ed140afb01c8a9","datavalue":{"value":{"amount":"+0.8084537386894226","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":"Q1433428$0B81552F-F271-4AF7-A8A2-844B82DE2F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72ab73ce6c74b4df4915c2d7af475a1ab6a31945","datavalue":{"value":{"entity-type":"item","numeric-id":596085,"id":"Q596085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c70eb62f7ac9f2403714967de57f3c744a43eb65","datavalue":{"value":{"amount":"+0.8040305972099304","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":"Q1433428$D36141A3-AE84-4615-A824-E07E0D3EB8A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the definition of word hyperbolic groups.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_definition_of_word_hyperbolic_groups."}}}}}