{"entities":{"Q303693":{"pageid":305460,"ns":120,"title":"Item:Q303693","lastrevid":56790618,"modified":"2026-03-23T15:00:21Z","type":"item","id":"Q303693","labels":{"en":{"language":"en","value":"A linear-time algorithm for the orbit problem over cyclic groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6618616"}},"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":"Q303693$9F3B4398-0C37-430C-8282-FFF7F9A6F4A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f64acc33e2a4f58bead1d1df4b8382c4df2a70b5","datavalue":{"value":{"text":"A linear-time algorithm for the orbit problem over cyclic groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q303693$E5E4F707-C317-4BF4-BFD3-6B127874FF48","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b1b923308958d0353fc327e4ce84f253ea90e46f","datavalue":{"value":"1347.68186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$3E109204-35F0-4C7F-B0FF-483932E15DEB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1da51825dbac02dbae2b1fae272f812e9417016","datavalue":{"value":{"entity-type":"item","numeric-id":201997,"id":"Q201997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$08384762-93A7-4FBD-AA3D-28AD96DD30DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d16040d29a42a439381bf088783c9058f5cad35","datavalue":{"value":{"entity-type":"item","numeric-id":1708663,"id":"Q1708663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$D99822EB-94A8-4790-8967-A36E75ADB66D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$375C2CD0-B511-4905-BD9D-6DCEFF00BE02","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70e273fe9462a734f2d1ac8ce28702f050bb6f4b","datavalue":{"value":{"time":"+2016-08-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":"Q303693$09931A61-E598-41D0-9CF8-B1527FEB3463","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"51473868fc98ee3cf9315e12822446301879ab87","datavalue":{"value":"https://arxiv.org/abs/1411.3164","type":"string"},"datatype":"url"},"type":"statement","id":"Q303693$E14CED17-2C76-4D2A-8046-E15E23DFF9E5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e81becdf0b93b49a8d24a17dbef226ad0232cb88","datavalue":{"value":"Let \\(G\\leq S_n\\) be a permutation group given by its generators. Let \\(\\Gamma\\) be an alphabet, then \\(G\\) acts on \\(\\Gamma^n\\) by permuting the indices. The orbit problem asks if two input words are in the same orbit with respect to this action. In general this problem is as hard as the graph isomorphism problem (see [\\textit{E. M. Clarke} et al., ``Exploiting symmetry in temporal logic model checking'', Formal Methods Syst. Des. 9, No. 1--2, 77--104 (1996; \\url{doi:10.1007/BF00625969})]).  The authors give a linear algorithm for the orbit problem when \\(G\\) is cyclic given by its generating permutation. They reduce the problem in linear time to solving a system of linear congruence equations. For the latter there exists a well-known linear algorithm assuming constant-time integer arithmetic operations. However, this algorithm runs in cubic time in the number of equations if the number of bit operations is measured. Therefore the authors provide a linear algorithm to solve a system of linear congruence equations in the bit complexity model, as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q303693$D653D595-CC3E-4A1E-8B1B-E3BAFD7D5C43","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$BD7FC36D-C62F-4173-98CF-83F6598FF692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6321ce6a9565f5f3e695a7afbb7a3eee2274d95d","datavalue":{"value":"11A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$DF7B81C1-DB5F-4063-895E-346596AE243F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0ac1dafab2cb163643c64b3cf5c7678542cb29be","datavalue":{"value":"20B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$3A6DF217-6613-474B-919B-E744A1A84334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9b5ca6a3bce811e2a3489608b95705717ca7328","datavalue":{"value":"20K01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$16BA3555-3546-4772-845B-8E4947BE1D76","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9fc7b6ab60fcd5efd866c3ff48e779c08572ca8","datavalue":{"value":"6618616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$3320AE7A-DAA5-48D4-8718-BDD4207448E9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"028e9c53e5c4550f5a7cbca2f6ae65c7e2ae92d1","datavalue":{"value":"orbit problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q303693$1C5EAD0A-4F7C-4A9F-AD46-E97CF20568F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b670490c7fe1a1183de0d6305c4f36548a861e99","datavalue":{"value":"system of linear congruence equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q303693$2FC42464-77A0-4643-8586-AB6D7126D38D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c2f271051bcea5067049becc331418d51167c4a","datavalue":{"value":"linear algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q303693$60065D25-1353-4878-9EAA-E5067712C52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e703bd7f998e27f84f2fa175f0b502d99f6eb93","datavalue":{"value":"bit complexity model","type":"string"},"datatype":"string"},"type":"statement","id":"Q303693$2D4851BC-787E-4643-9F2A-79289335CDD4","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"650e761a5f418c574655712b35b1fe882f756011","datavalue":{"value":{"entity-type":"item","numeric-id":19297,"id":"Q19297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$3A9303CE-4CFE-4912-A96F-9B86D8DCA983","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":"Q303693$02582743-155E-4D8F-BFF3-54F05E90F4C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74dfd7c0f905d05ce1433059c7236575633e54f7","datavalue":{"value":"W2099783652","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$C40E761A-77E2-4FDB-91F7-EA1007ABA420","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9c0297ccc7943530d7e60dae41b7cff33d7166","datavalue":{"value":{"entity-type":"item","numeric-id":1106840,"id":"Q1106840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$01D10E0A-BE36-4E5B-BE81-507604164969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a93f13262bc300fba769190aafdb0940400641e6","datavalue":{"value":{"entity-type":"item","numeric-id":4888749,"id":"Q4888749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$89849C40-A30D-47B0-AC2D-E15DE5C547C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c86a08be5f5838607c6949ad90f212a62c5cc3b","datavalue":{"value":{"entity-type":"item","numeric-id":4670644,"id":"Q4670644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$DF12CE88-20F6-45AA-8028-4ADC8442012C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff95cf9d4ceb86ce5090c97e97fbcd0a940d41b","datavalue":{"value":{"entity-type":"item","numeric-id":5432372,"id":"Q5432372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$79978ABC-F0A4-4E10-AC95-9811AAB40264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb228b8e0a9b8221782f1a1717638989a2d5dfc","datavalue":{"value":{"entity-type":"item","numeric-id":5484517,"id":"Q5484517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$16C900C8-E533-4249-A1B9-7D4E76017511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe234b893fe639d56d0ff3a37c6535b70c104f1","datavalue":{"value":{"entity-type":"item","numeric-id":4231664,"id":"Q4231664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$3A9BC16D-118B-4616-A3D9-F21B0A33A13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3bd2a89aeae9f01c497530d394e0c4804c2b95f","datavalue":{"value":{"entity-type":"item","numeric-id":3512430,"id":"Q3512430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$6824CEAF-69AE-4455-9B92-2B732FF984DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2854cda7e5988d324d2751b394a4a2ff4b92b03a","datavalue":{"value":{"entity-type":"item","numeric-id":4769056,"id":"Q4769056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$FF8BEA3C-9BDB-4C75-84DC-E6F8ADBCE5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$1F0282CE-5D11-43D7-A8A5-A5F6994F92D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"906bb055be1594d6031c60bc623b229c70cda2d4","datavalue":{"value":{"entity-type":"item","numeric-id":2862533,"id":"Q2862533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$4E407612-D318-46CE-8FDE-F711FF5D2B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b826c642afe26dad6e8fc081065e7b8060eb95b","datavalue":{"value":{"entity-type":"item","numeric-id":976988,"id":"Q976988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$7C70406A-20FB-446F-BD6E-BCFA463678FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f346f6935eab8f7bfd8c5b35d3ff010b785bc3a1","datavalue":{"value":{"entity-type":"item","numeric-id":4860774,"id":"Q4860774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$D032CD2C-5AC8-4064-A566-DB190773474C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"986e05cfef1c53e891858a34a46638d4252221a1","datavalue":{"value":{"entity-type":"item","numeric-id":3518705,"id":"Q3518705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$3BA4BA81-2E5E-4D9B-A2C8-928511B8C81A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a4719fb59209121c58d2497b93ce038b91f5ca3","datavalue":{"value":{"entity-type":"item","numeric-id":3462041,"id":"Q3462041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$DC880762-A414-4A5B-908F-5360F8078738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"067e393b8b4356a444ebb86fe4868b077a480748","datavalue":{"value":{"entity-type":"item","numeric-id":4273608,"id":"Q4273608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$8354B583-70EE-4824-98C6-ADA7D27E1AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8c877841b2c9b2cfab97814915e1e67ba82256c","datavalue":{"value":{"entity-type":"item","numeric-id":5325843,"id":"Q5325843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$64BA475A-915A-4604-B4E3-66ADD01394EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e7ce1f5ce7b22cd65f95bcce844b0844c2e79d2","datavalue":{"value":{"entity-type":"item","numeric-id":4855565,"id":"Q4855565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$DB7F0142-CD65-42BD-8D30-D07619AA875A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"667794c59d0b9bf8b44bb6b1022536e5fde568b5","datavalue":{"value":{"entity-type":"item","numeric-id":5316395,"id":"Q5316395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303693$CF64AEF3-0746-425A-9814-ABBA71AB55B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"048334b6a8dd73cd6b4363ae1d88f689fecbe119","datavalue":{"value":"10.1007/S00236-015-0251-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303693$BE2CAD84-2E31-4C05-95E0-CBA1E5E1755C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc2d28a32c665793a9444192af73f8aa26e84546","datavalue":{"value":{"entity-type":"item","numeric-id":3190127,"id":"Q3190127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ded592c839dd7425c1ba85b324d6150134b7cd8c","datavalue":{"value":{"amount":"+0.9869167804718018","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":"Q303693$15AB474A-BBB0-4E7A-9D85-C7329AA28E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5be2aa792261509b3bef663fe4b1b9ada52ddafc","datavalue":{"value":{"entity-type":"item","numeric-id":976988,"id":"Q976988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c1bc6e71951008d3defe306cd6dcd551dbfaacc","datavalue":{"value":{"amount":"+0.8011376261711121","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":"Q303693$AB340756-F8FA-4CB5-B7EA-8CFF042A225D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d5279c2bb3924dbfb0ea020a23b997f1f81704","datavalue":{"value":{"entity-type":"item","numeric-id":3344120,"id":"Q3344120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8877b18a5ea21318ff8a587f8c420478fc6f2aa","datavalue":{"value":{"amount":"+0.7739204168319702","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":"Q303693$074EA526-8EB3-4EEF-8852-35EDEE826714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"722494c895668aff3fc57e0cb08e7414e61bf58f","datavalue":{"value":{"entity-type":"item","numeric-id":3462041,"id":"Q3462041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df969a13ac1db5b24cd3b0c060b5f29d363a088c","datavalue":{"value":{"amount":"+0.761247456073761","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":"Q303693$AE61C88B-572E-4C37-8C51-07BA5EC88C8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc08693702180dd8fd4c66b690b83001b8a947e2","datavalue":{"value":{"entity-type":"item","numeric-id":2764000,"id":"Q2764000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e6a0082ff71ec69364618b559e1473faf5b6d76","datavalue":{"value":{"amount":"+0.7223242521286011","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":"Q303693$B0E08935-99F0-4F95-BF21-6125177110FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:303693","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:303693"}}}}}