{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:37:21Z","timestamp":1743039441152,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031270505"},{"type":"electronic","value":"9783031270512"}],"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-27051-2_32","type":"book-chapter","created":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:03:35Z","timestamp":1678665815000},"page":"384-395","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parity Permutation Pattern Matching"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3703-2335","authenticated-orcid":false,"given":"Virginia","family":"Ard\u00e9vol Mart\u00ednez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2670-6258","authenticated-orcid":false,"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2308-6970","authenticated-orcid":false,"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"issue":"2","key":"32_CR1","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."},{"key":"32_CR2","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. Discrete Math. Theor. Comput. Sci. 18(2) (2016)","DOI":"10.46298\/dmtcs.1308"},{"key":"32_CR3","unstructured":"Alexandersson, P., Fufa, S.A., Getachew, F., Qiu, D.: Pattern-avoidance and fuss-catalan numbers. arXiv preprint. arXiv:2201.08168 (2022)"},{"issue":"8","key":"32_CR4","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). https:\/\/doi.org\/10.1007\/s00453-021-00812-z","journal-title":"Algorithmica"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM 69(1), 3:1\u20133:46 (2022)","DOI":"10.1145\/3486655"},{"issue":"5","key":"32_CR6","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":"32_CR7","unstructured":"Bruner, M.L., Lackner, M.: The computational landscape of permutation patterns. Pure Mathematics and Applications: Special Issue for the Permutation Patterns 2012 Conference, vol. 24, no. 2, pp. 83\u2013101 (2013)"},{"issue":"1","key":"32_CR8","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). https:\/\/doi.org\/10.1007\/s00453-015-0013-y","journal-title":"Algorithmica"},{"key":"32_CR9","unstructured":"Bulteau, L., Fertin, G., Jug\u00e9, V., Vialette, S.: Permutation pattern matching for doubly partially ordered patterns. In: Proceedings of the CPM. LIPIcs, vol. 223, pp. 21:1\u201321:17 (2022)"},{"key":"32_CR10","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, Cambridge (2022)"},{"key":"32_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"32_CR12","unstructured":"Fox, J.: Stanley-wilf limits are typically exponential. arXiv preprint. arXiv:1310.8378 (2013)"},{"key":"32_CR13","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"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Gil, J.B., Tomasko, J.A.: Restricted Grassmannian permutations. Enumerative Comb. Appl. 2(4), #S4PP6 (2021)","DOI":"10.54550\/ECA2022V2S4PP6"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the SODA, pp. 82\u2013101. SIAM (2014)","DOI":"10.1137\/1.9781611973402.7"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1007\/978-3-642-10631-6_107","volume-title":"Algorithms and Computation","author":"S Guillemot","year":"2009","unstructured":"Guillemot, S., Vialette, S.: Pattern matching for 321-avoiding permutations. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 1064\u20131073. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_107"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Kyn\u010dl, J.: Hardness of permutation pattern matching. In: Proceedings of the SODA, pp. 378\u2013396. SIAM (2017)","DOI":"10.1137\/1.9781611974782.24"},{"key":"32_CR18","unstructured":"Jel\u00ednek, V., Opler, M., Pek\u00e1rek, J.: Griddings of permutations and hardness of pattern matching. In: Proceedings of the MFCS. LIPIcs, vol. 202, pp. 65:1\u201365:22 (2021)"},{"key":"32_CR19","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17333-2","volume-title":"Patterns in Permutations and Words","author":"S Kitaev","year":"2011","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series, Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-17333-2"},{"issue":"3","key":"32_CR20","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."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-27051-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:06:51Z","timestamp":1678666011000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-27051-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031270505","9783031270512"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-27051-2_32","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":"13 March 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hsinchu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","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":"22 March 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.walcom2023.conf.nycu.edu.tw\/","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":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"75","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":"30","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":"40% - 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":"10","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)"}},{"value":"This proceeding includes 2 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}