{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T00:27:57Z","timestamp":1755217677427,"version":"3.43.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2319181, 2319182"],"award-info":[{"award-number":["2319181, 2319182"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,8,5]]},"abstract":"<jats:p>We present an algorithm that canonicalizes the algebraic representations of the topological semantics of machine knitting programs. Machine knitting is a staple technology of modern textile production where hundreds of mechanical needles are manipulated to form yarn into interlocking loop structures. Our semantics are defined using a variant of a monoidal category, and they closely correspond to string diagrams. We formulate our canonicalization as an Abstract Rewriting System (ARS) over words in our category, and prove that our algorithm is correct and runs in polynomial time.<\/jats:p>","DOI":"10.1145\/3747517","type":"journal-article","created":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T16:56:02Z","timestamp":1754412962000},"page":"371-399","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Program Equivalence for Machine Knitting"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0988-1401","authenticated-orcid":false,"given":"Nathan","family":"Hurtig","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8618-0740","authenticated-orcid":false,"given":"Jenny Han","family":"Lin","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7356-2109","authenticated-orcid":false,"given":"Thomas S.","family":"Price","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2464-0876","authenticated-orcid":false,"given":"Adriana","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4231-4142","authenticated-orcid":false,"given":"James","family":"McCann","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3016-1169","authenticated-orcid":false,"given":"Gilbert Louis","family":"Bernstein","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935316"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498667"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3609023.3609803"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.12.009"},{"key":"e_1_2_2_5_1","first-page":"368","article-title":"On Involutive Monoidal Categories","volume":"25","author":"Egger J. M.","year":"2011","unstructured":"J. M. Egger. 2011. On Involutive Monoidal Categories. Theory and Applications of Categories, 25 (2011), 368\u2013393. issn:1201-561X http:\/\/www.tac.mta.ca\/tac\/volumes\/25\/14\/25-14.pdf","journal-title":"Theory and Applications of Categories"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3661814.3662098"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654777.3676405"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(91)90003-P"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.01.007"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592449"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687948"},{"key":"e_1_2_2_14_1","unstructured":"Logica. 2023. PaintKnit. [Online]. Available from:. https:\/\/www.paintknit.com"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture, Carolyn Yackel, Robert Bosch, Eve Torrence, and Krist\u00f3f Fenyvesi (Eds.)","author":"Markande Shashank G","year":"2020","unstructured":"Shashank G Markande and Elisabetta Matsumoto. 2020. Knotty Knits are Tangles in Tori. In Proceedings of Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture, Carolyn Yackel, Robert Bosch, Eve Torrence, and Krist\u00f3f Fenyvesi (Eds.). Tessellations Publishing, Phoenix, Arizona. 103\u2013112. isbn:978-1-938664-36-6 issn:1099-6702 http:\/\/archive.bridgesmathart.org\/2020\/bridges2020-103.html"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925940"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591262"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"K. Murasugi and B. Kurpita. 1999. A Study of Braids. Springer Netherlands Norwell MA USA. isbn:9780792357674 lccn:99027052 https:\/\/books.google.com\/books?id=tbi_FDbSJo0C","DOI":"10.1007\/978-94-015-9319-9"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236794"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186265"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/adfm.202212541"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12821-9_4"},{"key":"e_1_2_2_23_1","unstructured":"Shima Seiki. 2011. SDS-ONE Apex3. [Online]. Available from:. http:\/\/www.shimaseiki.com\/product\/design\/sdsone_apex\/flat\/"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677998.3678221"},{"key":"e_1_2_2_25_1","unstructured":"Stoll. 2011. M1Plus pattern software. [Online]. Available from:. http:\/\/www.stoll.com\/stoll_software_solutions_en_4\/pattern_software_m1plus\/3_1"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3704837"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3609023.3609805"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T16:56:59Z","timestamp":1754413019000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,5]]},"references-count":27,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2025,8,5]]}},"alternative-id":["10.1145\/3747517"],"URL":"https:\/\/doi.org\/10.1145\/3747517","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,8,5]]},"assertion":[{"value":"2025-02-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}