{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:49:50Z","timestamp":1790927390023,"version":"4.1.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T00:00:00Z","timestamp":1754352000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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":1,"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,8,5]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935316"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498667"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3609023.3609803"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.12.009"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"J. M. Egger. 2011. On Involutive Monoidal Categories. Theory and Applications of Categories 25 (2011) 368\u2013393. http:\/\/www.tac.mta.ca\/tac\/volumes\/25\/14\/25-14.pdf","DOI":"10.70930\/tac\/ill9238y"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3661814.3662098"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3654777.3676405"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"John Hopcroft. 1971. An n log n algorithm for minimizing states in a finite automaton. In Theory of Machines and Computations Zvi Kohavi and Azaria Paz (Eds.). Academic Press Cambridge MA USA 189\u2013196. doi:10.1016\/B978-0-12-417750-5.50022-1","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(91)90003-P"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.01.007"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3592449"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3687948"},{"key":"e_1_3_2_15_2","unstructured":"Logica. 2023. PaintKnit. [Online]. Available from: https:\/\/www.paintknit.com"},{"key":"e_1_3_2_16_2","first-page":"103","article-title":"Knotty Knits are Tangles in Tori","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\u0f3f Fenyvesi (Eds.). Tessellations Publishing, Phoenix, Arizona, 103\u2013112. http:\/\/archive.bridgesmathart.org\/2020\/bridges2020-103.html","journal-title":"Proceedings of Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925940"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591262"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9319-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236794"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186265"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/adfm.202212541"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12821-9_4"},{"key":"e_1_3_2_24_2","unstructured":"Shima Seiki. 2011. SDS-ONE Apex3. [Online]. Available from: http:\/\/www.shimaseiki.com\/product\/design\/sdsone_apex\/flat\/"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3677998.3678221"},{"key":"e_1_3_2_26_2","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_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3704837"},{"key":"e_1_3_2_28_2","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":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:00:36Z","timestamp":1784196036000},"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":[{"value":"2475-1421","type":"electronic"}],"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"}}]}}