Polynomial-Time Program Equivalence for Machine Knitting
Open Access
- 5 August 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (ICFP) , 371-399
Abstract
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.Keywords
Funding Information
- National Science Foundation (2319181, 2319182)
This publication has 23 references indexed in Scilit:
- 3D Knitting for Pneumatic Soft RoboticsAdvanced Functional Materials, 2023
- A compiler for 3D machine knittingACM Transactions on Graphics, 2016
- Rewriting modulo symmetric monoidal structure2016
- Knottedness is in, modulo GRHAdvances in Mathematics, 2014
- A Survey of Graphical Languages for Monoidal Categories2010
- Efficient solutions to the braid isotopy problemDiscrete Applied Mathematics, 2008
- The computational complexity of knot and link problemsJournal of the ACM, 1999
- A Study of Braids1999
- The geometry of tensor calculus, IAdvances in Mathematics, 1991
- AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON1971