{"entities":{"Q1270640":{"pageid":1281390,"ns":120,"title":"Item:Q1270640","lastrevid":67466691,"modified":"2026-04-12T18:09:02Z","type":"item","id":"Q1270640","labels":{"en":{"language":"en","value":"Nearly linear time algorithms for permutation groups: An interplay between theory and practice"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1218141"}},"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":"Q1270640$CE05008F-B04C-47B7-83FC-37E280C3AC20","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"814e228147a5058964edba9ec9b00c6427f9b5ff","datavalue":{"value":{"text":"Nearly linear time algorithms for permutation groups: An interplay between theory and practice","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1270640$2FE9DD63-F957-4A29-B05B-1A383BA21950","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3bbb7070e22e7f44e60adcc3fa5ae31654d2585e","datavalue":{"value":"0915.20001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$72E28A32-5FA4-41D1-8FD7-3C03D9849749","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c3ae2b0a1b8fd8d5b8ca590bdac28d30e035203","datavalue":{"value":"10.1023/A:1005911125383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$FE5726D0-0A7C-458D-B6CA-5373032FA24C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8d1231d86866fb01586b04e1f50e347c0a84f9cd","datavalue":{"value":{"entity-type":"item","numeric-id":190587,"id":"Q190587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270640$D5A4C9B0-3021-4B2C-B79B-31FDD9032197","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de63786316ebd0af50500de630c61ac9ddeda062","datavalue":{"value":{"time":"+1999-04-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1270640$170C3928-E20D-41C7-A613-3810DA7F0F93","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"42b9302a8567920d1e9e3442b898cffd9bb89c0b","datavalue":{"value":"This paper contains a nice survey of permutation group algorithms, concentrating on those which are polynomial time but also mentioning some which are not. The focus is on asymptotic analysis but practical implementations are mentioned also. This paper emphasizes ``nearly linear time'' algorithms, that is, those whose time bound is \\(O(n\\log^c| G|)\\) for a permutation group \\(G\\) of degree \\(n\\). (In the important case of small-base groups this time bound is linear except for factors of \\(\\log n\\).) After surveying several existing algorithms, the author presents some new nearly linear time algorithms (building on previous methods), culminating in one for finding the upper central series of a nilpotent group. This new algorithm is deterministic, unlike many other nearly linear time algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$4BF79AE9-87DC-47E6-AE64-BA9FB682AD05","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0ac1dafab2cb163643c64b3cf5c7678542cb29be","datavalue":{"value":"20B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$E452C144-5EFF-4212-9513-96476CAC5E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$D2438706-C8B9-4CF1-9BA2-A34EDAF8A342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$A9D1B9AE-3FD2-43A8-A1D3-9BE715D7F762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$7E4B5414-6E75-48C5-9C7F-E84623A3152F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d147236e0258eee5c0f4ad96f648e60a7ad2268","datavalue":{"value":"1218141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$8D12E569-10CD-49B2-8C83-15DA5B5CCAA5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d63abd00ba97e023260564ab1e5de7e72c9aae49","datavalue":{"value":"computational group theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$AC99416C-4A92-477F-8D0A-7DE2A42EF7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e3f7e0d18e9c7e5b9f5b19131aa549a1a707c3","datavalue":{"value":"permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$AB5ADE56-CEEC-461B-9299-B21E397B726E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68ef19f20ff91ae88cc10e972b96cbda1374bb9d","datavalue":{"value":"nearly linear time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$24A32871-0A82-4738-9809-F98690BCE287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bf0882370430827bf0ad95308baea9eb0d81fc7","datavalue":{"value":"deterministic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$E26FDBE5-E4D8-4EA6-BEAC-7BA92BA49972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88532c5e6291dc0f24c20ac44f61fba2930f2129","datavalue":{"value":"upper central series","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270640$4F838BED-CCD8-4814-B13F-61E9A1AACFBF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"306d9099ef8452dabdd265171a602e1aa51bd912","datavalue":{"value":{"entity-type":"item","numeric-id":162994,"id":"Q162994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270640$4FE062FB-7D6C-440E-B4AC-F1C7FA7083A1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"049723a0d6b9805299dc5ac60f4b30f3ffca1d3a","datavalue":{"value":{"entity-type":"item","numeric-id":757410,"id":"Q757410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270640$0BD73502-D6DF-4629-A9E9-4E9204EAF7C5","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4fe03e5b78d9974ebdfc0233dbd377f30d5d075f","datavalue":{"value":{"entity-type":"item","numeric-id":13295,"id":"Q13295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270640$0974DBB9-4DBA-4D77-BAD0-64AD75B7F3EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"58012661cd5902d08c1d307a106ffc22f40d0c6b","datavalue":{"value":{"entity-type":"item","numeric-id":13366,"id":"Q13366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270640$D56E96ED-A75A-49C3-B349-550EBA34B4B6","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":"Q1270640$923994D2-FEAF-4F64-BE1C-CC4950A34F1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"53d4bdb2574932777abaac04a92f5af0f87789b2","datavalue":{"value":"https://doi.org/10.1023/a:1005911125383","type":"string"},"datatype":"url"},"type":"statement","id":"Q1270640$417E62C8-A740-463A-A133-1C7641E98B40","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5234886306cd94d3d70b78b765feeb1b836d5e98","datavalue":{"value":"W1602534306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270640$C851C50E-6FC3-49A8-81F5-1E5F5D3E965E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d8343c039e70d0a2959362768122774d4e24fad","datavalue":{"value":{"entity-type":"item","numeric-id":4237394,"id":"Q4237394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99b84a3c27fd0f6101bd5fe336d7cccc01da256d","datavalue":{"value":{"amount":"+0.8829119205474854","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":"Q1270640$264D004C-4C6F-4AEE-9F65-C003AEDDD393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92fe6ac6b2c143c93316373d2083debfe0241964","datavalue":{"value":{"entity-type":"item","numeric-id":4335303,"id":"Q4335303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33b7ee63148ec16366efdf33b2f5614514c67677","datavalue":{"value":{"amount":"+0.8453302383422852","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":"Q1270640$A58390FB-0E48-40D1-9293-1D13E385530B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb10026b3595e258ac9c57efc53660da3303392","datavalue":{"value":{"entity-type":"item","numeric-id":1355778,"id":"Q1355778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ade3ee62e5b4c3f51f0de7724a9d5f969d29785","datavalue":{"value":{"amount":"+0.8356590867042542","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":"Q1270640$D9C38F34-C8D3-4A71-87AA-9BC686B906E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec6587de9b883b4effa53e18bd24d59920028ac5","datavalue":{"value":{"entity-type":"item","numeric-id":4227307,"id":"Q4227307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e1eae67cb33d0a419e65b210989d86e37b93876","datavalue":{"value":{"amount":"+0.829619824886322","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":"Q1270640$95825386-4B71-4471-BF55-8EF431F86E85","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nearly linear time algorithms for permutation groups: An interplay between theory and practice","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nearly_linear_time_algorithms_for_permutation_groups:_An_interplay_between_theory_and_practice"}}}}}