Time complexity for deterministic string machines

post by alcatal · 2024-04-21T22:35:36.062Z · LW · GW · 0 comments

Contents

  Parameterizing complexity in string machines
    Filtered transducers
    Finite-state string machines
      String machine description length
    The expressivity of finite-state string machines
      Without a meta-vertex
      With a meta-vertex
  Conclusions
    Further work
      Description complexity that encapsulates time complexity
      Characterizing the expressivity of transducers with a meta-vertex and monadic transducers
None
No comments

This was a project conducted during MATS 5.0 under the mentorship of Vanessa Kosoy [LW · GW] and supported by a grant from BERI. It builds off the String Machines [AF · GW] framework (and depends on the linked post for certain definitions), which models category-theoretic generalizations of finite-state transducers.

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 $FiltSet$ of filtered sets is the category such that

• an object is a tuple $(S,{\mathrm{deg}}_S)$, where $S$ is a set and ${\mathrm{deg}}_S:S\to N$ is a function,
• a morphism $f:(S,{\mathrm{deg}}_S)\to (T,{\mathrm{deg}}_T)$ is a function $S\to T$ such that ${\mathrm{deg}}_T\left(f\right(s\left)\right)\le {\mathrm{deg}}_S\left(s\right)$ for all $s\in S$.

We will generally refer to objects in $FiltSet$ 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 ${\mathrm{deg}}_S\left({id}_S\right(s\left)\right)={\mathrm{deg}}_S\left(s\right)$ for all $s\in S$ and is thus a morphism in $FiltSet$. One can also observe that given $f:S\to T$ and $g:T\to V$, ${\mathrm{deg}}_V\left(g\right(f\left(s\right)\left)\right)\le {\mathrm{deg}}_T\left(f\right(s\left)\right)\le {\mathrm{deg}}_S\left(s\right)$ for all $s\in S$, and therefore $g\circ f$ is also a morphism in $FiltSet$. Therefore, $FiltSet$ is indeed a category.

Definition 2. Given two objects $S,T\in Ob\left(FiltSet\right)$, we define their filtered product $S\otimes T$ to be the set $S\times T$ equipped with the function ${\mathrm{deg}}_{S\otimes T}:S\times T\to N$ satisfying ${\mathrm{deg}}_{S\otimes T}(s,t)={\mathrm{deg}}_S\left(s\right)+{\mathrm{deg}}_T\left(t\right)$ 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 ${\mathrm{deg}}_{U\otimes V}\left(f\right(s),g(t\left)\right)={\mathrm{deg}}_U\left(f\right(s\left)\right)+{\mathrm{deg}}_V\left(g\right(t\left)\right)\le {\mathrm{deg}}_S\left(s\right)+{\mathrm{deg}}_T\left(t\right)={\mathrm{deg}}_{S\otimes T}(s,t)$, so $f\otimes g$ is a morphism in $FiltSet$.

Due to the associativity and commutativity of addition, as well as the natural associativity and commutativity (up to isomorphisms which are still isomorphisms in $FiltSet$) of the cartesian product, $-\otimes -$ is naturally associative and commutative up to isomorphism. Additionally, the one-element set $1$ equipped with ${\mathrm{deg}}_1(\cdot )=0$ and unitor maps which are the same as in $Set$ (which are, by their definition, filtered morphisms) provides a left and right unit for $-\otimes -$, making $FiltSet$ a symmetric monoidal category.

Remark. Suppose filtered sets $S,T,U$ and filtered morphisms $f:S\to T$ and $g:S\to U$. Then, the unique factoring function $S\to T\times U$ defined by $s\mapsto \left(f\right(s),g(s\left)\right)$ is only a filtered morphism $S\to T\otimes U$ if ${\mathrm{deg}}_T\left(f\right(s\left)\right)+{\mathrm{deg}}_U\left(g\right(s\left)\right)\le {\mathrm{deg}}_S\left(s\right)$, which does not hold in general. Therefore, $-\otimes -$ does not provide a product except for when at least one of the sets has degree uniformly zero. However, $FiltSet$ does have finite products $S\times T$ where ${\mathrm{deg}}_{S\times T}(s,t):=max\left({\mathrm{deg}}_S\right(s),{\mathrm{deg}}_T(t\left)\right)$. We will not be using this construction.

Remark. The set-theoretic disjoint union, with its degree function being the canonical factoring map to $N$ of its components' degree functions, provides all finite coproducts in $FiltSet$.

Definition 3. A filtered-morphism category $C$ is a locally small symmetric monoidal category enriched over $FiltSet$, using $FiltSet$'s filtered product $-\otimes -$ as its monoidal structure.

This expresses the notion of morphisms having degrees which are subadditive under composition in a way that naturally extends to a complexity constraint on transducers. As the monoidal identity of $FiltSet$ is the single-element set with degree zero, the arrows $I_{FiltSet}\to {Hom}_C(A,A)$ providing the identity morphism ${id}_A$ in the enrichment construction will ensure that identity morphisms are degree zero.

One can generalize the construction of $Filtset$ by replacing $N$ with any partially-ordered symmetric monoid (where the partial order is, obviously, translation-invariant as it is with the usual definition of a partially-ordered group). We will make use of categories filtered over $N^2$ (with the partial order given by $(a,b)\le (c,d)$ if and only if $a\le c$ and $b\le d$) in our construction of the filtered state category, as follows:

