{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:07:50Z","timestamp":1787652470019,"version":"build-2736575974"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T00:00:00Z","timestamp":1671840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T00:00:00Z","timestamp":1671840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TU Wien"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this note we answer positively an open question posed by Yuster in 2020 [14] on the polynomial boundedness of the <jats:italic>perfect sequence covering array number<\/jats:italic><jats:inline-formula><jats:alternatives><jats:tex-math>$$g(n,k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>g<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (PSCA number). The latter determines the (renormalized) minimum row-count that <jats:italic>perfect sequence covering arrays<\/jats:italic> (PSCAs) can possess. PSCAs are matrices with permutations in <jats:inline-formula><jats:alternatives><jats:tex-math>$$S_n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>S<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> as rows, such that each ordered <jats:italic>k<\/jats:italic>-sequence of distinct elements of <jats:inline-formula><jats:alternatives><jats:tex-math>$$[n]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is covered by the same number of rows. We obtain the result after illuminating an isomorphism between this structure from design theory and a special case of min-wise independent permutations. Afterwards, we point out that asymptotic bounds and constructions can be transferred between these two structures. Moreover, we sharpen asymptotic lower bounds for <jats:italic>g<\/jats:italic>(<jats:italic>n<\/jats:italic>,\u00a0<jats:italic>k<\/jats:italic>) and improve upper bounds for <jats:italic>g<\/jats:italic>(<jats:italic>n<\/jats:italic>,\u00a04) and <jats:italic>g<\/jats:italic>(<jats:italic>n<\/jats:italic>,\u00a03), for some concrete values of <jats:italic>n<\/jats:italic>. We conclude with some open questions and propose a new matrix class being potentially advantageous for searching PSCAs.<\/jats:p>","DOI":"10.1007\/s10623-022-01168-3","type":"journal-article","created":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T12:02:36Z","timestamp":1671883356000},"page":"1487-1494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Growth of the perfect sequence covering array number"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7528-0834","authenticated-orcid":false,"given":"Enrico","family":"Iurlano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,12,24]]},"reference":[{"key":"1168_CR1","unstructured":"Bargachev V.: An improved lower bound on the size of $$k$$-rankwise independent families of permutations. Preprint on website of St. Petersburg Department of Steklov Institute of Mathematics. https:\/\/www.pdmi.ras.ru\/preprint\/2004\/04-13.html (2004)."},{"key":"1168_CR2","unstructured":"Brain M., Erdem E., Inoue K., Oetsch J., P\u00fchrer J., Tompits H., Yilmaz C.: Event-sequence testing using answer-set programming. Int. J. Adv. Softw. 5(3 &4) (2012)."},{"issue":"3","key":"1168_CR3","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"AZ Broder","year":"2000","unstructured":"Broder A.Z., Charikar M., Frieze A.M., Mitzenmacher M.: Min-wise independent permutations. J. Comput. Syst. Sci. 60(3), 630\u2013659 (2000).","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1168_CR4","doi-asserted-by":"publisher","first-page":"1844","DOI":"10.1137\/120894099","volume":"27","author":"YM Chee","year":"2013","unstructured":"Chee Y.M., Colbourn C.J., Horsley D., Zhou J.: Sequence covering arrays. SIAM J. Discret. Math. 27(4), 1844\u20131861 (2013).","journal-title":"SIAM J. Discret. Math."},{"key":"1168_CR5","doi-asserted-by":"crossref","unstructured":"Gentle A.R., Wanless I.M.: On perfect sequence covering arrays. Ann. Combinat. (2022).","DOI":"10.1007\/s00026-022-00610-6"},{"key":"1168_CR6","unstructured":"Itoh T., Takei Y., Tarui J.: On permutations with limited independence. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 137\u2013146 (2000)."},{"key":"1168_CR7","unstructured":"Iurlano E.: Scrambling permutations and related structures. Master\u2019s thesis, TU Wien, Austria (2022). https:\/\/repositum.tuwien.at\/handle\/20.500.12708\/101832"},{"key":"1168_CR8","doi-asserted-by":"crossref","unstructured":"Kuhn D.R., Higdon J.M., Lawrence J.F., Kacker R.N., Lei Y.: Combinatorial methods for event sequence testing. In: 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, pp. 601\u2013609. IEEE (2012).","DOI":"10.1109\/ICST.2012.147"},{"key":"1168_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/dma.1992.2.3.241","volume":"2","author":"VI Levenshtein","year":"1992","unstructured":"Levenshtein V.I.: On perfect codes in deletion and insertion metric. Discret. Math. Appl. 2, 241\u2013258 (1992).","journal-title":"Discret. Math. Appl."},{"key":"1168_CR10","unstructured":"Na J.: Perfect sequence covering arrays. Master\u2019s thesis, Simon Fraser University, Canada (2021). https:\/\/theses.lib.sfu.ca\/6570\/show"},{"key":"1168_CR11","unstructured":"Na J., Jedwab J., Li S.: A group-based structure for perfect sequence covering arrays. Designs Codes Cryptogr. (to appear)."},{"issue":"3\u20134","key":"1168_CR12","first-page":"349","volume":"22","author":"J Spencer","year":"1971","unstructured":"Spencer J.: Minimal scrambling sets of simple orders. Acta Math. Hungar. 22(3\u20134), 349\u2013353 (1971).","journal-title":"Acta Math. Hungar."},{"key":"1168_CR13","doi-asserted-by":"crossref","unstructured":"Tarui J., Itoh T., Takei Y.: A nearly linear size 4-min-wise independent permutation family by finite geometries. In: Arora S., Jansen K., Rolim J.D.P., Sahai A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 396\u2013408. Springer, Berlin, Heidelberg (2003).","DOI":"10.1007\/978-3-540-45198-3_33"},{"issue":"3","key":"1168_CR14","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/s10623-019-00698-7","volume":"88","author":"R Yuster","year":"2020","unstructured":"Yuster R.: Perfect sequence covering arrays. Des. Codes Crypt. 88(3), 585\u2013593 (2020).","journal-title":"Des. Codes Crypt."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01168-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01168-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01168-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T07:04:30Z","timestamp":1680678270000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01168-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,24]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1168"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01168-3","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,24]]},"assertion":[{"value":"5 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2022","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 author has no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}