{"entities":{"Q1090414":{"pageid":1101166,"ns":120,"title":"Item:Q1090414","lastrevid":49069774,"modified":"2026-01-06T13:30:42Z","type":"item","id":"Q1090414","labels":{"en":{"language":"en","value":"Computing short generator sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4006523"}},"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":"Q1090414$71453F79-05A1-45D1-820A-77CC7927975F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"756580977b436dff884fc4bcd94fec5c798f229b","datavalue":{"value":{"text":"Computing short generator sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090414$07E2D3D1-5FE8-40B4-9D5D-2E7DE2258905","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b1d9caf03c803ccbb9951906cc534b4f7b28238","datavalue":{"value":"0621.20016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$EE4F2A83-EBA4-45E6-8BF2-F9CB6B340B27","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2af07b72fc372ee522175f1ab1a18a5f43cfbe14","datavalue":{"value":"10.1016/0890-5401(87)90043-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$92330F51-601F-4732-86E1-2C7B3512B2D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d92f5d1cb083ab02204e0e0096060eb69f74ef88","datavalue":{"value":{"entity-type":"item","numeric-id":1090413,"id":"Q1090413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$EE3A9C07-748E-4405-8AA5-04F29391B032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7900dc37bcd45aeae85ec8ad08bdaad274265cfc","datavalue":{"value":{"entity-type":"item","numeric-id":1330933,"id":"Q1330933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$8C8664C4-C619-45CC-8C2A-50E4052E83C5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$85B6018C-5632-42C8-AB05-D499F9BC57C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1090414$BF2634D3-EB0E-4158-BD1F-A6E9BC618887","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8527c9d80d80441eac0860173b682a2bae31c413","datavalue":{"value":"Let P be a finite set of permutations of n letters. The diameter of the permutation group \\(G=<P>\\) (with respect to P) is by definition the least integer k such that every permutation in G can be expressed as a product of at most k elements of P. This concept corresponds to the diameter of the Cayley graph associated to the given presentation of G.    It is shown in the paper that the diameter of a permutation group G generated by a set P of cycles of bounded degree is \\(O(n^ 2)\\). This bound is best possible. In addition, it is shown that such short products can be found in polynomial time. The techniques presented in the paper may be applied to various well known permutation-group puzzles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$BCD50C88-091E-478A-A41B-8B663D89503F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$E9A2F5B6-2AC0-44B1-8A2E-2A2924E5D8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$A018181A-A67A-4E6F-89E6-071909406CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$3AB42782-529F-4EC6-83FC-16BA2E3BA54C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$B8786228-897A-4FA7-9EE6-D9175224E57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99162f665c9ec138d28e4bea8a477540421995b7","datavalue":{"value":"20B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$59C3112A-9015-479A-A63B-245566205963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$E01A37C1-A357-4EE7-90FF-F2905568FF56","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b51228bad18ee79c06c5c6cbb275746fdbb33563","datavalue":{"value":"4006523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$C21E6BC7-95F0-47E6-B778-B681C805E5BA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25a0d0a64145a26d41eb5308b1cb512dc20d7b36","datavalue":{"value":"computer algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$F669F54A-304C-4AEF-B040-47EA08ABC9A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$7BCD16C4-4C19-4E10-8917-55035342B458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c6cfb226154f07734dc1735b4277bef8a152f36","datavalue":{"value":"finite set of permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$B2A9AB80-9E26-4357-B9F0-26830C2D72F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a7cfb72b6a68a3ef50278476763814a39fedd50","datavalue":{"value":"diameter of the permutation group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$68511079-4BD9-4B80-A1D4-7E3F37DF7C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f046045effe4d96bd7d28b79a6e3ca55890681","datavalue":{"value":"Cayley graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$C7C22A54-434A-484A-8632-823367491D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e986f205a53c956ce83852b88693f1f1cb56e42c","datavalue":{"value":"presentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090414$06CDE1C0-BC19-4013-B61F-F0ED778E2FCB","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":"Q1090414$F7CDB2EF-1D40-4122-A201-0F85951DE0CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"710b66de59becafd4a26e6dd5d6a8e585c8296af","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90043-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090414$966CC220-40CB-4A1F-B8A1-45188917BD46","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05140d9b1159998009c6c41d6ac96a47473b0ee4","datavalue":{"value":"W2032908207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090414$F6A4A82C-6589-49E4-A80C-B8A771630E62","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f949f13e1712b62b2dca0010c2a3997b4691a24a","datavalue":{"value":{"entity-type":"item","numeric-id":3920644,"id":"Q3920644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$A8783101-7D30-497E-A763-0D66C4613328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5989e7b642a281e076cb0a5451b4d9c25f50f39c","datavalue":{"value":{"entity-type":"item","numeric-id":3253828,"id":"Q3253828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$38B4AFA2-CE53-42D2-B80D-5EF3AA555126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2861068ce2dce5975bcacf1aa90b84a22e43b7","datavalue":{"value":{"entity-type":"item","numeric-id":1058290,"id":"Q1058290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$B8A57890-AC6A-43B2-B5C1-29D0B05F9A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$96A6B11D-FCA1-4370-BAE1-05914E93D742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9674148e539c769c7cdfd14a34ccd8e74dc136e","datavalue":{"value":{"entity-type":"item","numeric-id":1060843,"id":"Q1060843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$EF626E6B-B400-417C-B7E4-7AA0223B2787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d545d46281c27f7c22d936768292713b57021712","datavalue":{"value":{"entity-type":"item","numeric-id":5617749,"id":"Q5617749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$FAE9764B-656B-44F5-845A-1F8A0CFA83BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed5cab814cd603492c1673559e52eda9669c1aa7","datavalue":{"value":{"entity-type":"item","numeric-id":5512231,"id":"Q5512231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090414$93E21A65-41B0-4B86-8A8B-FF451150C863","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ee62a5178a99bdcc0a3e4c33b6efb9b8f481a95","datavalue":{"value":{"entity-type":"item","numeric-id":1060843,"id":"Q1060843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b1ad365478d4fc62f2c47fc6f6cb3ce54c735bb","datavalue":{"value":{"amount":"+0.8727190494537354","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":"Q1090414$195ED71A-9FDF-4C5E-A03E-C0D425501ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7931ba66927e54ac56086d8760584094a87bee51","datavalue":{"value":{"entity-type":"item","numeric-id":3678670,"id":"Q3678670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2679d94cd8536cee3c631ba545ac9c9a8a2ad1ea","datavalue":{"value":{"amount":"+0.8398877382278442","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":"Q1090414$5F416BF6-9589-4028-B524-D646D081DEAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47fe02ae4e715ef705a5d5deb2b49f948c702a9d","datavalue":{"value":{"entity-type":"item","numeric-id":4226412,"id":"Q4226412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa27676d5b2b7d5dd574bab1d8f63f8e0ea884dd","datavalue":{"value":{"amount":"+0.825291633605957","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":"Q1090414$8ADEF787-C8D2-49E8-979A-50EA7464E058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e55791eb026da0ad2049d4f13d02259d4be79f9","datavalue":{"value":{"entity-type":"item","numeric-id":5501375,"id":"Q5501375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9f023245451260e6e08a2e0c1484ca3f8d5f16","datavalue":{"value":{"amount":"+0.8247647285461426","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":"Q1090414$AE4F3C11-2F29-4868-A572-FF78CCD167E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e54974ae6e53396d5ce0c94fd06a41ccab79bb7c","datavalue":{"value":{"entity-type":"item","numeric-id":1197618,"id":"Q1197618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8400d7eec05559f890710557faeb09ac2e2c51a8","datavalue":{"value":{"amount":"+0.8225558400154114","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":"Q1090414$AC2DD4EF-036F-4A26-BBE2-C2EF6A357A30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1090414","badges":[]}}}}}