Definition 4. Given a filtered-morphism category $C$ and a list $\left\{\right(X_i\to Y_i,a_{i}x+b_i){\}}_i$ of $C$-signatures (generators) and linear polynomials with coefficients in $N$, the freely-generated $N^2$-filtered category over $C$ with this list of signatures, or $C[X_1\to Y_1,\dots ,X_n\to Y_n]$, is the symmetric monoidal category where:

• objects are exactly the objects of $C$.
• A morphism $f:X\to Y$ is either a morphism of $C$, or obtained by composing morphisms of $C$ with free generators added to ${Hom}_C(X_i,Y_i)$ for each $C$-signature $X_i\to Y_i$ in the list.
• The $N^2$-degree of a morphism $f$ is a linear polynomial with coefficients in $N$, which is either its degree in $C$ (expressed as a constant) if it is a $C$-morphism, the polynomial $a_{i}x+b_i$ if it is one of the generators $X_i\to Y_i$ added when creating the category, or the sum of the degrees of all morphisms involved in its composition, with the degree contributions of composition-chains of $C$-morphisms being the degrees in $C$ of the morphism they compose to, and these being strictly additive with each other and the degrees of any generator morphisms once all simplifications have been performed.
  
  The monoidal product of a morphism with generators in its composition-chain and a $C$-morphism is taken to have the sum of their $N^2$-degrees.

We can now introduce filtered state categories.

Definition 5. Given a filtered-morphism category $C$, its corresponding filtered state category $C^S$ is the category where

• an object $A$ is a tuple $\left(S\right(A),V_A,{\mathrm{deg}}_A)$, where:
  • The state space of $A$ is a set $S\left(A\right)$.
  • The variables of $A$ are a functor $V_A$ from the discrete category corresponding to $S\left(A\right)$ to the discrete category formed by all finite ordered tuples of pairs of objects $X,Y$ in $C$. We call the tuple associated with a given $x\in S\left(A\right)$ the variables at $x$, or $V_A\left(x\right)$. Since variables implicitly denote morphism signatures, we will refer to a given variable $(X,Y)\in V_A\left(x\right)$ as $X\to Y$.
  • The degree of a variable $X\to Y\in V_A\left(x\right)$ for some $x\in S\left(A\right)$, denoted ${\mathrm{deg}}_{A,x}(X\to Y)$ (or simply ${\mathrm{deg}}_A(X\to Y)$ if $x$ can be inferred from context) is a tuple $(a,b)\in N^2$. We impose the same partial ordering $\le$ on these tuples as we do with degrees in the freely-generated $N^2$-filtered categories.
• a morphism $f:A\to B$ of degree $\ell$, where $\ell \in N$, is a tuple $\left(S\right(f),V_f)$, where:
  • The state transition $S\left(f\right)$ is a function $S\left(A\right)\to S\left(B\right)$.
  • The output function at $x\in S\left(A\right)$, denoted $V_f\left(x\right)$, is a collection of morphisms in a freely-generated $N^2$-filtered category over $C$, defined as follows:
    
    For each variable $X_j^{\prime }\to Y_j^{\prime }$ of degree $a_j^{\prime }x+b_j^{\prime }$, at $S\left(f\right)\left(x\right)$, $V_f\left(x\right)$ defines a morphism $X_j^{\prime }\to Y_j^{\prime }$ of degree at most $a_j^{\prime }(x+\ell )+b_j^{\prime }=a_j^{\prime }x+(a_j^{\prime }\ell +b_j^{\prime })$ (that is, the degree of the morphism cannot exceed this polynomial in either of its terms) in the freely-generated $N^2$-filtered category over $C$ with generators and the degrees of those generators provided by the variables $X_i\to Y_i$ of degrees $a_{i}x+b_i$ in $V_A\left(x\right)$. The function between hom-sets in $C$ can then be expressed by substituting each generator with a $C$-morphism of the appropriate signature.
    
    This induces a function (but not a filtered one!) between the product of the hom-sets ${Hom}_C(X_i,Y_i)$ for all variables $X_i\to Y_i$ at $x$ and the product of the hom-sets ${Hom}_C(X_j^{\prime },Y_j^{\prime })$ for all variables $X_j^{\prime }\to Y_j^{\prime }$ at $S\left(f\right)\left(x\right)$, which can be obtained by replacing each generator corresponding to a variable at $x$ with a morphism of $C$ of the appropriate signature.
