This was a project conducted during MATS 5.0 under the mentorship of Vanessa Kosoy and supported by a grant from BERI. It builds off the String Machines framework (and depends on the linked post for certain definitions), which models category-theoretic generalizations of finite-state transducers. [EDIT: The results here can also be found presented in self-contained form, in this paper.]

The framework as it previously existed did not have representation-independent ways of bounding (analogues of) time complexity, or natural guarantees that output size would not grow exponentially in input size. We introduce "filtered" transducers, which operate on categories enriched over filtered sets (sets equipped with a function to a partially ordered monoid, where morphisms are functions respecting order), and then, restricting our attention to transducers with a finite state space, prove constraints on the time complexity growth and expressivity of string machines.

Parameterizing complexity in string machines

Filtered transducers

Definition 1. The category $F i l t S e t$ of filtered sets is the category such that
an object is a tuple $(S, {deg}_{S})$ , where $S$ is a set and ${deg}_{S} : S \to N$ is a function,
a morphism $f : (S, {deg}_{S}) \to (T, {deg}_{T})$ is a function $S \to T$ such that ${deg}_{T} (f (s)) \leq {deg}_{S} (s)$ for all $s \in S$ .

We will generally refer to objects in $F i l t S e t$ solely by the symbol corresponding to the underlying set going forward. One can observe that the identity function on a set $S$ by definition satisfies ${deg}_{S} ({i d}_{S} (s)) = {deg}_{S} (s)$ for all $s \in S$ and is thus a morphism in $F i l t S e t$ . One can also observe that given $f : S \to T$ and $g : T \to V$ , ${deg}_{V} (g (f (s))) \leq {deg}_{T} (f (s)) \leq {deg}_{S} (s)$ for all $s \in S$ , and therefore $g \circ f$ is also a morphism in $F i l t S e t$ . Therefore, $F i l t S e t$ is indeed a category.

Definition 2. Given two objects $S, T \in O b (F i l t S e t)$ , we define their filtered product $S \otimes T$ to be the set $S \times T$ equipped with the function ${deg}_{S \otimes T} : S \times T \to N$ satisfying ${deg}_{S \otimes T} (s, t) = {deg}_{S} (s) + {deg}_{T} (t)$ for all $(s, t) \in S \times T$ . Given a morphism $f : S \to U$ and a morphism $g : T \to V$ , we define the morphism $f \otimes g : S \otimes T \to U \otimes V$ to be the function $f \times g$ . Indeed, we have that ${deg}_{U \otimes V} (f (s), g (t)) = {deg}_{U} (f (s)) + {deg}_{V} (g (t)) \leq {deg}_{S} (s) + {deg}_{T} (t) = {deg}_{S \otimes T} (s, t)$ , so $f \otimes g$ is a morphis

...

Posts

Wikitag Contributions

Comments