  Algorithms which learn environments represented by automata in the past have
had complexity scaling with the number of states in the automaton, which can be
exponentially large even for automata recognizing regular expressions with a
small description length. We thus formalize a compositional language that can
construct automata as transformations between certain types of category,
representable as string diagrams, which better reflects the description
complexity of various automata. We define complexity constraints on this
framework by having them operate on categories enriched over filtered sets, and
using these constraints, we prove elementary results on the runtime and
expressivity of a subset of these transformations which operate
deterministically on finite state spaces. These string diagrams, or "string
machines," are themselves morphisms in a category, so it is possible for string
machines to create other string machines in runtime to model computations which
take more than constant memory. We prove sufficient conditions for polynomial
runtime guarantees on these, which can help develop complexity constraints on
string machines which also encapsulate runtime complexity.