• Given two morphisms $f:A\to B$ of degree $\ell$ and $g:B\to C$ of degree ${\ell }^{\prime }$, their composition $g\circ f:A\to C$ is a tuple $\left(S\right(g\circ f),V_{g\circ f})$ where:
  • The composite state transition $S(g\circ f)$ is defined as $S\left(g\right)\circ S\left(f\right)$.
  • The composite output function $V_{g\circ f}\left(x\right)$ is defined as follows: For each variable $X_k^{\prime \prime }\to Y_k^{\prime \prime }$ defined at $S(g\circ f)\left(x\right)$, of degree $a_k^{\prime \prime }x+b_k^{\prime \prime }$, $V_g\left(S\right(f\left)\right(x\left)\right)$ defines a morphism of degree at most $a_k^{\prime \prime }(x+{\ell }^{\prime })+b_k^{\prime \prime }=a_k^{\prime \prime }x+(a_k^{\prime \prime }{\ell }^{\prime }+b_k^{\prime })$ in the category freely generated over $C$ with generators corresponding to the variables $\{X_j^{\prime }\to Y_j^{\prime }{\}}_j$ at $S\left(f\right)\left(x\right)$ and their degrees. Now, $V_f\left(x\right)$ induces a functor from $C[X_1^{\prime }\to Y_1^{\prime },\dots ]$ to $C[X_1\to Y_1,\dots ]$ (where $\{X_i\to Y_i{\}}_i$ denote the variables at $x$), which fixes $C$ but replaces every free generator of the category freely generated over the variables at $S\left(f\right)\left(x\right)$ with the morphism associated with it by $V_f\left(x\right)$, in the category freely generated over the variables at $x$. Therefore, the output function $V_{g\circ f}\left(x\right)$ at $x$ is simply the image of each of the morphisms generated by $V_g\left(x\right)$ under this functor defined by $V_f\left(x\right)$. The function between products of hom-sets induced by the composite output function is therefore just the composition of the functions induced by the individual morphisms' output functions.
    
    Now, for a given variable $X_k^{\prime \prime }\to Y_k^{\prime \prime }$ at $S(f\circ g)\left(x\right)$ of degree $a_k^{\prime \prime }x+b_k^{\prime \prime }$, every generator of some degree $a_j^{\prime }x+b_j^{\prime }$ involved in the morphism of (initial) degree $a_k^{\prime \prime }x+a_k^{\prime \prime }{\ell }^{\prime }+b_k^{\prime \prime }$ defined by $V_g\left(x\right)$ has been replaced with one of degree $a_j^{\prime }x+a_j^{\prime }\ell +b_j^{\prime }$. Suppose each generator $X_j^{\prime }\to Y_j^{\prime }$ appears with multiplicity $m_j^{\prime }$ in the morphism corresponding to $X_k^{\prime \prime }\to Y_k^{\prime \prime }$. Then, we have it that ${\sum }_j{m}_j{a}_j^{\prime }\le a_k^{\prime \prime }$, and since $a_j^{\prime }\ell$ worth of degree has been added to the morphism for every generator appearing in it, we have that the degree of the morphism generated by $V_{g\circ f}\left(x\right)$ must be $a_k^{\prime \prime }+a_k^{\prime \prime }{\ell }^{\prime }+b_k^{\prime \prime }+{\sum }_j{m}_j{a}_j^{\prime }\ell \le a_k^{\prime \prime }+a_k^{\prime \prime }(\ell +{\ell }^{\prime })+b_k^{\prime \prime }$. So, the degree of $g\circ f$ is $\ell +{\ell }^{\prime }$.

Remark. $C^S$ is a filtered-morphism category with the degrees of morphisms being defined as in the definition of the category, as the identity morphism of each object $A$ has an output function that outputs a variable of degree $ax+b$ (the generator corresponding to the variable itself) for any variable of degree $ax+b$ and is thus of degree zero. Additionally, as also demonstrated in the definition, degree is subadditive with composition, meaning that the composition arrow is indeed a morphism in $FiltSet$.

Definition 6. A filtered functor $F:C\to D$ is an enriched functor between filtered-morphism categories.

Given a filtered functor $F:C\to D$, since the definition of an enriched functor requires the functor's action on morphisms to be provided by a morphism between hom-objects within the category, it automatically holds that ${\mathrm{deg}}_{D}F\left(\alpha \right)\le {\mathrm{deg}}_C\left(\alpha \right)$ for all morphisms $\alpha$ in $C$.

Definition 7. A filtered deterministic transducer is a deterministic transducer where the input and output categories, $C$ and $D$, are filtered-morphism categories, and the functor $F:C\to D^S$ affording the transducer structure is a filtered functor to the filtered state category of the output category.

Finite-state string machines

For the following section, we assume a filtered deterministic transducer $T$ with input category $C$, output category $D$, structure functor $F$, input state space $S\left(A\right)$, output state space $S\left(B\right)$, primary input $C$-signature $X\to Y$, auxiliary input $D$-signatures $(X_i\to Y_i{)}_{1\le i\le n}$, and output $D$-signatures $(X_j^{\prime }\to Y_j^{\prime }{)}_{1\le j\le m}$. We will now demonstrate that requiring a finite output state space on a transducer provides us with certain output size and time complexity guarantees.

Proposition 1. If $S\left(B\right)$ is finite, and, for every $x\in S\left(A\right)$, the linear term of the degree of every variable in $V_A\left(x\right)$ is nonzero, then, for every $x\in S\left(A\right)$ and every primary input $C$-morphism $\alpha$, the number of copies of the generator corresponding to each auxiliary input $X_i\to Y_i$ appearing in each morphism corresponding to each output signature $X_j^{\prime }\to Y_j^{\prime }$ in $V_{F\left(\alpha \right)}\left(S\right(F\left(\alpha \right)\left)\right(x\left)\right)$ is bounded by a fixed integer $k$, which does not depend on $\mathrm{deg}\left(\alpha \right)$.

