Time complexity for deterministic string machines

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

  • an object is a tuple , where is a set and is a function,

  • a morphism is a function such that for all .

We will generally refer to objects in solely by the symbol corresponding to the underlying set going forward. One can observe that the identity function on a set by definition satisfies for all and is thus a morphism in . One can also observe that given and , for all , and therefore is also a morphism in . Therefore, is indeed a category.

Definition 2. Given two objects , we define their filtered product to be the set equipped with the function satisfying for all . Given a morphism and a morphism , we define the morphism to be the function . Indeed, we have that , so is a morphism in .

Due to the associativity and commutativity of addition, as well as the natural associativity and commutativity (up to isomorphisms which are still isomorphisms in ) of the cartesian product, is naturally associative and commutative up to isomorphism. Additionally, the one-element set equipped with and unitor maps which are the same as in (which are, by their definition, filtered morphisms) provides a left and right unit for , making a symmetric monoidal category.

Remark. Suppose filtered sets and filtered morphisms and . Then, the unique factoring function defined by is only a filtered morphism if , which does not hold in general. Therefore, does not provide a product except for when at least one of the sets has degree uniformly zero. However, does have finite products where . We will not be using this construction.

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

Definition 3. A filtered-morphism category is a locally small symmetric monoidal category enriched over , using ’s filtered product 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 is the single-element set with degree zero, the arrows providing the identity morphism in the enrichment construction will ensure that identity morphisms are degree zero.

One can generalize the construction of by replacing 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 (with the partial order given by if and only if and ) in our construction of the filtered state category, as follows:

Definition 4. Given a filtered-morphism category and a list of -signatures (generators) and linear polynomials with coefficients in , the freely-generated -filtered category over with this list of signatures, or , is the symmetric monoidal category where:

  • objects are exactly the objects of .

  • A morphism is either a morphism of , or obtained by composing morphisms of with free generators added to for each -signature in the list.

  • The -degree of a morphism is a linear polynomial with coefficients in , which is either its degree in (expressed as a constant) if it is a -morphism, the polynomial if it is one of the generators 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 -morphisms being the degrees in 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 -morphism is taken to have the sum of their -degrees.

We can now introduce filtered state categories.

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

  • an object is a tuple , where:

    • The state space of is a set .

    • The variables of are a functor from the discrete category corresponding to to the discrete category formed by all finite ordered tuples of pairs of objects in . We call the tuple associated with a given the variables at , or . Since variables implicitly denote morphism signatures, we will refer to a given variable as .

    • The degree of a variable for some , denoted (or simply if can be inferred from context) is a tuple . We impose the same partial ordering on these tuples as we do with degrees in the freely-generated -filtered categories.

  • a morphism of degree , where , is a tuple , where:

    • The state transition is a function .

    • The output function at , denoted , is a collection of morphisms in a freely-generated -filtered category over , defined as follows:

      For each variable of degree , at , defines a morphism of degree at most (that is, the degree of the morphism cannot exceed this polynomial in either of its terms) in the freely-generated -filtered category over with generators and the degrees of those generators provided by the variables of degrees in . The function between hom-sets in can then be expressed by substituting each generator with a -morphism of the appropriate signature.

      This induces a function (but not a filtered one!) between the product of the hom-sets for all variables at and the product of the hom-sets for all variables at , which can be obtained by replacing each generator corresponding to a variable at with a morphism of of the appropriate signature.

  • Given two morphisms of degree and of degree , their composition is a tuple where:

    • The composite state transition is defined as .

    • The composite output function is defined as follows: For each variable defined at , of degree , defines a morphism of degree at most in the category freely generated over with generators corresponding to the variables at and their degrees. Now, induces a functor from to (where denote the variables at ), which fixes but replaces every free generator of the category freely generated over the variables at with the morphism associated with it by , in the category freely generated over the variables at . Therefore, the output function at is simply the image of each of the morphisms generated by under this functor defined by . 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 at of degree , every generator of some degree involved in the morphism of (initial) degree defined by has been replaced with one of degree . Suppose each generator appears with multiplicity in the morphism corresponding to . Then, we have it that , and since 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 must be . So, the degree of is .

Remark. 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 has an output function that outputs a variable of degree (the generator corresponding to the variable itself) for any variable of degree 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 .

