{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T17:04:13Z","timestamp":1773853453835,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T00:00:00Z","timestamp":1740700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T00:00:00Z","timestamp":1740700800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2018-04211"],"award-info":[{"award-number":["RGPIN-2018-04211"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10623-025-01581-4","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T02:04:10Z","timestamp":1740708250000},"page":"2349-2367","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Constructing k-ary orientable sequences with asymptotically optimal length"],"prefix":"10.1007","volume":"93","author":[{"given":"Daniel","family":"Gabri\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joe","family":"Sawada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"1581_CR1","unstructured":"Adamson D., Gusev V.V., Potapov I., Deligkas A.: Ranking bracelets in polynomial time. In: Gawrychowski P., Starikovskaya T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs) Series, vol. 191, pp. 4:1\u20134:17. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2021)."},{"key":"1581_CR2","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1007\/s12095-024-00742-x","volume":"16","author":"A Alhakim","year":"2024","unstructured":"Alhakim A., Mitchell C.J., Szmidt J., Wild P.R.: Orientable sequences over non-binary alphabets. Cryptogr. Commun. 16, 1309\u20131326 (2024).","journal-title":"Cryptogr. Commun."},{"issue":"4","key":"1581_CR3","doi-asserted-by":"publisher","first-page":"1832","DOI":"10.1137\/100805674","volume":"25","author":"A Blanca","year":"2011","unstructured":"Blanca A., Godbole A.P.: On universal cycles for new classes of combinatorial structures. SIAM J. Discret. Math. 25(4), 1832\u20131842 (2011).","journal-title":"SIAM J. Discret. Math."},{"issue":"4\/5","key":"1581_CR4","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/0020-0190(80)90149-0","volume":"10","author":"KS Booth","year":"1980","unstructured":"Booth K.S.: Lexicographically least circular substrings. Inf. Process. Lett. 10(4\/5), 240\u2013242 (1980).","journal-title":"Inf. Process. Lett."},{"key":"1581_CR5","first-page":"31","volume-title":"Cryptography and Coding III","author":"J Burns","year":"1993","unstructured":"Burns J., Mitchell C.J.: Position sensing coding schemes. In: Ganley M.J. (ed.) Cryptography and Coding III, pp. 31\u201366. Oxford University Press, Oxford (1993)."},{"issue":"1","key":"1581_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0012-365X(92)90699-G","volume":"110","author":"F Chung","year":"1992","unstructured":"Chung F., Diaconis P., Graham R.: Universal cycles for combinatorial structures. Discret. Math. 110(1), 43\u201359 (1992).","journal-title":"Discret. Math."},{"key":"1581_CR7","doi-asserted-by":"crossref","unstructured":"Currie J., Lafrance P.: Avoidability index for binary patterns with reversal. Electron. J. Combin. 23(1), 1\u201314, #P1.36 (2016).","DOI":"10.37236\/5483"},{"issue":"3","key":"1581_CR8","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1137\/080735795","volume":"23","author":"D Curtis","year":"2009","unstructured":"Curtis D., Hines T., Hurlbert G., Moyer T.: Near-universal cycles for subsets exist. SIAM J. Disc. Math. 23(3), 1441\u20131449 (2009).","journal-title":"SIAM J. Disc. Math."},{"key":"1581_CR9","first-page":"97","volume-title":"Cryptography and Coding III","author":"ZD Dai","year":"1993","unstructured":"Dai Z.D., Martin K.M., Robshaw M.J.B., Wild P.R.: Orientable sequences. In: Ganley M.J. (ed.) Cryptography and Coding III, pp. 97\u2013115. Oxford University Press, Oxford (1993)."},{"issue":"6","key":"1581_CR10","doi-asserted-by":"publisher","first-page":"2323","DOI":"10.1007\/s00373-016-1727-6","volume":"32","author":"M D\u0229bski","year":"2016","unstructured":"D\u0229bski M., Lonc Z.: Universal cycle packings and coverings for $$k$$-subsets of an $$n$$-set. Graphs and Combinatorics 32(6), 2323\u20132337 (2016).","journal-title":"Graphs and Combinatorics"},{"key":"1581_CR11","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/11925903_14","volume-title":"DNA Computing","author":"M Domaratzki","year":"2006","unstructured":"Domaratzki M.: Hairpin structures defined by DNA trajectories. In: Computing D.N.A., Mao C., Yokomori T. (eds.) DNA Computing, vol. 4287, pp. 182\u2013194. Lecture Notes in Computer Science Series. Springer, Berlin (2006)."},{"issue":"2","key":"1581_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(86)90118-0","volume":"44","author":"T Etzion","year":"1986","unstructured":"Etzion T.: An algorithm for generating shift-register cycles. Theor. Comput. Sci. 44(2), 209\u2013224 (1986).","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1581_CR13","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0097-3165(87)90035-5","volume":"44","author":"T Etzion","year":"1987","unstructured":"Etzion T.: Self-dual sequences. J. Comb. Theory Ser. A 44(2), 288\u2013298 (1987).","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"1581_CR14","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1109\/TIT.1984.1056919","volume":"30","author":"T Etzion","year":"1984","unstructured":"Etzion T., Lempel A.: Algorithms for the generation of full-length shift-register sequences. IEEE Trans. Inf. Theory 30(3), 480\u2013484 (1984).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1581_CR15","unstructured":"Fleischer L., Shallit J.O.: Words that avoid reversed factors, revisited. arXiv preprint (2019). arXiv:1911.11704 [cs.FL]."},{"issue":"2","key":"1581_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/1024041","volume":"24","author":"H Fredricksen","year":"1982","unstructured":"Fredricksen H.: A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24(2), 195\u2013221 (1982).","journal-title":"SIAM Rev."},{"key":"1581_CR17","unstructured":"Gabri\u0107 D., Sawada J.: Construction of orientable sequences in $${O}(1)$$-amortized time per bit. arXiv preprint (2024a). arXiv:2401.14341v3."},{"key":"1581_CR18","unstructured":"Gabri\u0107 D., Sawada J.: Efficient construction of long orientable sequences. In: 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024), pp. 1\u201312 (to appear) (2024b)."},{"issue":"1","key":"1581_CR19","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1109\/TIT.2019.2928292","volume":"66","author":"D Gabri\u0107","year":"2020","unstructured":"Gabri\u0107 D., Sawada J., Williams A., Wong D.: A successor rule framework for constructing $$k$$-ary de Bruijn sequences and universal cycles. IEEE Trans. Inf. Theory 66(1), 679\u2013687 (2020).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1581_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer C.: Ueber die M\u00f6glichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6, 30\u201332 (1873).","journal-title":"Math. Ann."},{"issue":"2","key":"1581_CR21","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(2), 215\u2013245 (2012).","journal-title":"Algorithmica"},{"issue":"1","key":"1581_CR22","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/0196-6774(90)90028-D","volume":"11","author":"Y Huang","year":"1990","unstructured":"Huang Y.: A new algorithm for the generation of binary de Bruijn sequences. J. Algorithms 11(1), 44\u201351 (1990).","journal-title":"J. Algorithms"},{"issue":"4","key":"1581_CR23","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/S0895480191220861","volume":"7","author":"G Hurlbert","year":"1994","unstructured":"Hurlbert G.: On universal cycles for $$k$$-subsets of an $$n$$-set. SIAM J. Discret. Math. 7(4), 598\u2013604 (1994).","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1581_CR24","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(93)90330-V","volume":"117","author":"BW Jackson","year":"1993","unstructured":"Jackson B.W.: Universal cycles of $$k$$-subsets and $$k$$-permutations. Discret. Math. 117(1), 141\u2013150 (1993).","journal-title":"Discret. Math."},{"issue":"5","key":"1581_CR25","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1109\/18.133272","volume":"37","author":"CJA Jansen","year":"1991","unstructured":"Jansen C.J.A., Franx W.G., Boekee D.E.: An efficient algorithm for the generation of DeBruijn cycles. IEEE Trans. Inf. Theory 37(5), 1475\u20131478 (1991).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1581_CR26","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/11753681_12","volume-title":"DNA Computing","author":"L Kari","year":"2006","unstructured":"Kari L., Konstantinidis S., Losseva E., Sos\u00edk P., Thierrin G.: Hairpin structures in DNA words. In: Computing D.N.A., Carbone A., Pierce N.A. (eds.) DNA Computing, vol. 3892, pp. 158\u2013170. Lecture Notes in Computer Science Series. Springer, Berlin (2006)."},{"issue":"05","key":"1581_CR27","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1142\/S0129054105003467","volume":"16","author":"L Kari","year":"2005","unstructured":"Kari L., Konstantinidis S., Sos\u00edk P.: Bond-free languages: formalizations, maximality and construction methods. Int. J. Found. Comput. Sci. 16(05), 1039\u20131070 (2005).","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1581_CR28","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/11505877_26","volume-title":"Developments in Language Theory","author":"L Kari","year":"2005","unstructured":"Kari L., Konstantinidis S., Sos\u00edk P., Thierrin G.: On hairpin-free words and languages. In: De Felice C., Restivo A. (eds.) Developments in Language Theory, vol. 3572, pp. 296\u2013307. Lecture Notes in Computer Science Series. Springer, Berlin (2005)."},{"key":"1581_CR29","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.tcs.2016.12.022","volume":"682","author":"R Merca\u015f","year":"2017","unstructured":"Merca\u015f R.: On the aperiodic avoidability of binary patterns with variables and reversals. Theor. Comput. Sci. 682, 180\u2013189 (2017).","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"1581_CR30","doi-asserted-by":"publisher","first-page":"4782","DOI":"10.1109\/TIT.2022.3158645","volume":"68","author":"CJ Mitchell","year":"2022","unstructured":"Mitchell C.J., Wild P.R.: Constructing orientable sequences. IEEE Trans. Inf. Theory 68(7), 4782\u20134789 (2022).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1581_CR31","doi-asserted-by":"crossref","unstructured":"Mitchell C.J., Wild P.R.: Orientable and negative orientable sequences. arXiv preprint (2024). arXiv:2409.00672.","DOI":"10.2139\/ssrn.5124754"},{"key":"1581_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03563-4","volume-title":"DNA Computing: New Computing Paradigms","author":"G P\u01ceun","year":"1998","unstructured":"P\u01ceun G., Rozenberg G., Salomaa A.: DNA Computing: New Computing Paradigms. Springer, Berlin (1998)."},{"key":"1581_CR33","first-page":"157","volume":"54","author":"N Rampersad","year":"2005","unstructured":"Rampersad N., Shallit J.O.: Words that avoid reversed subwords. J. Comb. Math. Comb. Comput. 54, 157\u2013164 (2005).","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"1581_CR34","doi-asserted-by":"publisher","first-page":"P18","DOI":"10.37236\/2852","volume":"20","author":"Y Rudoy","year":"2013","unstructured":"Rudoy Y.: An inductive approach to constructing universal cycles on the $$k$$-subsets of [$$n$$]. Electron. J. Comb. 20, P18 (2013).","journal-title":"Electron. J. Comb."},{"issue":"3","key":"1581_CR35","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 6(3), 1\u201312 (2010).","journal-title":"ACM Trans. Algorithms"},{"key":"1581_CR36","unstructured":"Sawada J., Sears J., Trautrim A., Williams A.: Concatenation trees: a framework for efficient universal cycle and de Bruijn sequence constructions. arXiv preprint (2023). arXiv:2308.12405 [math.CO]."},{"issue":"6","key":"1581_CR37","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1007\/s00453-022-01047-2","volume":"85","author":"J Sawada","year":"2023","unstructured":"Sawada J., Williams A.: Constructing the first (and coolest) fixed-content universal cycle. Algorithmica 85(6), 1754\u20131785 (2023).","journal-title":"Algorithmica"},{"key":"1581_CR38","doi-asserted-by":"crossref","unstructured":"Sawada J., Williams A., Wong D.: Universal cycles for weight-range binary strings. In: Combinatorial Algorithms\u201424th International Workshop, IWOCA 2013, Rouen, France, 10\u201312 July 2013. LNCS, vol. 8288, pp. 388\u2013401 (2013).","DOI":"10.1007\/978-3-642-45278-9_33"},{"issue":"10","key":"1581_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.112022","volume":"343","author":"J Sawada","year":"2020","unstructured":"Sawada J., Wong D.: Efficient universal cycle constructions for weak orders. Discret. Math. 343(10), 112022 (2020).","journal-title":"Discret. Math."},{"issue":"1","key":"1581_CR40","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0012-365X(02)00298-4","volume":"258","author":"B Stevens","year":"2002","unstructured":"Stevens B., Buskell P., Ecimovic P., Ivanescu C., Malik A.M., Savu A., Vassilev T.S., Verrall H., Yang B., Zhao Z.: Solution of an outstanding conjecture: the non-existence of universal cycles with $$k=n-2$$. Discret. Math. 258(1), 193\u2013204 (2002).","journal-title":"Discret. Math."},{"key":"1581_CR41","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/11493785_31","volume-title":"DNA Computing","author":"N Takahashi","year":"2005","unstructured":"Takahashi N., Kameda A., Yamamoto M., Ohuchi A.: Aqueous computing with DNA hairpin-based RAM. In: Ferretti C., Mauri G., Zandron C. (eds.) DNA Computing, pp. 355\u2013364. Springer, Berlin (2005)."},{"issue":"11","key":"1581_CR42","doi-asserted-by":"publisher","first-page":"1244","DOI":"10.1002\/smll.200600237","volume":"2","author":"M Takinoue","year":"2006","unstructured":"Takinoue M., Suyama A.: Hairpin-DNA memory using molecular addressing. Small 2(11), 1244\u20131247 (2006).","journal-title":"Small"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01581-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-025-01581-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01581-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T06:44:27Z","timestamp":1757141067000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-025-01581-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,28]]},"references-count":42,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1581"],"URL":"https:\/\/doi.org\/10.1007\/s10623-025-01581-4","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,28]]},"assertion":[{"value":"8 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}