Proof. Since $S\left(B\right)$ is finite, and the number of variables which exist at any state is finite, there exists a variable with maximal linear degree $a_{max}^{\prime }$ across all variables in all states in $S\left(B\right)$, in some state in $S\left(B\right)$. No morphism in $D^S$ can generate a morphism in the appropriate $N^2$-graded free category over $D$ with linear degree greater than that of its corresponding variable. Therefore, given any starting state $x\in S\left(A\right)$, no morphism $f:A\to B$ in $D^S$ exists where any component of the output function has more than $a_{max}^{\prime }$ copies of any of the generators corresponding to the variables at $x$, since each of these will have sizes with linear term at least $1$. ◻

 

Proposition 2. Suppose $S\left(B\right)$ is finite, and every variable in every state in $S\left(A\right)$ has a linear term of $1$ or greater in its degree. Denote the primary input morphism of $T$ as $\alpha$ and its tuple of auxiliary input morphisms as ${\beta }_1,\dots ,{\beta }_n$, and define ${\mathrm{deg}}_m\left(\beta \right):={max}_{1\le i\le n}\left(\mathrm{deg}\right({\beta }_i\left)\right)$. Then, for every output signature $X_j^{\prime }\to Y_j^{\prime }$, there exist fixed integers $a_j^T,b_k^T,c_j^T$ such that, for the morphism ${\gamma }_j$ outputted for this signature given these inputs, $\mathrm{deg}\left({\gamma }_j\right)\le a_j^T\mathrm{deg}\left(\alpha \right)+b_j^T{\mathrm{deg}}_m\left(\beta \right)+c_j^T$.

Proof. For every output signature $X_j^{\prime }\to Y_j^{\prime }$, there exists a state $y\in S\left(B\right)$ such that ${\mathrm{deg}}_{B,y}(X_j^{\prime }\to Y_j^{\prime })$ attains some maximal linear coefficient $a_{max}^{\prime }$, the generators corresponding to auxiliary inputs of $T$ can appear in $X_j^{\prime }\to Y_j^{\prime }$ at most some fixed $a_{max}^{\prime }$ number of times. Additionally, a similar maximum $b_{max}^{\prime }$ can be found for the constant term of ${\mathrm{deg}}_{B,y}(X_j^{\prime }\to Y_j^{\prime })$. Since, by the definition of a filtered functor, $\mathrm{deg}\left(F\right(\alpha \left)\right)\le \mathrm{deg}\left(\alpha \right)$, and by the definition of the state category, the $N^2$-degree of the output at $X_j^{\prime }\to Y_j^{\prime }$ can be at most $a_j^{\prime }x+a_j^{\prime }\mathrm{deg}\left(F\right(\alpha \left)\right)+b_j^{\prime }$, then $\mathrm{deg}\left({\gamma }_j\right)\le a_{max}^{\prime }{\mathrm{deg}}_m\left(\beta \right)+a_{max}^{\prime }\mathrm{deg}\left(\alpha \right)+b_{max}^{\prime }$. ◻

 

Corollary 2.1. Suppose a string machine composed only of a finite set of filtered transducers $\{T_k{\}}_{1\le k\le N}$, where each transducer $T_k$ has input state space $S\left(A_k\right)$ and output state space $S\left(B_k\right)$ such that every variable at every state in $S\left(A_k\right)$ has a degree with $1$ or greater linear term, and $S\left(B_k\right)$ is finite. Denote by ${\alpha }_k^{\prime }$ the morphism that $T_k$ will receive as its primary input morphism, given overall input morphisms ${\alpha }_1,\dots ,{\alpha }_n$ and input states $x_1,\dots ,x_m$ to the string machine. Then, ${\sum }_{k=1}^N\mathrm{deg}\left({\alpha }_k^{\prime }\right)=O\left({\sum }_{i=1}^n\mathrm{deg}\right({\alpha }_i\left)\right)$.

Proof. Suppose two transducers $T_1,T_2$, where $T_1$ receives a primary input morphism $\alpha$ and auxiliary input morphisms ${\beta }_1,\dots ,{\beta }_m$. Therefore, by Proposition 2, there exist integers $a_1,b_1,c_1$ such that, for a given output $\gamma$ produced by $T_1$, the degree of $\gamma$ satisfies $\mathrm{deg}\left(\gamma \right)\le a_1\mathrm{deg}\left(\alpha \right)+b_1{\mathrm{deg}}_m\left(\beta \right)+c_1$. Now, if the primary input of $T_2$ is not connected to an output of $T_1$, then the string machine composed of these transducers satisfies the proposition, as the inputs of $T_2$ are now included in the overall inputs of the string machine. If $\gamma$ is composed into the primary input of $T_2$, however, then $\mathrm{deg}\left({\alpha }_2^{\prime }\right)\le a_1\mathrm{deg}\left(\alpha \right)+b_1{\mathrm{deg}}_m\left(\beta \right)+c_1$. Given similar coefficients $a_2,b_2,c_2$ for a given output ${\gamma }_2$ of $T_2$, we can see that $\mathrm{deg}\left({\gamma }_2\right)\le a_2\left(\mathrm{deg}\right({\alpha }_2^{\prime }\left)\right)+b_2{\mathrm{deg}}_m\left({\beta }_2\right)+c_2$, where ${\mathrm{deg}}_m\left({\beta }_2\right)$ is bounded from above by either the same kind of linear sum as the one for $\gamma$ (if the greatest degree among the auxiliary inputs comes from an output of $T_1$), or the degree of yet another additional input to the overall string machine. Therefore, any further composition of transducers $T_3,\dots$ will result in ${\alpha }_3^{\prime },\dots$ also being bounded by a linear sum of the degrees of the overall inputs of the string machine, meaning that the sum ${\sum }_{k=1}^N\mathrm{deg}\left({\alpha }_k^{\prime }\right)$ is also bounded by a linear sum of these degrees. ◻

