The Nonlinear Library AF - Time complexity for deterministic string machines by alcatal
Apr 22, 2024
36:01
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Time complexity for deterministic string machines, published by alcatal on April 21, 2024 on The AI Alignment Forum.
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.
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,degS), where S is a set and degS:SN is a function,
a morphism f:(S,degS)(T,degT) is a function ST such that degT(f(s))degS(s) for all sS.
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 degS(idS(s))=degS(s) for all sS and is thus a morphism in FiltSet. One can also observe that given f:ST and g:TV, degV(g(f(s)))degT(f(s))degS(s) for all sS, and therefore gf is also a morphism in FiltSet. Therefore, FiltSet is indeed a category.
Definition 2. Given two objects S,TOb(FiltSet), we define their filtered product ST to be the set ST equipped with the function degST:STN satisfying degST(s,t)=degS(s)+degT(t) for all (s,t)ST. Given a morphism f:SU and a morphism g:TV, we define the morphism fg:STUV to be the function fg. Indeed, we have that degUV(f(s),g(t))=degU(f(s))+degV(g(t))degS(s)+degT(t)=degST(s,t), so fg 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, is naturally associative and commutative up to isomorphism. Additionally, the one-element set 1 equipped with deg1()=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 , making FiltSet a symmetric monoidal category.
Remark. Suppose filtered sets S,T,U and filtered morphisms f:ST and g:SU. Then, the unique factoring function STU defined by s(f(s),g(s)) is only a filtered morphism STU if degT(f(s))+degU(g(s))degS(s), 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, FiltSet does have finite products ST where degST(s,t):=max(degS(s),degT(t)). 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 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 IFiltSetHomC(A,A) providing the identity morphism idA in the enrichment construction will ensure that...
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.
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,degS), where S is a set and degS:SN is a function,
a morphism f:(S,degS)(T,degT) is a function ST such that degT(f(s))degS(s) for all sS.
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 degS(idS(s))=degS(s) for all sS and is thus a morphism in FiltSet. One can also observe that given f:ST and g:TV, degV(g(f(s)))degT(f(s))degS(s) for all sS, and therefore gf is also a morphism in FiltSet. Therefore, FiltSet is indeed a category.
Definition 2. Given two objects S,TOb(FiltSet), we define their filtered product ST to be the set ST equipped with the function degST:STN satisfying degST(s,t)=degS(s)+degT(t) for all (s,t)ST. Given a morphism f:SU and a morphism g:TV, we define the morphism fg:STUV to be the function fg. Indeed, we have that degUV(f(s),g(t))=degU(f(s))+degV(g(t))degS(s)+degT(t)=degST(s,t), so fg 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, is naturally associative and commutative up to isomorphism. Additionally, the one-element set 1 equipped with deg1()=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 , making FiltSet a symmetric monoidal category.
Remark. Suppose filtered sets S,T,U and filtered morphisms f:ST and g:SU. Then, the unique factoring function STU defined by s(f(s),g(s)) is only a filtered morphism STU if degT(f(s))+degU(g(s))degS(s), 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, FiltSet does have finite products ST where degST(s,t):=max(degS(s),degT(t)). 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 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 IFiltSetHomC(A,A) providing the identity morphism idA in the enrichment construction will ensure that...