{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T15:10:37Z","timestamp":1721920237314},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T00:00:00Z","timestamp":1716336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T00:00:00Z","timestamp":1716336000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s00453-024-01237-0","type":"journal-article","created":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T02:01:25Z","timestamp":1716343285000},"page":"2605-2624","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parity Permutation Pattern Matching"],"prefix":"10.1007","volume":"86","author":[{"given":"Virginia Ard\u00e9vol","family":"Mart\u00ednez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"issue":"5","key":"1237_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998)","journal-title":"Inf. Process. Lett."},{"key":"1237_CR2","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2022)"},{"key":"1237_CR3","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Vialette, S.: Pattern matching for 321-avoiding permutations. In: Proceeding of ISAAC, vol. 5878 of LNCS, pp. 1064\u20131073. Springer (2009)","DOI":"10.1007\/978-3-642-10631-6_107"},{"key":"1237_CR4","doi-asserted-by":"crossref","unstructured":"Albert, M.H., Lackner, M., Lackner, M., Vatter, V.: The complexity of pattern matching for 321-avoiding and skew-merged permutations. Discret. Math. Theor. Comput. Sci. 18(2) (2016)","DOI":"10.46298\/dmtcs.1308"},{"key":"1237_CR5","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Rizzi, R., Vialette, S.: Pattern matching for k-track permutations. In: Iliopoulos, C.S., Leong, H.W., Sung, W. (eds.) Combinatorial Algorithms\u201429th International Workshop, IWOCA 2018, Singapore, Proceedings. vol. 10979 of Lecture Notes in Computer Science, pp. 102\u2013114. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-94667-2_9","DOI":"10.1007\/978-3-319-94667-2_9"},{"key":"1237_CR6","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Kyn\u010dl, J.: Hardness of permutation pattern matching. In: Proceedings of SODA, pp. 378\u2013396. SIAM (2017)","DOI":"10.1137\/1.9781611974782.24"},{"key":"1237_CR7","unstructured":"Jel\u00ednek, V., Opler, M., Pek\u00e1rek, J.: Griddings of permutations and hardness of pattern matching. In: Proceedings of MFCS. vol. 202 of LIPIcs, pp. 65:1\u201365:22 (2021)"},{"issue":"2","key":"1237_CR8","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/S0895480104444776","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discrete Math. 22(2), 629\u2013649 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"8","key":"1237_CR9","doi-asserted-by":"publisher","first-page":"2552","DOI":"10.1007\/s00453-021-00812-z","volume":"83","author":"BA Berendsohn","year":"2021","unstructured":"Berendsohn, B.A., Kozma, L., Marx, D.: Finding and counting permutations via CSPs. Algorithmica 83(8), 2552\u20132577 (2021)","journal-title":"Algorithmica"},{"key":"1237_CR10","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Rzepecki, M.: Faster exponential algorithm for permutation pattern matching. In: 5th SOSA@SODA 2022, pp. 279\u2013284. SIAM (2022)","DOI":"10.1137\/1.9781611977066.21"},{"issue":"1","key":"1237_CR11","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/s00453-015-0013-y","volume":"75","author":"M Bruner","year":"2016","unstructured":"Bruner, M., Lackner, M.: A fast algorithm for permutation pattern matching based on alternating runs. Algorithmica 75(1), 84\u2013117 (2016)","journal-title":"Algorithmica"},{"key":"1237_CR12","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of SODA, pp. 82\u2013101. SIAM (2014)","DOI":"10.1137\/1.9781611973402.7"},{"key":"1237_CR13","unstructured":"Fox, J.: Stanley-Wilf limits are typically exponential. Preprint at arXiv:1310.8378 (2013)"},{"issue":"1","key":"1237_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3486655","volume":"69","author":"\u00c9 Bonnet","year":"2022","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM 69(1), 1\u201346 (2022)","journal-title":"J. ACM"},{"key":"1237_CR15","doi-asserted-by":"crossref","unstructured":"Kitaev, S.: Patterns in permutations and words. In: Monographs in Theoretical Computer Science. An EATCS Series. Springer (2011)","DOI":"10.1007\/978-3-642-17333-2"},{"key":"1237_CR16","unstructured":"Bruner, M.L., Lackner, M.: The computational landscape of permutation patterns. In: Pure Mathematics and Applications: Special Issue for the Permutation Patterns 2012 Conference, vol. 24, no. 2, pp. 83\u2013101 (2013)"},{"key":"1237_CR17","unstructured":"Alexandersson, P., Fufa, S.A., Getachew, F., Qiu, D.: Pattern-avoidance and Fuss-Catalan numbers. Preprint at arXiv:2201.08168 (2022)"},{"key":"1237_CR18","unstructured":"Bulteau, L., Fertin, G., Jug\u00e9, V., Vialette, S.: Permutation pattern matching for doubly partially ordered patterns. In: Proceedings of CPM, vol. 223 of LIPIcs, p. 21:1\u201321:17 (2022)"},{"issue":"3","key":"1237_CR19","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.aam.2009.07.002","volume":"44","author":"S Tanimoto","year":"2010","unstructured":"Tanimoto, S.: Combinatorics of the group of parity alternating permutations. Adv. Appl. Math. 44(3), 225\u2013230 (2010)","journal-title":"Adv. Appl. Math."},{"key":"1237_CR20","doi-asserted-by":"crossref","unstructured":"Gil, J.B., Tomasko, J.A.: Restricted Grassmannian permutations. Enumerative Combinatorics and Applications. 2(4):#S4PP6 (2021)","DOI":"10.54550\/ECA2022V2S4PP6"},{"key":"1237_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00026-007-0313-2","volume":"11","author":"S Kitaev","year":"2007","unstructured":"Kitaev, S., Remmel, J.: Classifying descents according to parity. Ann. Comb. 11, 173\u2013193 (2007)","journal-title":"Ann. Comb."},{"key":"1237_CR22","doi-asserted-by":"crossref","unstructured":"Ard\u00e9vol\u00a0Mart\u00ednez, V., Sikora, F., Vialette, S.: Parity permutation pattern matching. In: Lin, C., Lin, B.M.T., Liotta, G. (eds.) WALCOM: Algorithms and Computation\u201417th International Conference and Workshops, WALCOM 2023, Hsinchu, Proceedings. vol. 13973 of Lecture Notes in Computer Science, pp. 384\u2013395. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-27051-2_32","DOI":"10.1007\/978-3-031-27051-2_32"},{"key":"1237_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al.: Parameterized Algorithms. Springer (2015)"},{"issue":"2","key":"1237_CR24","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., et al.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"key":"1237_CR25","doi-asserted-by":"crossref","unstructured":"Neou, B.E., Rizzi, R., Vialette, S.: Permutation Pattern matching in (213, 231)-avoiding permutations. Discrete Math. Theor. Comput. Sci. 18(2) (2016)","DOI":"10.46298\/dmtcs.1329"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01237-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01237-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01237-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T14:41:20Z","timestamp":1721918480000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01237-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,22]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1237"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01237-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,22]]},"assertion":[{"value":"12 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 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 have no Conflict of interest related to this publication.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}