Corollary 2.1 can be used to bound the time complexity of string machines, if, fixing some model of computation, we have a bound on the time it takes to run a single transducer as a function of its inputs. We note that the coefficients bounding output size are multiplied together upon composition into either an auxiliary input or a primary input, but only composition into a primary input ties the degree of the state transition that will occur in the second transducer to the primary input degree of the first transducer. We define the sum bounded in the corollary as follows:

Definition 8. Take a string machine $K$ with input signatures $X_1\to Y_1,\dots X_n\to Y_n$ and input state spaces $S\left(A_1\right),\dots ,S\left(A_m\right)$, where the transducers forming $K$ form the set $\{T_k{\}}_{1\le k\le N}$. Denote by ${\alpha }_k^{\prime }$ the morphism that the transducer $T_k$ will receive as its primary input morphism, given inputs ${\alpha }_1,\dots ,{\alpha }_n$ ($\overline{\alpha }$ for short) and $x_1,\dots ,x_m$ ($\overline{x}$ for short) to $K$. We define the internal total primary input degree of $K$ to be ${IPD}_K(\overline{\alpha },\overline{x}):={\sum }_{k=1}^N\mathrm{deg}\left({\alpha }_k^{\prime }\right)$.

While we have established that, lacking a meta-vertex, ${IPD}_K$ will be linearly bounded by the total degree of its inputs, its scaling properties as a function of the number of transducers composed has no such guarantees. One can observe that composing more and more transducers that double their input size together causes exponential growth in ${IPD}_K$. As we are interested in the time complexity of both string machines that incorporate a meta-vertex and of parameterized families of string machines, we must obtain some sufficient conditions for ${IPD}_K$ to grow polynomially in the number of transducers in our string machine. To help determine these conditions, we will define the output-degree-bounding parameters referenced in Proposition 2.

Definition 9. Take a filtered deterministic transducer $T$ with a finite output state space $S\left(B\right)$ and an output signature $X\to Y$ of $T$. Given an input state $x$, primary input morphism $\alpha$, and auxiliary input morphisms ${\beta }_1,\dots ,{\beta }_m$ to $T$, denote by $\gamma$ the output morphism produced for $X\to Y$. We define the output degree ${\mathrm{deg}}_o^T(X\to Y)$ of the output $X\to Y$ of $T$ to be the integer triple $(a,b,c)$ such that the relation described in Proposition 2, $\mathrm{deg}\left(\gamma \right)\le a\mathrm{deg}\left(\alpha \right)+b{\mathrm{deg}}_m\left(\beta \right)+c$, holds for all possible $\alpha$ and ${\beta }_1,\dots ,{\beta }_m$ (and the $\gamma$ produced by these inputs). Given the minimal linear term $a_{min}$ (at least $1$) that the degree of any variable in any state in the input state space of $T$, and the maximal linear term $a_{max}^{\prime }$ and constant term $b_{max}^{\prime }$ for the degree of the variable in the output state space corresponding to $X\to Y$, we can unambiguously define ${\mathrm{deg}}_o^T(X\to Y)=(a_{max}^{\prime },\lfloor a_{max}^{\prime }/a_{min}\rfloor ,b_{max}^{\prime })$.

We can now prove some elementary sufficient conditions for ${IPD}_{K_N}$ for a family $\{K_N{\}}_{N\le 1}$ of string machines to grow polynomially in $N$.

Proposition 3. Suppose a family of string machines $\{K_N{\}}_{N\ge 1}$, where $K_1$ is composed of a single filtered deterministic transducer with a finite output state space, and for $N>1$, $K_N$ is created by composing some of the outputs of $K_{N-1}$ into the inputs of a new filtered deterministic transducer with a finite output state space, such that the remaining uncomposed input legs of each $K_N$ are the same for all $N$. Given the output $X_N\to Y_N$ of $K_{N-1}$ composed into the primary input of the new transducer added to obtain $K_N$, we designate the transducer that that output is produced from as $T_N^{\prime }$, and write ${\mathrm{deg}}_o^{T_N^{\prime }}(X_N\to Y_N)=(a_N,b_N,c_N)$. Now, fixing any input states and morphisms, ${IPD}_{K_N}=O\left(N^h\right)$ for some $h$, regardless of the value of the inputs fixed, if the following conditions are met:

• We have that $c_N=O\left(N^k\right)$, for some fixed $k$.
• We have that $a_N+b_N=O\left(1\right)$.
• The number of times that $a_N+b_N>1$ is $O\left(\log N\right)$.