Definition 6. A filtered functor is an enriched functor between filtered-morphism categories.

Given a filtered functor , 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 for all morphisms in .

Definition 7. A filtered deterministic transducer is a deterministic transducer where the input and output categories, and , are filtered-morphism categories, and the functor 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 with input category , output category , structure functor , input state space , output state space , primary input -signature , auxiliary input -signatures , and output -signatures . 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 is finite, and, for every , the linear term of the degree of every variable in is nonzero, then, for every and every primary input -morphism , the number of copies of the generator corresponding to each auxiliary input appearing in each morphism corresponding to each output signature in is bounded by a fixed integer , which does not depend on .

Proof. Since is finite, and the number of variables which exist at any state is finite, there exists a variable with maximal linear degree across all variables in all states in , in some state in . No morphism in can generate a morphism in the appropriate -graded free category over with linear degree greater than that of its corresponding variable. Therefore, given any starting state , no morphism in exists where any component of the output function has more than copies of any of the generators corresponding to the variables at , since each of these will have sizes with linear term at least . ◻

Proposition 2. Suppose is finite, and every variable in every state in has a linear term of or greater in its degree. Denote the primary input morphism of as and its tuple of auxiliary input morphisms as , and define . Then, for every output signature , there exist fixed integers such that, for the morphism outputted for this signature given these inputs, .

Proof. For every output signature , there exists a state such that attains some maximal linear coefficient , the generators corresponding to auxiliary inputs of can appear in at most some fixed number of times. Additionally, a similar maximum can be found for the constant term of . Since, by the definition of a filtered functor, , and by the definition of the state category, the -degree of the output at can be at most , then . ◻

Corollary 2.1. Suppose a string machine composed only of a finite set of filtered transducers , where each transducer has input state space and output state space such that every variable at every state in has a degree with or greater linear term, and is finite. Denote by the morphism that will receive as its primary input morphism, given overall input morphisms and input states to the string machine. Then, .

Proof. Suppose two transducers , where receives a primary input morphism and auxiliary input morphisms . Therefore, by Proposition 2, there exist integers such that, for a given output produced by , the degree of satisfies . Now, if the primary input of is not connected to an output of , then the string machine composed of these transducers satisfies the proposition, as the inputs of are now included in the overall inputs of the string machine. If is composed into the primary input of , however, then . Given similar coefficients for a given output of , we can see that , where is bounded from above by either the same kind of linear sum as the one for (if the greatest degree among the auxiliary inputs comes from an output of ), or the degree of yet another additional input to the overall string machine. Therefore, any further composition of transducers will result in also being bounded by a linear sum of the degrees of the overall inputs of the string machine, meaning that the sum 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 with input signatures and input state spaces , where the transducers forming form the set . Denote by the morphism that the transducer will receive as its primary input morphism, given inputs ( for short) and ( for short) to . We define the internal total primary input degree of to be .

While we have established that, lacking a meta-vertex, 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 . 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 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 with a finite output state space and an output signature of . Given an input state , primary input morphism , and auxiliary input morphisms to , denote by the output morphism produced for . We define the output degree of the output of to be the integer triple such that the relation described in Proposition 2, , holds for all possible and (and the produced by these inputs). Given the minimal linear term (at least ) that the degree of any variable in any state in the input state space of , and the maximal linear term and constant term for the degree of the variable in the output state space corresponding to , we can unambiguously define .

We can now prove some elementary sufficient conditions for for a family of string machines to grow polynomially in .

Proposition 3. Suppose a family of string machines , where is composed of a single filtered deterministic transducer with a finite output state space, and for , is created by composing some of the outputs of into the inputs of a new filtered deterministic transducer with a finite output state space, such that the remaining uncomposed input legs of each are the same for all . Given the output of composed into the primary input of the new transducer added to obtain , we designate the transducer that that output is produced from as , and write . Now, fixing any input states and morphisms, for some , regardless of the value of the inputs fixed, if the following conditions are met:

  • We have that , for some fixed .

  • We have that .

  • The number of times that is .

Proof. Omitting our input morphisms and states, we have that , where is the output of composed into the new transducer’s primary input. is obviously simply the degree of our initial primary input. either adds degrees’ worth of material to the new transducer’s primary input compared to , or at most multiplies 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 can be expressed as a sum

