{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:18:47Z","timestamp":1743031127399,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031439797"},{"type":"electronic","value":"9783031439803"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43980-3_26","type":"book-chapter","created":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T12:02:15Z","timestamp":1695124935000},"page":"323-330","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Constant Time and\u00a0Space Updates for\u00a0the\u00a0Sigma-Tau Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3233-0691","authenticated-orcid":false,"given":"Zsuzsanna","family":"Lipt\u00e1k","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2078-6835","authenticated-orcid":false,"given":"Francesco","family":"Masillo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6816-4368","authenticated-orcid":false,"given":"Aaron","family":"Williams","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"issue":"5","key":"26_CR1","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1089\/106652701753216503","volume":"8","author":"DA Bader","year":"2001","unstructured":"Bader, D.A., Moret, B.M.E., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J. Comput. Biol. 8(5), 483\u2013491 (2001)","journal-title":"J. Comput. Biol."},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pp. 148\u2013157. IEEE Computer Society (1993)","DOI":"10.1109\/SFCS.1993.366872"},{"issue":"2","key":"26_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discret. Math. 11(2), 224\u2013240 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Bass, D.W., Sudborough, I.H.: On the shuffle-exchange permutation network. In: Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN 1997), pp. 165\u2013171. IEEE (1997)","DOI":"10.1109\/ISPAN.1997.645088"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-86692-1_1","volume-title":"String Processing and Information Retrieval","author":"C Boucher","year":"2021","unstructured":"Boucher, C., Cenzato, D., Lipt\u00e1k, Z., Rossi, M., Sciortino, M.: r-indexing the eBWT. In: Lecroq, T., Touzet, H. (eds.) SPIRE 2021. LNCS, vol. 12944, pp. 3\u201312. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86692-1_1"},{"issue":"3","key":"26_CR6","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00453-022-01022-x","volume":"85","author":"B Cameron","year":"2023","unstructured":"Cameron, B., Sawada, J., Therese, W., Williams, A.: Hamiltonicity of k-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality. Algorithmica 85(3), 717\u2013744 (2023)","journal-title":"Algorithmica"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2019.10.012","volume":"279","author":"G Cerbai","year":"2020","unstructured":"Cerbai, G., Ferrari, L.S.: Permutation patterns in genome rearrangement problems: The reversal model. Discret. Appl. Math. 279, 34\u201348 (2020)","journal-title":"Discret. Appl. Math."},{"issue":"3\u20134","key":"26_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1080\/03081089308818261","volume":"35","author":"RC Compton","year":"1993","unstructured":"Compton, R.C., Gill Williamson, S.: Doubly adjacent gray codes for the symmetric group. Linear Multilinear Algebra 35(3\u20134), 237\u2013293 (1993)","journal-title":"Linear Multilinear Algebra"},{"key":"26_CR9","unstructured":"Egan, G.: Superpermutations (2018). http:\/\/www.gregegan.net\/SCIENCE\/Superpermutations\/Superpermutations.html"},{"issue":"3","key":"26_CR10","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1145\/321765.321781","volume":"20","author":"G Ehrlich","year":"1973","unstructured":"Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. ACM 20(3), 500\u2013513 (1973)","journal-title":"J. ACM"},{"issue":"1","key":"26_CR11","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1080\/00029890.2021.1835384","volume":"128","author":"M Engen","year":"2020","unstructured":"Engen, M., Vatter, V.: Containing all permutations. Am. Math. Mon. 128(1), 4\u201324 (2020)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"26_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1273340.1273341","volume":"3","author":"J Feng","year":"2007","unstructured":"Feng, J., Zhu, D.: Faster algorithms for sorting by transpositions and sorting by block interchanges. ACM Trans. Algorithms 3(3), 25 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52, 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"26_CR14","series-title":"Computational Molecular Biology","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of Genome Rearrangements","author":"G Fertin","year":"2009","unstructured":"Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. Computational Molecular Biology, MIT Press, Cambridge (2009)"},{"issue":"51","key":"26_CR15","doi-asserted-by":"publisher","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theoret. Comput. Sci. 410(51), 5354\u20135364 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully-functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM 67(1), article 2 (2020)","DOI":"10.1145\/3375890"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1459\u20131477 (2018)","DOI":"10.1137\/1.9781611975031.96"},{"issue":"3","key":"26_CR18","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1093\/comjnl\/bxab181","volume":"66","author":"P Ganapathi","year":"2023","unstructured":"Ganapathi, P., Chowdhury, R.: A unified framework to discover permutation generation algorithms. Comput. J. 66(3), 603\u2013614 (2023)","journal-title":"Comput. J."},{"issue":"2","key":"26_CR19","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC 1995), pp. 178\u2013189. ACM (1995)","DOI":"10.1145\/225058.225112"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Hartman, T., Shamir, R.: A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput. 204(2), 275\u2013290 (2006)","DOI":"10.1016\/j.ic.2005.09.002"},{"key":"26_CR22","unstructured":"Hindenburg, C.F.: Sammlung combinatorisch-analytischer Abhandlungen, vol. 1. ben Gerhard Fleischer dem Jungern (1796)"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00453-011-9544-z","volume":"64","author":"AE Holroyd","year":"2012","unstructured":"Holroyd, A.E., Ruskey, F., Williams, A.: Shorthand universal cycles for permutations. Algorithmica 64, 215\u2013245 (2012)","journal-title":"Algorithmica"},{"key":"26_CR24","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming). Addison-Wesley Professional (2005)"},{"issue":"1","key":"26_CR25","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2012.03.005","volume":"438","author":"JI Munro","year":"2012","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations and functions. Theoret. Comput. Sci. 438, 74\u201388 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"M\u00fctze, T.: Combinatorial gray codes\u2013an updated survey. Electron. J. Combin. 30(3-DS26) (2023)","DOI":"10.37236\/11023"},{"key":"26_CR28","unstructured":"OEIS Foundation Inc.: Sequence A055881 in the On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A055881. Accessed 2 June 2023"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Rankin, R.A.: A campanological problem in group theory. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 44, pp. 17\u201325. Cambridge University Press (1948)","DOI":"10.1017\/S030500410002394X"},{"issue":"17","key":"26_CR30","doi-asserted-by":"publisher","first-page":"5305","DOI":"10.1016\/j.disc.2007.11.048","volume":"309","author":"F Ruskey","year":"2009","unstructured":"Ruskey, F., Williams, A.: The coolest way to generate combinations. Discret. Math. 309(17), 5305\u20135320 (2009)","journal-title":"Discret. Math."},{"issue":"3","key":"26_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1798596.1798598","volume":"6","author":"F Ruskey","year":"2010","unstructured":"Ruskey, F., Williams, A.: An explicit universal cycle for the $$(n-1)$$-permutations of an $$n$$-set. ACM Trans. Algorithms (TALG) 6(3), 1\u201312 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"26_CR32","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2021.06.008","volume":"882","author":"W Rytter","year":"2021","unstructured":"Rytter, W., Zuba, W.: Syntactic view of sigma-tau generation of permutations. Theor. Comput. Sci. 882, 49\u201362 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"26_CR33","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"CD Savage","year":"1997","unstructured":"Savage, C.D.: A survey of combinatorial Gray codes. SIAM Rev. 39(4), 605\u2013629 (1997)","journal-title":"SIAM Rev."},{"key":"26_CR34","doi-asserted-by":"crossref","unstructured":"Sawada, J., Williams, A.: A Hamilton path for the Sigma-Tau problem. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 568\u2013575. SIAM (2018)","DOI":"10.1137\/1.9781611975031.37"},{"key":"26_CR35","doi-asserted-by":"crossref","unstructured":"Sawada, J., Williams, A.: Solving the Sigma-Tau problem. ACM Trans. Algorithms 16(1), 11:1\u201311:17 (2020)","DOI":"10.1145\/3359589"},{"key":"26_CR36","first-page":"1","volume":"85","author":"J Sawada","year":"2022","unstructured":"Sawada, J., Williams, A.: Constructing the first (and coolest) fixed-content universal cycle. Algorithmica 85, 1\u201332 (2022)","journal-title":"Algorithmica"},{"issue":"2","key":"26_CR37","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R Sedgewick","year":"1977","unstructured":"Sedgewick, R.: Permutation generation methods. ACM Comput. Surv. (CSUR) 9(2), 137\u2013164 (1977)","journal-title":"ACM Comput. Surv. (CSUR)"},{"issue":"2","key":"26_CR38","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1080\/00029890.1999.12005023","volume":"106","author":"RG Swan","year":"1999","unstructured":"Swan, R.G.: A simple proof of Rankin\u2019s campanological theorem. Am. Math. Mon. 106(2), 159\u2013161 (1999)","journal-title":"Am. Math. Mon."},{"key":"26_CR39","doi-asserted-by":"crossref","unstructured":"Williams, A.: Loopless generation of multiset permutations using a constant number of variables by prefix shifts. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 987\u2013996. SIAM (2009)","DOI":"10.1137\/1.9781611973068.107"},{"key":"26_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-642-13122-6_35","volume-title":"Fun with Algorithms","author":"A Williams","year":"2010","unstructured":"Williams, A.: O(1)-time unsorting by prefix-reversals in a boustrophedon linked list. In: Boldi, P., Gargano, L. (eds.) FUN 2010. LNCS, vol. 6099, pp. 368\u2013379. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13122-6_35"},{"key":"26_CR41","unstructured":"Williams, A.: Hamiltonicity of the Cayley digraph on the symmetric group generated by $$\\sigma =(1 \\; 2 \\ldots \\; n)$$ and $$\\tau =(1 \\; 2)$$. CoRR abs\/1307.2549 (2013)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43980-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T10:40:53Z","timestamp":1730112053000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43980-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031439797","9783031439803"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43980-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"20 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2023.isti.cnr.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}