{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T17:04:17Z","timestamp":1773853457327,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T00:00:00Z","timestamp":1725235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T00:00:00Z","timestamp":1725235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We describe new, simple, recursive methods of construction for <jats:italic>orientable sequences<\/jats:italic> over an arbitrary finite alphabet, i.e. periodic sequences in which any sub-sequence of <jats:italic>n<\/jats:italic> consecutive elements occurs at most once in a period in either direction. In particular we establish how two variants of a generalised Lempel homomorphism can be used to recursively construct such sequences, generalising previous work on the binary case. We also derive an upper bound on the period of an orientable sequence.<\/jats:p>","DOI":"10.1007\/s12095-024-00742-x","type":"journal-article","created":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T07:02:15Z","timestamp":1725260535000},"page":"1309-1326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Orientable sequences over non-binary alphabets"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2995-3740","authenticated-orcid":false,"given":"Abbas","family":"Alhakim","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6118-0055","authenticated-orcid":false,"given":"Chris J.","family":"Mitchell","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7482-2339","authenticated-orcid":false,"given":"Janusz","family":"Szmidt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7344-1742","authenticated-orcid":false,"given":"Peter R.","family":"Wild","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,2]]},"reference":[{"issue":"2","key":"742_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10623-010-9423-7","volume":"60","author":"A Alhakim","year":"2011","unstructured":"Alhakim, A., Akinwande, M.: A recursive construction of nonbinary de Bruijn sequences. Des. Codes Cryptogr. 60(2), 155\u2013169 (2011)","journal-title":"Des. Codes Cryptogr."},{"key":"742_CR2","unstructured":"Berkowitz, R.,\u00a0Kopparty, S.: Robust positioning patterns. In R.\u00a0Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pages 1937\u20131951. SIAM (2016)"},{"issue":"7","key":"742_CR3","doi-asserted-by":"publisher","first-page":"4884","DOI":"10.1109\/TIT.2012.2191699","volume":"58","author":"AM Bruckstein","year":"2012","unstructured":"Bruckstein, A.M., Etzion, T., Giryes, R., Gordon, N., Holt, R.J., Shuldiner, D.: Simple and robust binary self-location patterns. IEEE Trans. Inf. Theory 58(7), 4884\u20134889 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"742_CR4","doi-asserted-by":"crossref","unstructured":"Burns, J., Mitchell, C.J.: Coding schemes for two-dimensional position sensing. Technical Report HPL\u201392\u201319, January 1992. https:\/\/www.chrismitchell.net\/HPL-92-19.pdf","DOI":"10.1016\/0305-4179(93)90113-M"},{"key":"742_CR5","unstructured":"Burns, J., Mitchell, C.J.: Coding schemes for two-dimensional position sensing. In: Ganley, M.J.: editor, Cryptography and Coding III, pages 31\u201366. Oxford University Press (1993)"},{"key":"742_CR6","doi-asserted-by":"crossref","unstructured":"Chee, Y.M., Dao, D.T., Kiah, H.M.,\u00a0Ling, S.,\u00a0Wei, H.: Binary robust positioning patterns with low redundancy and efficient locating algorithms. In: Chan T.M., editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pages 2171\u20132184. SIAM (2019)","DOI":"10.1137\/1.9781611975482.131"},{"issue":"2","key":"742_CR7","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/19M1253472","volume":"49","author":"YM Chee","year":"2020","unstructured":"Chee, Y.M., Dao, D.T., Kiah, H.M., Ling, S., Wei, H.: Robust positioning patterns with low redundancy. SIAM J. Comput. 49(2), 284\u2013317 (2020)","journal-title":"SIAM J. Comput."},{"key":"742_CR8","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, 43\u201359 (1992)","journal-title":"Discret. Math."},{"key":"742_CR9","first-page":"97","volume-title":"Cryptography and Coding III","author":"Z-D 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)"},{"key":"742_CR10","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, 195\u2013221 (1982)","journal-title":"SIAM Rev."},{"key":"742_CR11","unstructured":"Gabric, D.,\u00a0Sawada, J.: Efficient construction of long orientable sequences, 2024. Available at https:\/\/arxiv.org\/abs\/2401.14341"},{"key":"742_CR12","volume-title":"Shift register sequences","author":"SW Golomb","year":"1967","unstructured":"Golomb, S.W.: Shift register sequences. Holden-Day, San Francisco (1967)"},{"issue":"17","key":"742_CR13","doi-asserted-by":"publisher","first-page":"5341","DOI":"10.1016\/j.disc.2009.04.002","volume":"309","author":"B Jackson","year":"2009","unstructured":"Jackson, B., Stevens, B., Hurlbert, G.: Research problems on Gray codes and universal cycles. Discret. Math. 309(17), 5341\u20135348 (2009)","journal-title":"Discret. Math."},{"key":"742_CR14","doi-asserted-by":"publisher","first-page":"1204","DOI":"10.1109\/T-C.1970.222859","volume":"C\u201319","author":"A Lempel","year":"1970","unstructured":"Lempel, A.: On a homomorphism of the de Bruijn graph and its application to the design of feedback shift registers. IEEE Transactions on Computers. C\u201319, 1204\u20131209 (1970)","journal-title":"IEEE Transactions on Computers."},{"key":"742_CR15","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1109\/18.532887","volume":"42","author":"CJ Mitchell","year":"1996","unstructured":"Mitchell, C.J., Etzion, T., Paterson, K.G.: A method for constructing decodable de Bruijn sequences. IEEE Trans. Inf. Theory 42, 1472\u20131478 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"742_CR16","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, 4782\u20134789 (2022)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"742_CR17","unstructured":"Nellore, A., Ward, R.A.: Arbitrary-length analogs to de Bruijn sequences. In H.\u00a0Bannai and J.\u00a0Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27\u201329, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 9:1\u20139:20. Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 2022. Available at https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.9"},{"key":"742_CR18","doi-asserted-by":"crossref","unstructured":"Petriu, E.M.: Absolute-type position transducers using a pseudorandom encoding. IEEE Transactions on Instrumentation and Measurement, IM-36:950\u2013955 (1987)","DOI":"10.1109\/TIM.1987.6312588"},{"key":"742_CR19","unstructured":"Ronse, C.: Feedback Shift Registers, volume 169 of Lecture Notes in Computer Science. Springer (1984)"},{"key":"742_CR20","unstructured":"Sawada, J.,\u00a0Sears, J.,\u00a0Trautrim, A.,\u00a0Williams, A.: Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions (2023). Available at https:\/\/arxiv.org\/abs\/2308.12405"},{"key":"742_CR21","doi-asserted-by":"crossref","unstructured":"Szentandr\u00e1si, I.,\u00a0Zachari\u00e1s, M.,\u00a0Havel, J.,\u00a0Herout, A., Dubsk\u00e1, M.,\u00a0Kajan, R.: Uniform marker fields: Camera localization by orientable De Bruijn tori. In: 11th IEEE International Symposium on Mixed and Augmented Reality, ISMAR 2012, Atlanta, GA, USA, November 5\u20138, 2012, pages 319\u2013320. IEEE Computer Society (2012)","DOI":"10.1109\/ISMAR.2012.6402593"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-024-00742-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-024-00742-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-024-00742-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T16:20:10Z","timestamp":1737476410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-024-00742-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,2]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["742"],"URL":"https:\/\/doi.org\/10.1007\/s12095-024-00742-x","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,2]]},"assertion":[{"value":"25 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2024","order":3,"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":"Competing interests"}}]}}