Proof. Omitting our input morphisms and states, we have that ${IPD}_{K_N}={IPD}_{K_{N-1}}+{\gamma }_N$, where ${\gamma }_N$ is the output of $K_{N-1}$ composed into the new transducer's primary input. ${IPD}_{K_1}$ is obviously simply the degree of our initial primary input. $T_N^{\prime }$ either adds $O\left(N^k\right)$ degrees' worth of material to the new transducer's primary input compared to ${IPD}_{K_{N-1}}$, or at most multiplies ${IPD}_{K_{N-1}}$ by some fixed amount and then adds this extra degree. Since subsequent multiplications of this sum can be bounded from above by doing all the additions first first and then multiplying the result by the cumulative multiplication thus far, the function bounding ${IPD}_{K_N}$ can be expressed as a sum 

$$\sum _{i=1}^{N}O\left(1{)}^{O\left(\log i\right)}\right(n+iO\left(i^k\right))\le N(N^{O\left(1\right)}(n+O(N^{k+1}\left)\right))=N^{\ell +1}n+O(N^{\ell +k+2})$$

 where $\ell$ is the constant coefficient affording the $O\left(\log i\right)$ bound, and $n$ is the total degree of the input morphisms to $K_N$. ◻

Remark. We have thus far only considered filtered transducers where the linear term of every variable in the input state space is non-vanishing. If we change this condition to only require that the constant term of the variable be non-vanishing, then the total number of generators in the $N^2$-filtered category over the output category produced in the output is still bounded by a linear function of the primary input signature. So, the degree of the output function is now linear in the product of the degrees of the primary and auxiliary inputs. One can observe, however, that any composition of transducers will only cause outputs to be multiplied with each other a fixed number of times, so $IPD$ will now be bounded by a polynomial in the total inputs of the string machine.

String machine description length

As string machines can themselves be thought of as morphisms in a category, and we are interested in extending our complexity constraints to the case where the meta-vertex is involved, we must imbue the category that string machines are morphisms in with a filtered category structure itself. While this could be accomplished by setting the degree of a string machine to just be the number of transducers involved (where a no-transducer string machine is just the identity and has degree zero), this obviously fails to capture the internal complexity of a transducer.

If we require that the input category of every non-meta-vertex transducer be finitely-generated, then we could make reference to the size of some fixed graph representation of a transducer's transition table and output functions corresponding to generators, and then have this size be additive when transducers are composed. However, as discussed in the previous section, this description size does not constrain time complexity for transducers which build other transducers and then run them. We discuss possible approaches in our conclusion.

The expressivity of finite-state string machines

Now that we have obtained guarantees for the scaling of $IPD$, which can be thought of as an analogue to the time complexity of running a string machine, in both the number of transducers in a string machine and in input size, we focus on characterizing the expressivity of string machines consisting of finite-state deterministic transducers, that is, filtered deterministic transducers where the state space corresponding to every element of the input category (not only the output state space) is finite.

In the following section, we will assume that all transducers have an input category that is of a form described as follows:

Definition 10. A tape category is a filtered-morphism copy-discard category $X$ freely generated over a single object $X$ and a finite number of morphisms of the form $X^m\to X^n$ (where superscripts denote monoidal self-products), where every generator morphism has positive degree. If all our generator morphisms are of signature $X^m\to X$, then a tape category is the copy-discard category freely generated over the symmetric monoidal category freely generated from the multicategory with one object freely generated from those generators, by way of the functor from multicategories to monoidal categories proven by Hermida to be an adjoint to the forgetful functor in the other direction.

We can treat tapes as a special case of tape category, where all generators are endomorphisms of the generating object.

Without a meta-vertex

Finite-state string machines, even without a meta-vertex, can prepend to their output, which is not something the traditional definition of finite-state transducer can do. It is natural to investigate if this makes the framework more expressive than a deterministic finite automaton, e.g., having it recognize palindromes by reversing a string and then feeding the product of these two (their overlaying) into a transducer that then checks if each character matches up.

Unfortunately, given morphisms $f:A\to B$ and $g:C\to D$ in an input category (not necessarily a tape category) $C$, and their product $f\otimes g$, we can see that, since $F(f\otimes g)=F(f\otimes {id}_D)\circ F({id}_A\otimes g)=F({id}_B\otimes g)\circ F(f\otimes {id}_C)$, a state transition on a collection of finite state spaces induced by the product of two morphisms can only capture the same sort of information that could be captured by independently running two finite-state transducers on both morphisms and comparing their states at the very end.

Thus, "per-character" comparisons of the sort that would require conditions analogous to aligning characters on tape would require infinite state spaces to represent the equivalent memory operations being performed. However, due to the nature of the auxiliary input, as well as the aforementioned prepending capabilities, we are clearly able to model functions that finite state transducers cannot, even without a meta-vertex.

To characterize the class of decision problems computable by non-meta-vertex finite-state string machines, we first prove the following lemma:

Lemma 4. Suppose some finite-state transducer $T$ with primary input signature $X\to X$ in a tape category $X$, structure functor $F$, and output state space $S\left(A\right)$, such that these are its only inputs and outputs. Fix a finite set of morphisms $\{g_1,\dots ,g_n:X\to X\}$ in the freely-generated $N^2$-filtered category over $X$ with a single generating signature $X\to X$ of degree $x$, such that the linear coefficient of the degree of each $g_i$ is at most $1$ (that is, the generator corresponding to $X\to X$ appears at most once). Suppose we are able to construct a primary input morphism $g:X\to X$ for this transducer in the following way:

