{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:56:53Z","timestamp":1780675013202,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1955444"],"award-info":[{"award-number":["1955444"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>\n            Machine knitting is a well-established fabrication technique for complex soft objects, and both companies and researchers have developed tools for generating machine knitting patterns. However, existing representations for machine knitted objects are incomplete (do not cover the complete domain of machine knittable objects) or overly specific (do not account for symmetries and equivalences among knitting instruction sequences). This makes it difficult to define correctness in machine knitting, let alone verify the correctness of a given program or program transformation. The major contribution of this work is a formal semantics for knitout, a low-level Domain Specific Language for knitting machines. We accomplish this by using what we call the\n            <jats:italic>fenced tangle<\/jats:italic>\n            , which extends concepts from knot theory to allow for a mathematical definition of knitting program equivalence that matches the intuition behind knit objects. Finally, using this formal representation, we prove the correctness of a sequence of rewrite rules; and demonstrate how these rewrite rules can form the foundation for higher-level tasks such as compiling a program for a specific machine and optimizing for time\/reliability, all while provably generating the same knit object under our proposed semantics. By establishing formal definitions of correctness, this work provides a strong foundation for compiling and optimizing knit programs.\n          <\/jats:p>","DOI":"10.1145\/3592449","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T14:29:21Z","timestamp":1690381761000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Semantics and Scheduling for Machine Knitting Compilers"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8618-0740","authenticated-orcid":false,"given":"Jenny","family":"Lin","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8497-8191","authenticated-orcid":false,"given":"Vidya","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Amazon, Seattle, Washington, United States of America"},{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5255-0918","authenticated-orcid":false,"given":"Yuka","family":"Ikarashi","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6243-9543","authenticated-orcid":false,"given":"Jonathan","family":"Ragan-Kelley","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3016-1169","authenticated-orcid":false,"given":"Gilbert","family":"Bernstein","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, Washington, United States of America"}],"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, Pennsylvania, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"The Knot Book","author":"Adams C.C.","unstructured":"C.C. Adams. 1994. The Knot Book. W.H. Freeman, New York, NY."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3526113.3545694"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290605.3300414"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3411764.3445564"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/17513470902896561"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-end Optimizing Compiler for Deep Learning. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI'18). USENIX Association, Berkeley, CA, USA, 579--594. http:\/\/dl.acm.org\/citation.cfm?id=3291168.3291211"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786784.2786801"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434322"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1177\/0040517508095600"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/503502.503505"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523446"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3488006"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.3390\/textiles2020015"},{"key":"e_1_2_2_14_1","volume-title":"Breen","author":"Kapllani Levi","year":"2021","unstructured":"Levi Kapllani, Chelsea Amanatides, Genevi\u00e8ve Dion, Vadim Shapiro, and David E. Breen. 2021. TopoKnit : A Process-Oriented Representation for Modeling the Topology of Yarns in Weft-Knitted Textiles. CoRR abs\/2101.04560 (2021), 22 pages. arXiv:2101.04560 https:\/\/arxiv.org\/abs\/2101.04560"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332165.3347879"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"3281","author":"Kaspar Alexandre","year":"2019","unstructured":"Alexandre Kaspar, Tae-Hyun Oh, Liane Makatura, Petr Kellnhofer, and Wojciech Ma-tusik. 2019b. Neural Inverse Knitting: From Images to Manufacturing Instructions. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, Long Beach, California, USA, 3272--3281."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459752"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-3-1-182-199"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459853"},{"key":"e_1_2_2_20_1","volume-title":"CompCert - A Formally Verified Optimizing Compiler. In ERTS 2016: Embedded Real Time Software and Systems. SEE","author":"Leroy Xavier","year":"2016","unstructured":"Xavier Leroy, Sandrine Blazy, Daniel K\u00e4stner, Bernhard Schommer, Markus Pister, and Christian Ferdinand. 2016. CompCert - A Formally Verified Optimizing Compiler. In ERTS 2016: Embedded Real Time Software and Systems. SEE, Toulouse, France. http:\/\/xavierleroy.org\/publi\/erts2016_compcert.pdf"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9562113"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213512.3213515"},{"key":"e_1_2_2_23_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--112. http:\/\/archive.bridgesmathart.org\/2020\/bridges2020-103.html"},{"key":"e_1_2_2_24_1","unstructured":"James McCann. 2017. The \"Knitout\" (.k) File Format. [Online]. Available from: https:\/\/textiles-lab.github.io\/knitout\/knitout.html."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925940"},{"key":"e_1_2_2_26_1","unstructured":"J.R. Munkres. 2000. Topology. Prentice Hall Incorporated. https:\/\/books.google.com\/books?id=XjoZAQAAIAAJ"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459790"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186265"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322995"},{"key":"e_1_2_2_30_1","volume-title":"Joseph Paradiso, and Hiroshi Ishii.","author":"Ou Jifei","year":"2019","unstructured":"Jifei Ou, Daniel Oran, Don Derek Haddad, Joseph Paradiso, and Hiroshi Ishii. 2019. SensorKnit: Architecting textile sensors with machine knitting. 3D Printing and Additive Manufacturing 6, 1 (2019), 1--11."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.istruc.2020.02.013"},{"key":"e_1_2_2_32_1","volume-title":"Tom Van Mele, and Philippe Block","author":"Popescu Mariana","year":"2018","unstructured":"Mariana Popescu, Matthias Rippmann, Tom Van Mele, and Philippe Block. 2018. Automated Generation of Knit Patterns for Non-developable Surfaces. In Humanizing Digital Reality, De Rycke K. et al. (Ed.). Springer, Singapore."},{"key":"e_1_2_2_33_1","volume-title":"The fabric of civilization : how textiles made the world","author":"Postrel Virginia","unstructured":"Virginia Postrel. 2020. The fabric of civilization : how textiles made the world. Basic Books, Hachette Book Group, New York."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459778"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_2_2_36_1","volume-title":"Mathematical Models of Rigid Solid Objects. Production Automation Project","author":"Requicha Aristides A.G.","year":"1977","unstructured":"Aristides A.G. Requicha. 1977. Mathematical Models of Rigid Solid Objects. Production Automation Project, University of Rochester, Rochester, New York 14627 28 (1977), 74 pages."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/adfm.202212541"},{"key":"e_1_2_2_38_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_39_1","unstructured":"Shima Seiki. 2019. SDS-ONE Apex4. [Online]. Available from: https:\/\/www.shimaseiki.com\/product\/design\/."},{"key":"e_1_2_2_40_1","unstructured":"Soft Byte Ltd. 1999. Designaknit. [Online]. Available from: https:\/\/www.softbyte.co.uk\/designaknit.htm."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3049832.3049841"},{"key":"e_1_2_2_42_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_43_1","volume-title":"The design of 3D shape knitted preforms. Ph. D. Dissertation. Fashion and Textiles","author":"Underwood Jenny","unstructured":"Jenny Underwood. 2009. The design of 3D shape knitted preforms. Ph. D. Dissertation. Fashion and Textiles, RMIT University."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356518"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508499"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592449","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592449","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592449","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:59Z","timestamp":1750182539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1145\/3592449"],"URL":"https:\/\/doi.org\/10.1145\/3592449","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"2023-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}