{"entities":{"Q1264436":{"pageid":1275186,"ns":120,"title":"Item:Q1264436","lastrevid":67154709,"modified":"2026-04-12T15:39:43Z","type":"item","id":"Q1264436","labels":{"en":{"language":"en","value":"An algorithm for solving the factorization problem in permutation groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1204269"}},"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":"Q1264436$C75E96AF-1483-46CA-85D5-F2228F983010","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6be899542f02a8883015a934e323e30b944be4b","datavalue":{"value":{"text":"An algorithm for solving the factorization problem in permutation groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1264436$2A65D9F9-C3B6-4A64-9ED4-823E90E98675","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"607dd23931a6b161901d3b77dc9befc367a48041","datavalue":{"value":"0909.20002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$D9210BC0-DBE5-4199-A232-521193D3A33D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b417796f60ac1d54382eeb6bbc24b839b151d735","datavalue":{"value":{"entity-type":"item","numeric-id":1264422,"id":"Q1264422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264436$94D327A8-3805-4B90-A057-14AE16F25DAC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264436$CDF9A3F9-1E3D-4EB3-9EAF-D476733EDB6C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6de77886165457228ab86330dde78964d550a8e2","datavalue":{"value":{"time":"+1999-01-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":"Q1264436$63A45A24-1068-4285-9E80-2005B25B932E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65acdf7d6d24d09069f1dd42f9efc4f84b673dc7","datavalue":{"value":"A stabilizer chain [\\textit{C. Sims}, Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002)] can be used to express elements of a permutation group as words in (given) generators. The words obtained this way however can be very long. To overcome this problem, the author proposes to compute the transversal elements of the stabilizer chain not (as usually done) by an orbit algorithm, but by systematically computing short words in the generators until elements for all transversal positions have been found.   This yields a larger strong generating set (SGS) whose elements however are short words in the generators. Thus the standard factorization algorithm using this SGS tends to produce shorter words. Such short words can be useful for practical purposes (like the evaluation of homomorphisms [\\textit{C. R. Leedham-Green, C. E. Praeger} and \\textit{L. H. Soicher}, J. Symb. Comput. 12, No. 4/5, 527-532 (1991; Zbl 0789.20001)]) even though they are not the shortest possible.   The author gives explicit algorithms and lists performance times and word lengths for a couple of examples, using his implementation in the computer algebra system GAP. He notes that the main problem of the algorithm is a situation when long words are needed for some transversal positions as happens for \\(S_n=\\langle(1,2),(2,3),(3,4),\\ldots,(n-1,n)\\rangle\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$96E8BCA1-4C17-4A8F-B002-E47185F5F5D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0ac1dafab2cb163643c64b3cf5c7678542cb29be","datavalue":{"value":"20B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$0BC9658E-DDB6-4C8A-8A97-BDCB42516D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$2DDDFBB5-541F-40FE-BE6D-B1CBC7F32F92","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7092edf94fca6f5fe3adf40e43a8d66f50e05566","datavalue":{"value":"1204269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$FC5F1BDF-5161-4A3B-A00C-10F2E446431E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24a5daf034c96e5a0f233cbd1150fb812661091b","datavalue":{"value":"Schreier-Sims method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$3F7014C3-CAEC-4C7E-8B85-0D115546EE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$26841736-34A1-4020-ABFF-BDBF6BA4E88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48056913cba4d6d344d0ae8ace1e3868044bfc6d","datavalue":{"value":"strong generating sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$613B5B62-AA92-45D4-B9D9-56CF98BC0746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e3f7e0d18e9c7e5b9f5b19131aa549a1a707c3","datavalue":{"value":"permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$8A732B9B-3537-4344-9595-338933BEC915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53ae0496261488b8091a5c53187cba8ab59a62d5","datavalue":{"value":"factorizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$4EE8BD61-F221-438D-8BF6-24D5CD753B0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dd25cfb6aa80b782fd82c373e60b5f83ed78839","datavalue":{"value":"short words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1264436$B74F93A5-BD35-4CD7-8A04-B5A531B06096","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d1b22c512cf981f74352b0d894ac3ba97318e0e","datavalue":{"value":{"entity-type":"item","numeric-id":237007,"id":"Q237007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264436$03A4E8C3-474B-4124-8CD2-86B1DCECBA54","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dd7f0abef058f8eae97be2e317c30210cbb29e90","datavalue":{"value":{"entity-type":"item","numeric-id":13081,"id":"Q13081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1264436$63556DFA-1044-486F-9EA3-D0B9B6B6967A","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":"Q1264436$7355F4EE-2C29-43BF-A2B6-2C315613D372","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b4109e263d4a51f22f20f9a0b4cdc4e2aa11391","datavalue":{"value":"https://doi.org/10.1006/jsco.1998.0202","type":"string"},"datatype":"url"},"type":"statement","id":"Q1264436$DA07545C-52BA-4222-9DC5-0C6AC9C13CA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c21c3155b5aa556df4e7579892714c247935ac24","datavalue":{"value":"W1972851637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$ED2A902C-F591-4B30-B689-CBE93E2E5532","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c29d04dccb22ad5b2211694b79d214dab8837f9","datavalue":{"value":"10.1006/JSCO.1998.0202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1264436$BF89B5AB-5002-4F7C-B7E7-95F12489F593","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f3093cbd41eee3958f9f1acf4748dcb9c70d6c5","datavalue":{"value":{"entity-type":"item","numeric-id":3752563,"id":"Q3752563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88bb972d38c890d37634c3913ee3dee4cf1743a1","datavalue":{"value":{"amount":"+0.82488936","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":"Q1264436$58442872-D25A-49F6-B148-36D4E7B8FB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227c89bb957aaf516a74fb9bcfb2cee9e75c9ada","datavalue":{"value":{"entity-type":"item","numeric-id":4020769,"id":"Q4020769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aaebc5cba29e673d63bca1e4eeccfba54f15da4","datavalue":{"value":{"amount":"+0.8191772","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":"Q1264436$C0571A01-76BD-4F41-B5E0-CC94AAFCAA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328c07f1ba38419601793228c2693fc954686916","datavalue":{"value":{"entity-type":"item","numeric-id":4376174,"id":"Q4376174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6ac5e3aad7b1ac16250ec5716c7902d4e12061","datavalue":{"value":{"amount":"+0.81464493","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":"Q1264436$CDC40C13-8579-433E-91A3-CAA33F5331DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f00458f1a35e18c5cb4cccc8abd0e96b864b30f1","datavalue":{"value":{"entity-type":"item","numeric-id":1180408,"id":"Q1180408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3596a384f731f7b0a7e29e9495c57e9f657d12c8","datavalue":{"value":{"amount":"+0.8121887","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":"Q1264436$8BA37208-1BC0-4CBC-8B2A-3CFC9ED8AF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38215f416bbe252fb6d02d3a45e183cb8987f947","datavalue":{"value":{"entity-type":"item","numeric-id":3792860,"id":"Q3792860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72707a69a07eb969daa7998051ac06071f0b1697","datavalue":{"value":{"amount":"+0.8103486","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":"Q1264436$B86A1C84-78F9-4598-B10F-ADD918FC2BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3c0cea31caba9b03c957229ad5f254fd2e73815","datavalue":{"value":{"entity-type":"item","numeric-id":1892223,"id":"Q1892223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55495f168725bffca44be95b9ac87868bfea6598","datavalue":{"value":{"amount":"+0.8011183","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":"Q1264436$A1E97F27-FEA1-43AC-A12E-4961BA2C347E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d973ffdfcf055c6d9b69808aac826752d8176911","datavalue":{"value":{"entity-type":"item","numeric-id":913945,"id":"Q913945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60406e977590e8ed6dfae1f7dfe6956fafd46f62","datavalue":{"value":{"amount":"+0.787853","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":"Q1264436$CD66A53C-12C8-4BD1-8F25-C6755A9FBFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38a58611df1cf1cc8006ce2762d420bbb5b90cce","datavalue":{"value":{"entity-type":"item","numeric-id":2958996,"id":"Q2958996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9bd6afda49c373b953513716335dc45711b8215","datavalue":{"value":{"amount":"+0.78781235","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":"Q1264436$5B913313-3410-414B-8C20-222CB6C984D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1204a959b3e7f52cbf5ecb4b354b394a534e480d","datavalue":{"value":{"entity-type":"item","numeric-id":3338422,"id":"Q3338422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb05fa5df786f9c6264f5d30f8d24bb6c35baf3d","datavalue":{"value":{"amount":"+0.7835524","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":"Q1264436$71119612-6435-47A0-B505-A81DE2E18A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03a9cf4ad10330c24b96295542ee50367ffaaccd","datavalue":{"value":{"entity-type":"item","numeric-id":3810817,"id":"Q3810817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8655af674d30638450ccba176fe6b95340f3225a","datavalue":{"value":{"amount":"+0.7813885","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":"Q1264436$CF695435-3FB1-4F14-B39E-F04BF9DD7071","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for solving the factorization problem in permutation groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_solving_the_factorization_problem_in_permutation_groups"}}}}}