• Our starting value for $g$ is ${id}_X$.
• We can replace $g$ with with one of the previously-given $g_i$, with $g$ substituted for the generator morphism. We can perform this step a finite of times.
• Then, given some state transition reached as a result of some such $g$, the space complexity of computing the output state of the transducer is $O\left(1\right)$ in the degree of $g$.

Proof. We will assume that one "computational step" involves performing one of the operations involved in constructing $g$ described above. We will demonstrate that computing the next state after any of the operations performed requires storing an amount of information that is $O\left(1\right)$ in the degree of $g$.

• If one of the $g_i$ does not have the generator morphism appear at all, then $S\left(A\right)$ after this $g_i$ has replaced $g$ depends solely on the $g_i$ used, and since the set of such $g_i$ is finite, it takes a finite amount of space to store the state reached from the starting state when one of these $g_i$ are evaluated.
• If one of the $g_i$ only involves post-composing an endomorphism of $X$ into the generator, then storing the state reached from a given state after any of these endomorphisms is post-composed takes a fixed amount of memory, since the set of $g_i$ is finite.
• If one of the $g_i$ involves only pre-composing and post-composing endomorphisms of $T$ into $g$, then computing the resultant state after the action of one of these $g_i$ only requires us to store $|S\left(A\right)|$ extra "possible current states." That is, if we know what state we would be in after the evaluation of $g$ had we started at any other one of the $|S\left(A\right)|$ states of the transducer, then after computing which new starting state we would have started at (which, since the set of endomorphisms we pre-compose is finite, is equivalent to storing a fixed-size transition table), we can then pick the state that the copy of the transducer that started at that state would be at after the action of $g$. This is therefore equivalent to running $|S\left(A\right)|$ copies of a finite state automaton, where each copy starts at a different state.
• Suppose one of the $g_i$ is obtained by taking a morphism $\alpha :X\to X^n$, post-composing morphisms into each branch (such that one branch includes the generator), and then finally post-composing a morphism $\beta :X^n\to X$. Even if multiple "branchings" occur, since the generator where $g$ will be substituted appears only once, we can still decompose this into a morphism obtained by first taking the monoidal product of $g$ with a number of fixed morphisms such that the overall signature of their product is $X^n\to X^n$, and then composing in $\alpha$ and $\beta$. Now, we only need $O\left(1\right)$ space to store the functions $S\left(F\right(X\left)\right)\to S\left(F\right(X^n\left)\right)$ and $S\left(F\right(X^n\left)\right)\to S\left(F\right(X\left)\right)$ induced by $\alpha$ and $\beta$, since these are functions between finite sets. Additionally, for the function $S\left(F\right(X^n\left)\right)\to S\left(F\right(X^n\left)\right)$ induced by the monoid product of $g$ with with a fixed morphism $\gamma$ of signature $X^{n-1}\to X^{n-1}$, by the property discussed at the start of this section, we only need to be keeping track of the action of $F(g\otimes {id}_{X^{n-1}})$ on $S\left(F\right(X^n\left)\right)$ (which, since there are a finite number of $g_i$, only requires keeping an absolutely bounded number of automata running), and then compute the action of $F({id}_X\otimes \gamma )$ on the result, which, as a function with a finite domain and codomain, takes finite space to store.

Therefore, to compute the state transition induced by $g$, we only need to keep $|S\left(A\right)|$ copies of the finite state automaton running, as well as some fixed number of finite-state automata with input and output state spaces corresponding to $S\left(F\right(X^n\left)\right)$ for some fixed $n$. ◻

With this lemma, it now remains to show, roughly speaking, that for any string machine made out of finite-state deterministic transducers which decides some language (represented by morphisms in a tape category), the computation performed at every input morphism can be broken into a constant-bounded number of transitions of the type described in the lemma. We present a conjecture that finite-state string machines without a meta-vertex can only recognize regular languages, followed by a sketch for a proof of this conjecture.

Conjecture. Suppose a string machine composed only of finite-state transducers, where the input and output categories of each transducer are tape categories. Suppose this string machine has only one free input $X\to X$ in some tape category $X$ where all generating morphisms (which form a set $\Sigma$) are endomorphisms of the generating object $X$, and has as its sole output a state space $S\left(A\right)$, with some subset of $S\left(A\right)$ designated as accepting. Then, taking an endomorphism $X\to X$ in $X$ which does not include any instances of the copy morphism to be a string over the alphabet $\Sigma$, any language over $\Sigma$ accepted by this string machine is regular.

Proof sketch. It suffices to prove that the computation involved in deciding this language takes constant space as a function of input size, as $DSPACE\left(O\right(1\left)\right)=REG$. More precisely, given any input morphism $g:X\to X$ and a finite set of possible character strings that we can post-compose into $g$, we desire to show that there is a constant-bounded amount of information (independent of the size of $g$) that we need to store, which will allow us to calculate the output state after any of these character strings are added to $g$. By Proposition 1, each transducer involved in the string machine can create a constant-bounded number of duplicates of its auxiliary inputs within each of its outputs. This means that to predict the state of a given transducer after one of the operations described in Lemma 4 done to an auxiliary input, we need to store a constant amount of information. Moreover, due to the limitation caused by the size of a variable on the number of transitions one can make before we run out of variable space and must either limit ourselves to Lemma 4-like operations or reset, the number of "shapes" auxiliary inputs can exist in is absolutely bounded. The hope is that if we back-propagate until reaching the primary input of the first transducer, we will still have a constant-bounded amount of information to keep track of to predict the output state after the next character is reached.