where is the constant coefficient affording the bound, and is the total degree of the input morphisms to . ◻

Assuming the time complexity of a state-category morphism is proportional to its degree, we must impose either a constant or logarithmic bound on the number of primary-input compositions where the output is multiplied to preserve time complexity that is polynomial in the total number of transducers. In the figure, vertical arrows go to a transducer’s primary input, while horizontal ones go to its auxiliary input.

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 -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 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 , 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 freely generated over a single object and a finite number of morphisms of the form (where superscripts denote monoidal self-products), where every generator morphism has positive degree. If all our generator morphisms are of signature , 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 and in an input category (not necessarily a tape category) , and their product , we can see that, since , 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 with primary input signature in a tape category , structure functor , and output state space , such that these are its only inputs and outputs. Fix a finite set of morphisms in the freely-generated -filtered category over with a single generating signature of degree , such that the linear coefficient of the degree of each is at most (that is, the generator corresponding to appears at most once). Suppose we are able to construct a primary input morphism for this transducer in the following way:

  • Our starting value for is .

  • We can replace with with one of the previously-given , with 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 , the space complexity of computing the output state of the transducer is in the degree of .

Proof. We will assume that one “computational step” involves performing one of the operations involved in constructing described above. We will demonstrate that computing the next state after any of the operations performed requires storing an amount of information that is in the degree of .

  • If one of the does not have the generator morphism appear at all, then after this has replaced depends solely on the used, and since the set of such is finite, it takes a finite amount of space to store the state reached from the starting state when one of these are evaluated.

  • If one of the only involves post-composing an endomorphism of 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 is finite.

  • If one of the involves only pre-composing and post-composing endomorphisms of into , then computing the resultant state after the action of one of these only requires us to store extra “possible current states.” That is, if we know what state we would be in after the evaluation of had we started at any other one of the 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 . This is therefore equivalent to running copies of a finite state automaton, where each copy starts at a different state.

  • Suppose one of the is obtained by taking a morphism , post-composing morphisms into each branch (such that one branch includes the generator), and then finally post-composing a morphism . Even if multiple “branchings” occur, since the generator where will be substituted appears only once, we can still decompose this into a morphism obtained by first taking the monoidal product of with a number of fixed morphisms such that the overall signature of their product is , and then composing in and . Now, we only need space to store the functions and induced by and , since these are functions between finite sets. Additionally, for the function induced by the monoid product of with with a fixed morphism of signature , by the property discussed at the start of this section, we only need to be keeping track of the action of on (which, since there are a finite number of , only requires keeping an absolutely bounded number of automata running), and then compute the action of 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 , we only need to keep 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 for some fixed . ◻

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 in some tape category where all generating morphisms (which form a set ) are endomorphisms of the generating object , and has as its sole output a state space , with some subset of designated as accepting. Then, taking an endomorphism in which does not include any instances of the copy morphism to be a string over the alphabet , any language over 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 . More precisely, given any input morphism and a finite set of possible character strings that we can post-compose into , we desire to show that there is a constant-bounded amount of information (independent of the size of ) that we need to store, which will allow us to calculate the output state after any of these character strings are added to . 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 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 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 where all generating morphisms are endomorphisms of the generating object , mark a special generating endomorphism . Given a generating endomorphism of , we define to be the filtered deterministic transducer with input and output category , with input and output signatures and three states, a fixed one of which is the starting state. When in the starting state, will transition to the “accepting state” and store in the sole variable at that state if it encounters , and transition to the “rejecting state” and store 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 , the transducer will output with its first “character” removed if and only if it starts with , and output otherwise. As a morphism, it is of signature .

Now, we define a filtered deterministic transducer with input category , which outputs a filtered deterministic transducer without meta vertices. This transducer has input signature and only one state, with one variable of signature , and it is assumed that no morphism fed to will include . Given a generator morphism of , the transducer will prepend to the current variable’s stored string machine. If we compose a meta vertex that takes the output of and takes the same input morphism as and passes it on to the string machine formed by , then we obtain a string machine that outputs if it is given a palindrome, and 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 . 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 to finite-state filtered transducers, where and 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 , where a morphism of degree can compose in a transducer of at most that degree, meaning the output variable is of degree by abuse of notation. where the superscript indicates -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.

No comments.