{"entities":{"Q716392":{"pageid":718241,"ns":120,"title":"Item:Q716392","lastrevid":63842250,"modified":"2026-04-11T15:55:03Z","type":"item","id":"Q716392","labels":{"en":{"language":"en","value":"A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5882248"}},"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":"Q716392$37B803EF-7820-41A5-B606-96A530E4144E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"05739ab1e156e5c18b4cfe06d0b7e2d8f29bda15","datavalue":{"value":{"text":"A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q716392$75AE8152-EE58-490C-AA25-CB85886E8DE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d60abcf432bce2bfbf109164981893faa8fadb8","datavalue":{"value":"1234.20048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$67E0F826-2FA5-4E8F-A416-DF68180F1684","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2b9e892f1ffa11a66ee26af1e2c8bc1a173eacc","datavalue":{"value":{"entity-type":"item","numeric-id":226831,"id":"Q226831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716392$D174D862-D6B8-43CF-966A-C4B540BB2D70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2b6451ced8faca5a776070094e00eadb4afa93f8","datavalue":{"value":{"time":"+2011-04-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":"Q716392$58C48C4F-17B6-43CA-93D2-69696FC04677","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40c3d6d11fc5705834465d94b4221ab334dcc6d2","datavalue":{"value":"https://arxiv.org/abs/0903.0216","type":"string"},"datatype":"url"},"type":"statement","id":"Q716392$8FCAE55B-1081-48A0-ADDF-883E55885ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"93ef4c43a6948008a9e61dc55f12ebd1dc599473","datavalue":{"value":"https://projecteuclid.org/euclid.ijm/1299679740","type":"string"},"datatype":"url"},"type":"statement","id":"Q716392$0706C146-8C8B-4A79-8986-A1E2801153D1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3fdaf70d9845a910e9764654d114c179de075963","datavalue":{"value":"Recently \\textit{A. Myasnikov, V. Roman'kov, A. Ushakov} and \\textit{A. Vershik} [Trans. Am. Math. Soc. 362, No. 9, 4655-4682 (2010; Zbl 1207.20026)] proved that for free metabelian groups with standard generating sets, the following `bounded geodesic problem' is NP-complete: given a word in the generators and an integer \\(k\\), decide whether the geodesic length of the word is less than \\(k\\). The author and \\textit{A. Rechnitzer} [Groups Complex. Cryptol. 2, No. 2, 223-229 (2010; Zbl 1222.20023)] show that this problem is equivalent to the `geodesic problem' (find for a word a geodesic word representing the same element) and simultaneously to the `length geodesic problem' (find for a word its geodesic length).   A deterministic algorithm is given which takes as input a word of length \\(n\\) in the generators in the Baumslag-Solitar group \\(B(1,p)=\\langle a,t\\mid tat^{-1}=a^p\\rangle\\) for any integer \\(p\\geq 2\\), and outputs a geodesic word representing the same element, in time \\(O(n)\\). Consequently, the three problems mentioned above are solvable in linear time.   Recent work of \\textit{V. Diekert} and \\textit{J. Laun} [Int. J. Algebra Comput. 21, No. 1-2, 119-145 (2011; Zbl 1235.20041)] extends the result of this paper to groups of the form \\(\\langle a,t\\mid ta^pt^{-1}=a^q\\rangle\\) when \\(p\\) divides \\(q\\). Their algorithm runs in quadratic time, but in the case \\(p=1\\) the time reduces to linear, although their algorithm is qualitatively different.","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$9381759C-2F4D-4E92-A43A-5F15CF48EFF6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"639e35a4d8066ba3b320b7c5998ad4d73a0cf431","datavalue":{"value":"20F65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$F53229B4-CAE5-4FAC-81A5-6693B5B478A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$2DC73CF9-88F4-4DE0-B0C6-D931ABF31129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$50C78966-4382-4C19-B86D-7794CD679E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1a9473403ba5aadfa1076dd6525b25a3172ff28b","datavalue":{"value":"20F16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$1AED4C38-0F19-483E-AE76-FCA4602E2EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$25782385-E9EE-4370-AFF3-AAD742771D4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f7aa1b2dd7063ad6f153ccf32cee15ca48e3911","datavalue":{"value":"5882248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716392$9C283CD4-C4D6-4A4D-9F82-FCB824316BF8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9d6a69d4f52fefcd1a1fe065ca69518a1f73256","datavalue":{"value":"geodesic problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$4DA0E391-44B2-4B2E-AA7B-B61A88811B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dd102ffd1d7fa8867b9b7cba996a8fc147ee16b","datavalue":{"value":"Baumslag-Solitar groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$6A51C7D4-3B73-49FF-8F89-E0C46802849C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2fabb4d1521f8c12f5dbed2f4ee1b32f73b653","datavalue":{"value":"metabelian groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$CA8B5991-138A-4F7C-96B9-4149A2AF7721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$E2A8D526-6760-48EA-A862-8504C502E6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$6886A371-09B7-4329-8E47-5D515CD03018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ceb535f23f8c9bd3e37e171067fb430af011773e","datavalue":{"value":"geodesic lengths","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$D171AB9E-D7E5-402D-8930-EA43DA619362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bf0882370430827bf0ad95308baea9eb0d81fc7","datavalue":{"value":"deterministic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q716392$8C4D401B-9DE7-4438-958D-8DF567A59131","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"70ab787c9073b134ad5dbc9157f7bc83a250ba96","datavalue":{"value":{"entity-type":"item","numeric-id":1863082,"id":"Q1863082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716392$CCF103CF-CB13-47B8-B0FE-7B82F1940EF1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c75e46d52756574cc2c3b6666627a330102767ca","datavalue":{"value":{"entity-type":"item","numeric-id":338846,"id":"Q338846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716392$AEC6EED1-725E-483B-BD70-56843E447FB3","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":"Q716392$968C214D-7E55-4239-BC24-E2ED38BB870D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f8a0d5044f41e77cd6db9554e6b6bc3a4eb8b21","datavalue":{"value":{"entity-type":"item","numeric-id":2996841,"id":"Q2996841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"504ba501fe070450ad08284e7b9fcf2af9bd6a4b","datavalue":{"value":{"amount":"+0.8332598209381104","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":"Q716392$266B0BA5-D12E-4268-8225-7033C2AF96B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a162d8f169e5df7928937eb0e87d9b96100f3d93","datavalue":{"value":{"entity-type":"item","numeric-id":2975255,"id":"Q2975255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5271d11c7aa66b179f34231a8938902e55c6e9e6","datavalue":{"value":{"amount":"+0.8029393553733826","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":"Q716392$603B86D5-D3D3-4B22-9452-58612ABED099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12cce627a629d2e5eadd1608a58484c19ad8968b","datavalue":{"value":{"entity-type":"item","numeric-id":3085995,"id":"Q3085995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21ac743feebd27cd9bd13f00405de9e25da25e2b","datavalue":{"value":{"amount":"+0.7959042191505432","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":"Q716392$E878ECE2-49C1-458A-866F-BCA91A620D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2099ea4bdd9a65e53e3cb945fe8f86504d6971f3","datavalue":{"value":{"entity-type":"item","numeric-id":4930015,"id":"Q4930015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91907fd5518e52184879b273e73bdac825118b29","datavalue":{"value":{"amount":"+0.7901278138160706","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":"Q716392$A786CE1D-9526-4FBE-9450-29965B5EC2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34dbaf9d50ca331a3caba354dc8878b2a03251f1","datavalue":{"value":{"entity-type":"item","numeric-id":2114372,"id":"Q2114372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329be8ad673fc994908f2f42d22a88379eb1ad50","datavalue":{"value":{"amount":"+0.7857277989387512","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":"Q716392$D72607E9-9664-40BB-8A98-4681CB7CE79B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear-time_algorithm_to_compute_geodesics_in_solvable_Baumslag-Solitar_groups."}}}}}