Remark. This conjecture is already suggested by the combination of Corollary 2.1 and classical results by Kobayashi and Hennie which together imply that any one-tape Turing machine that runs in $o\left(n\log n\right)$ time decides a regular language. The reason the proposition is not trivially implied by these results is that a naive simulation of the string machine in question on a single-tape Turing machine will cross the last cell of its initial input a guaranteed $O\left(n\right)$ times (when going back and forth to read the next cell to write the inputs to feed to the next automaton in line). The conjecture would also automatically be implied if we prove that the composition of two finite-state transducers can be equivalently modeled by a single finite-state transducer.

With a meta-vertex

The meta-vertex, even at meta-level one, can clearly be seen to increase the expressivity of finite-state string machines. We construct a string machine which can be recognize palindromes as follows:

Given a tape category $X$ where all generating morphisms are endomorphisms of the generating object $X$, mark a special generating endomorphism $r$. Given a generating endomorphism $\alpha \ne r$ of $X$, we define $T_{\alpha }$ to be the filtered deterministic transducer with input and output category $X$, with input and output signatures $X\to X$ and three states, a fixed one of which is the starting state. When in the starting state, $T_{\alpha }$ will transition to the "accepting state" and store ${id}_X$ in the sole variable at that state if it encounters $\alpha$, and transition to the "rejecting state" and store $r$ if any other generating morphism is encountered. When in the rejecting state, all morphisms are mapped to the identity on the rejecting state. When in the accepting state, all morphisms transition back to the accepting state, but this time append the current primary input generator morphism to the output. The end result is that when given an endomorphism $s:X\to X$, the transducer $T_{\alpha }$ will output $s$ with its first "character" removed if and only if it starts with $\alpha$, and output $r$ otherwise. As a morphism, it is of signature $(X\to X{)}_X\to (X\to X{)}_X$.

Now, we define a filtered deterministic transducer $T$ with input category $X$, which outputs a filtered deterministic transducer without meta vertices. This transducer has input signature $X\to X$ and only one state, with one variable of signature $(X\to X)\to (X\to X)$, and it is assumed that no morphism $X\to X$ fed to $T$ will include $r$. Given a generator morphism $\alpha$ of $X$, the transducer $T$ will prepend $T_{\alpha }$ to the current variable's stored string machine. If we compose a meta vertex that takes the output of $T$ and takes the same input morphism as $T$ and passes it on to the string machine formed by $T$, then we obtain a string machine that outputs ${id}_X$ if it is given a palindrome, and $r$ if it is fed anything else.

Conclusions

Thus far, we have proven results about the time complexity and expressivity of finite-state deterministic transducers in the string machines framework. This framework allows us to model the compositionality of transducers in a way that allows for more compression of description length. For example, we are able to implement the trivial time-space tradeoff of recognizing a regular language that is the intersection of several regular languages by running several automata in sequence instead of the product automaton, or the cascade product in Krohn-Rhodes theory by having a transducer "shuffle" its primary input using its ability to prepend.

Additionally, our time complexity scaling guarantees in the number of transducers in a string machine translate to sufficient conditions for transducers which build and run other transducers in runtime to run in polynomial time. This will allow us to take advantage of the additional compression opportunities the meta-vertex presents. These results are valuable for developing string machines into a framework that can be used to model hypothesis spaces representable by automata.

Further work

Description complexity that encapsulates time complexity

As exemplified by Definition 4, the construction of filtered sets can be extended to a partially-ordered monoid that is not $N$. Since a string machine without a meta-vertex will have the degrees of its outputs be bounded by a linear function of the degrees of its inputs, we can assign a degree $ax+b$ to finite-state filtered transducers, where $a$ and $b$ are the maximal values for some sum of the coefficients appearing in the output degree in Definition 9, where the partial order is the same as in Definition 4. However, in this case, the monoid operation imposed on the polynomials is composition, due to how the linear relations bounding output size get composed when transducers are composed, and the filtered-set category is no longer symmetric monoidal since this operation is not commutative.

Now, the variables in our state categories would have their degrees be of the form $ay+bx+c$, where a morphism of degree $dx+e$ can compose in a transducer of at most that degree, meaning the output variable is of degree $a(y+(dx+e\left)\right)+bx+c=ay+(dx+e{)}^a\circ bx+c$ by abuse of notation. where the superscript indicates $a$-fold self-composition. At further meta-levels, we keep adding terms, though it is unclear how we would disambiguate which variable to compose into for the monoid operation.

Characterizing the expressivity of transducers with a meta-vertex and monadic transducers

We have not yet established bounds on the expressivity of finite-state deterministic transducers which incorporate the meta-vertex, but, due to the bounding on levels of meta, it is likely that the languages they decide are some subset of context-free languages. The time complexity guarantees also need to be translated to the monadic case. Work on bounding the expressivity of monadic string machines may involve defining equivalents for string machines of various properties (see work by Mohri, Allauzen et al., Kostolanyi, and Bell et al.) which characterize determinizable weighted transducers, which may in turn allow us to bound the computational complexity of computing the distribution on output morphisms given by a monadic transducer.

0 comments

Comments sorted by top scores.