CALF: Categorical Automata Learning Framework

Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. We illustrate its generality with two examples: deterministic and weighted automata.

Introduction
Automata learning enables the use of model-based verification methods on black-box systems. Learning algorithms have been successfully applied to find bugs in implementations of network protocols [15], to provide defense mechanisms against botnets [13], to rejuvenate legacy software [27], and to learn an automaton describing the errors in a program up to a user-defined abstraction [12]. Many learning algorithms were originally designed to learn a deterministic automaton and later, due to the demands of the verification task at hand, extended to other types of automata. For instance, the popular L algorithm, devised by Angluin [2], has been adapted for various other types of automata accepting regular languages [9,3], as well as more expressive automata, including Büchi-style automata [23,4], register automata [10,11], and nominal automata [24]. As the complexity of these automata increases, the learning algorithms proposed for them tend to become more obscure. More worryingly, the correctness proofs become involved and harder to verify. This paper aims to introduce an abstract framework for studying automata learning algorithms in which specific instances, correctness proofs, and optimizations can be derived without much effort. The framework can also be used to study algorithms such as minimization and testing, showing the close connections between the seemingly different problems. These connections also enable the transfer of extensions and optimizations among algorithms.
First steps towards a categorical understanding of active learning appeared in [19]. The abstract definitions provided were based on very concrete data structures used in L , which then restricted potential generalization to study other learning algorithms and capture other data structures used by more efficient variations of the L algorithm. Moreover, there was no where M is a finite set of states, δ M : M × A → M is the transition function, F M ⊆ M is the set of accepting states, and m 0 ∈ M is the initial state. Note that the transition function is well-defined because of the definition of t L and M is finite because the language is regular. Though we know M is finite, computing it naively as the image of t L does not terminate, since the domain of t L is the infinite set A * . Learning algorithms approximate M by instead constructing two finite sets S, E ⊆ A * , which induce the function row : S ∪ S · A → 2 E defined as row(u)(v) = L(uv). The name "row" reflects the usual representation of this function as a table with rows indexed by S ∪ S · A and columns indexed by E. This table is called an  observation table,  It is often required that ε is an element of both S and E, so that the initial and accepting states are well-defined. For the transition function to be well-defined, the observation table is ID. Angluin [1] showed that, for algorithms with just this extra assumption, the number of membership queries has a lower bound that is exponential in the size of M . She then introduced an algorithm called ID that makes a stronger assumption. It assumes a finite set S of words such that each state of M (that does not accept the empty language) is reached by reading a word in S. Initializing E = {ε}, the algorithm obtains M up to isomorphism after making the table consistent (for a slightly stronger definition of consistency related to the sink state being kept implicit). This makes ID polynomial in the sizes of M , S, and A.
L . Subsequently, Angluin introduced the algorithm L [2], which makes yet another assumption: it assumes an oracle that can test any DFA for equivalence with the target language. In the case of a discrepancy, the oracle will provide a counterexample, which is a word in the symmetric difference of the two languages. L adds the given counterexample and its prefixes to S. One can show that this means that the next hypothesis will classify the counterexample correctly and that therefore the size of the hypothesis must have increased. The algorithm is polynomial in the sizes of M and A and in the length of the longest counterexample. CALF. The framework we introduce in this paper aims to provide a formal and general account of the concepts introduced above, based on category theory. Although the focus is on automata learning, the general perspective brought by CALF allows us to unveil deep connections between learning and algorithms for minimization and testing. The structure of CALF is depicted in Figure 1. After introducing the basic elements of the framework in Section 3, we use the framework in Section 4 to give a new categorical correctness 29:4 CALF: Categorical Automata Learning Framework proof, encompassing all the algorithms mentioned above. Then we explore connections with minimization and testing, following the edges of the triangle in Figure 1: 1 Section 5 shows how our correctness proof also applies to minimization algorithms. In particular, we connect consistency fixing to the steps in the classical partition refinement algorithm that merge observationally equivalent states. Dually, reachability analysis, which is also needed to get the minimal automaton, is related to fixing closedness defects. 2 Section 6 extends the correctness proof to an abstract result about testing and we show how it applies to algorithms such as the W-method [14], which enable testing against a black-box system. 3 From the abstract framework and the observations in 1 and 2 , we also see how certain basic sets used in testing algorithms like the W-method can be obtained using generalized minimization algorithms. This triangular structure is on its own a contribution of the paper, tying together three important techniques that play a role in automata learning and verification. Another strong point of CALF is the ability to seamlessly accommodate variants of learning algorithms: algorithms for other types of automata, by varying the category on which automata are defined. This includes weighted automata, which are defined in the category of vector spaces. We present details of this example in Appendix A. algorithms with optimizations, by varying the data structure. Section 7 discusses classification trees [20], which optimize the observation tables of classical learning algorithms. CALF also provides guidelines on how to combine these variants, and on how to obtain corresponding minimization/testing algorithms via the connections described above. This can lead to more efficient algorithms, and, because of our abstract approach, correctness proofs can be reused.

Abstract Learning
In this section, we develop CALF by starting with categorical definitions that capture the basic data structures and definitions used in learning.

Observation Tables as Approximated Algebras
In the automata learning algorithms described in Section 2, observation tables are used to approximate the minimal automaton M for the target language L. We start by introducing a notion of approximation of an object in a category, called wrapper. We work in a fixed category C unless otherwise indicated.

Definition 1 (Wrapper). A wrapper for an object T is a pair of morphisms
Example 2. The algorithms explained in Section 2 work by producing subsequent approximations of M . In each approximation, we have two finite sets of words S, E ⊆ A * , yielding Here σ maps s ∈ S to the state reached by M after reading s while π assigns to each state of M the language accepted by that state, but restricted to the words in E. Although M is unknown, the composition of π and σ is given by (π • σ)(s)(e) = L(se), which can be determined using membership queries. This composition is precisely the component S → 2 E of the observation table row : We claim that the other component S · A → 2 E of row is an approximated version of the transition function δ M : M × A → M , and that it can be obtained via the wrapper w. More generally, we can abstract away from the structure of automata and approximate algebras for a functor F , i.e., pairs (T, f : F T → T ). Notice that (M, δ M ) is an algebra for (−) × A.
Definition 3 (Approximation of Algebras Along a Wrapper). Given an F -algebra (T, f ) and We write ξ w for ξ w id = π • σ, and we may leave out superscripts if the relevant wrapper w is clear from the context. We remark that our theory does not depend on a specific choice of wrappers and approximations along them. Observation tables are just an instance. Other data structures representing approximations of automata can also be captured, as will be shown in Section 7.
Although the algebra f may be unknown-as for instance f = δ M is unknown to automata learning algorithms-the approximated version ξ f can sometimes be recovered via the following simple result, stating that approximations transfer along algebra homomorphisms.

Proposition 4. For all endofunctors
Example 5. Consider again the wrapper in Example 2. There σ = rch • inc, where inc : S → A * is the inclusion of S into A * and rch : A * → M is the full reachability map of M . If we equip A * with transitions cat : A * × A → A * defined as cat(u, a) = ua, then rch is an algebra homomorphism (A * , c) → (M, δ) for (−) × A. We can therefore apply Proposition 4 to obtain ξ (rch•inc,π) δ = ξ (inc,π•rch) c . It follows that ξ δ : S × A → 2 E is given by ξ δ (s, a)(e) = L(sae), which corresponds to the S · A → 2 E part of the row function in Section 2.

Hypotheses as Factorizations
We now formalize the process of deriving a hypothesis automaton from an observation table.
Recall from Section 2 that the state space of the hypothesis automaton is precisely the image of the component S → 2 E of the row function. Image factorizations are abstractly captured by the notion of (E, M) factorization system on a category. We will assume throughout the paper that our category C has (E, M) factorizations.
Definition 6 (Factorization System). A factorization system is a pair (E, M) of sets of morphisms such that 1. all morphisms f can be decomposed as f = m • e, with m ∈ M and e ∈ E; 2.
for all commutative squares as on the right, where i ∈ E and j ∈ M, there is a unique diagonal d making the triangles commute; 3. both E and M are both closed under composition and contain all isomorphisms; 4. every morphism in E is an epi, and every morphism in M is a mono. We will use double-headed arrows ( ) to indicate morphisms in E and arrows with a tail ( ) to indicate morphisms in M. For instance, in Set the pair (surjective functions, injective functions) forms a factorization system, where each function f : X → Y can be decomposed as a surjective map X img(f ) followed by the inclusion img(f ) Y . wrapper (σ, π) is the (E, M)-factorization of π • σ, depicted on the right. Notice that (e, m) is a wrapper for H.
In the wrapper of Example 2, H is the state space of the hypothesis automaton defined in Section 2. However, H does not yet have an automaton structure. In the concrete setting, this can be computed from the S · A → 2 E part of row whenever closedness and consistency are satisfied. We give our abstract characterization of these requirements, which generalize the definitions due to Jacobs and Silva [19].
(1) making the left triangle in (1) commute; we say that w is fconsistent if there is a morphism cons w f : F H → P making the right triangle commute.
Closedness and consistency together yield an algebra structure on the hypothesis. This is not just any algebra, but one that relates the wrapper to its minimization, as we show next. Proof. Given the morphisms close f and cons f , we let θ f be the unique diagonal provided by the factorization system for the commutative square (1); conversely, given θ f , we take To understand abstract closedness and consistency properties in Set, and to relate them to the concrete definitions given in Section 2, we give the following general result.
Proof. 1. If such an i exists, then for each u ∈ U we have h(i(u)) = g(u). Conversely, define i(u) to be any w ∈ W such that h(w) = g(u), which exists by assumption. Then therefore g(u 1 ) = g(u 2 ). Conversely, define j(f (u)) to be g (u), using that f is surjective.
We only need to check that this is well-defined; i.e., that whenever f (u 1 ) = f (u 2 ) we also have g(u 1 ) = g(u 2 ). This is precisely the assumption.
For the wrapper in Example 2 and F = (−) × A, δ M -closedness and δ M -consistency coincide respectively with closedness and consistency as defined in Section 2. If these are satisfied, then the function θ δ M is precisely the transition function δ H defined there. Notice that all endofunctors on Set preserve surjections.
Interestingly, closedness and consistency also tell us when initial and accepting states of H can be derived from the observation table. For initial states, we note that the initial state m 0 ∈ M can be seen as a function m 0 : 1 → M . As the set 1 is the constant functor 1 applied to M , this initial state gives rise to another closedness property, which states that there must be an s ∈ S such that ξ(s)(e) = L(e) for all e ∈ E. Note that m 0 -consistency trivially holds because of the constant functor involved. When m 0 -closedness is satisfied, close m0 : 1 → H is an initial state map. For instance, in L this property is always satisfied because ε ∈ S.
For accepting states, one would expect a similar property regarding the set F M ⊆ M , which can be represented by a function F M : M → 2. However, this is a coalgebra (for the constant functor 2) rather than an algebra. Fortunately, a wrapper (S In particular, for F M : M → 2, this leads to a consistency 1 property stating that for all s 1 , s 2 ∈ S such that ξ(s 1 ) = ξ(s 2 ) we must have L(s 1 ) = L(s 2 ). The L algorithm ensures this by having ε ∈ E, using that L(s) = ξ(s)(ε) for any s ∈ S.

A General Correctness Theorem
In this section we work towards a general correctness theorem that is completed in Section 4.1, where we introduce an abstract notion of automaton. We then show in Section 4.2 how the theorem applies to the ID algorithm, to the algorithm by Arbib and Zeiger, and to L . First, we need the following result.
Proposition 11. If f : The key observation for the correctness theorem is the following.
If σ ∈ E, then the factorization system gives us a unique diagonal φ in the left square of (3), which by (the dual of) Proposition 11 satisfies φ ∈ E. Similarly, if π ∈ M, we have ψ in the right square of (3), with ψ ∈ M. Composing the two diagrams and using again the unique diagonal property, one sees that φ and ψ must be mutually inverse. We can conclude that H and T are isomorphic. Now, if w is a wrapper produced by a learning algorithm and T is the state space of the target minimal automaton, as in Example 2, our reasoning hints at a correctness criterion: σ ∈ E and π ∈ M upon termination ensure that H is isomorphic to T . Of course, the criterion will have to guarantee that the automata, not just the state spaces, are isomorphic.
We first show that the argument above lifts to F -algebras f : F T → T , for an arbitrary endofunctor F : C → C preserving E.
Proposition 13. For a wrapper w = (σ, π) and an F -algebra f , if σ ∈ E and w is fconsistent, then φ as given in (3) and w is f -closed, then ψ as given in (3) The proof for the other part is analogous. Using Lemma 12 and Theorem 9 we see that θ f exists. Since F σ is epic and m monic, it suffices to which is done on the right.

Abstract Automata
Now we enrich F -algebras with initial and final states, obtaining a notion of automaton in a category. Then we give the full correctness theorem for automata. We fix objects I and Y in C, which will serve as initial state selector and output of the automaton, respectively.

Definition 15 (Automaton). An automaton in C is an object
An input system is an automaton without an output map; an output system is an automaton without an initial state map.
Automata form a category, where morphisms f between automata U and V are F -algebra homomorphisms that commute with initial state and output maps: f • init U = init V and out V • f = out U . Composition and identities are as in C. There are analogous categories of input and output systems.
To recover DAs (DFAs that may not be finite) over an alphabet A as automata, we take I = 1, Y = 2, and F = (−) × A in the category C = Set. An input system is then a DA without a classification of states into accepting and rejecting states; an output system is a DA without a designated initial state.
In Appendix A we explain how weighted automata can be modeled as automata. Nominal automata are automata in the category of nominal sets and equivariant functions if we take I = 1 with a trivial action, Y any nominal set, and F = (−) × A for a nominal set A. We do not treat this setting in the present paper, but the L adaptation devised by Moerman et al.
We assume the existence of an initial input system A and a final output system Z. These give general notions of reachability and observability.

Definition 16 (Reachability and Observability
reachability map of an automaton Q is the unique input system homomorphism rch Q : A → Q; its observability map is the unique output system homomorphism An automaton is minimal if it is both reachable and observable. In the DA setting, the set of words A * forms an initial input system. Its initial state is the empty word ε : 1 → A * , and its transition function cat : A * ×A → A * is given by concatenation: cat(u, a) = ua. This yields the expected definition of the reachability map rch Q : a). The set of languages 2 A * in this setting forms a final output system. Its accepting states ε? : 2 A * → 2 are those languages that contain the empty word, ε?(L) = L(ε), and its dynamics deriv The observability map of a DA Q assigns to each state the language it accepts: obs Q (q)(ε) = out Q (q) and obs Q (q)(av) = obs Q (δ Q (q, a))(v).
In general, we define the language of an automaton Q to be L Q = out Q • rch Q : A → Y . For DFAs, this is the usual definition of the accepted language A * → 2 (alternatively, L Q = obs Q • init Q : 1 → 2 A * , which explicitly mentions the initial state). If for automata U and V there exists an automaton homomorphism U → V , one can prove that L U = L V .
We are now ready to give the main result of this section, which extends Proposition 13. Intuitively, it provides conditions for when the hypothesis automaton is actually the target automaton. Remarkably, unlike Proposition 13, it is enough to require just one of σ ∈ E and π ∈ M, thanks to observability and reachability.
be a wrapper for an automaton Q and let H be the hypothesis automaton for w. If at least one the following is true: 1. Q is observable and w is an out Q -consistent and δ Q -consistent wrapper such that σ ∈ E; 2. Q is reachable and w is an init Q -closed and δ Q -closed wrapper such that π ∈ M; then H and Q are isomorphic automata.
Proof. We only show point 1; the other is analogous. Recall that the initial state map of the automaton is an algebra for the constant functor I while the output map is a coalgebra for the constant functor Y . Hence, we can apply Proposition 13 (or its dual for the coalgebra) to them and to δ Q to find that φ : Q → H is an automaton homomorphism. Then obs Q = obs H • φ by finality of Z. Since obs Q is in M, this means that φ ∈ M (see Proposition 11). Because m ∈ M and π = m • φ (3), we have π ∈ M. Therefore, we can apply Corollary 14, again three times, and obtain an automaton isomorphism between Q and H.

Applications to Known Learning Algorithms
Recall that ID assumes a finite set S ⊆ A * such that each state of the minimal target DFA M is reached by reading one of the words in S when starting from m 0 . In the terminology of the previous section, the algorithm takes a wrapper (S σ − → M, M π − → 2 E ) as in Example 2, with E initialized to {ε}, extends E for δ-consistency, and obtains M as the hypothesis.
The correctness of the algorithm can be explained via Theorem 17(1) as follows.
The assumption of ID about S is equivalent to σ ∈ E, because σ is defined to be the reachability map restricted to S. The out-consistency condition is satisfied by initializing E = {ε}, and ensuring δ-consistency is precisely what the algorithm does. Therefore, by Theorem 17(1), the final wrapper yields a hypothesis DFA isomorphic to M .
Theorem 17(2) suggests a dual to this algorithm, where we assume a finite set E ⊆ A * such that every pair of different states of M is distinguished by some word in E. Enforcing closedness will lead to a hypothesis DFA isomorphic to M .
In a minimal DFA M with at most n states, every state is reached via a word of length at most n − 1; similarly, every pair of states is distinguished by a word of length up to n − 1. The algorithm of Arbib and Zeiger takes a wrapper (S σ − → M, M π − → 2 E ) as in Example 2, with S = E = A ≤n−1 , and by Corollary 14 (applied once for each of init M , δ M , and out M ) immediately obtains M up to isomorphism as the hypothesis. We note that taking this large C S L 2 0 1 7 29:10 CALF: Categorical Automata Learning Framework E is unnecessary, as we could simply apply Theorem 17(1), thus reducing the algorithm to ID.
Finally, we consider the L algorithm. Let the wrapper (S be as in Example 2, and let H be its hypothesis DFA. We have the following result.
be the minimization of the wrapper. Furthermore, let z = a 1 a 2 . . . a n for n the length of z and each a i ∈ A. For 0 ≤ i ≤ n, define z i = a 1 a 2 . . . a n . Each prefix of z is z i for some i. Assume that for every i there is an s i ∈ S such that rch M (s i ) = rch M (z i ). We will show by induction to n that for all i, ξ( This concludes the proof that for all i, ξ(s i ) = (m•rch H )(z i ). In particular, then, (m•e)(s n ) = ξ(s n ) = (m • rch H )(z). Because m is injective, we have e(s n ) = rch H (z). Therefore, Corollary 19. If z ∈ A * is a counterexample, i.e., L H (z) = L M (z), then adding all prefixes of z to S will increase the size of img(rch M • inc).
Thus, after L has processed at most |M | counterexamples, the conditions for Theorem 17(1) are satisfied, which means that the next hypothesis will be isomorphic to M .

Minimization
In this section we explore the connection 1 in Figure 1 between automata learning and minimization algorithms. Recall that minimization algorithms typically have two phases: a reachability analysis phase, which removes unreachable states; and a merging phase, where language-equivalent states are merged. We will rephrase these two phases in the terminology of Section 2, and we will show that Theorem 17 can be used to explain their correctness. We fix a DFA Q throughout the section.
Reachability Analysis Phase. Let R be the reachable part of Q and S any subset of R.
There is a wrapper w = (S σ − → R, R π − → Q), where σ and π are just the inclusions. The set S models the state of an algorithm performing a reachability analysis on Q. Since σ and π are inclusions, the hypothesis for w is the set S itself.
As the inclusion π is an automaton homomorphism, by Proposition 4 we can use the transition function δ : Q × A → Q and initial state q 0 : 1 → Q to compute The function ξ δ simply assigns to each state s ∈ S and each symbol a ∈ A the state δ Q (s, a). The wrapper is therefore δ R -closed if for all q ∈ S and a ∈ A we have δ Q (q, a) ∈ S; it is r 0 -closed if q 0 ∈ S. The obvious algorithm to ensure these closedness properties, namely initializing S = {q 0 } and adding δ Q (q, a) to S while there are q ∈ S and a ∈ A such that δ Q (q, a) ∈ S, is the usual reachability analysis algorithm. Since R is reachable and π injective, Theorem 17(2) confirms that this algorithm finds an automaton isomorphic to R.
Alternatively, one could let S be a subset of A * and use the wrapper (S where inc is the inclusion and rch the reachability map for R (see Definition 16). Starting from S = {ε}, the algorithm would add to S words reaching states not yet visited. This is closer to how automata learning algorithms fix closedness.
State Merging Phase. Now we are interested in finding the DFA O that is obtained from Q by merging states that accept the same language. Formally, this automaton is obtained by factorizing the observability map obs Q for Q (see Definition 16) as DA homomorphisms where res restricts a language to the words in E. Consider ξ w : Q → 2 E (i.e., the composition of the morphisms in w): even though O is not known a priori, this function can be computed by testing for a given state which words in E it accepts. Because h is an automaton homomorphism, ξ w δ O by Proposition 4 equals ξ Since h is surjective, Theorem 17(1) says that we only have to ensure δ-consistency and out-consistency. One may start with E = {ε} to satisfy the latter. For δ-consistency, for all q 1 , q 2 ∈ Q such that ξ(q 1 ) = ξ(q 2 ) we must have ξ(δ(q 1 , a)) = ξ(δ(q 2 , a)) for each a ∈ A. This can be ensured in the same fashion as for an observation table.
The algorithm we have just described reminds of Moore's reduction procedure [25]. However, using a table as data structure is less efficient because many cells may be redundant. The same redundancy has been observed in the L algorithm. In Section 7 we will show how CALF covers optimized versions of these algorithms, but first we discuss yet another application of our framework. Conformance Testing In this section we consider the connections 2 and 3 in Figure 1 between testing and, respectively, automata learning and minimization. More precisely, we consider an instance of conformance testing where a known DFA U is tested for equivalence against a black-box DFA V . One application of this problem is the realization of equivalence queries in the L algorithm, where U is the hypothesis DFA and V is the target. Testing consists in comparing U and V on a finite set of words, approximating their behavior. Following the idea of using wrappers to generalize approximations, we now capture testing using our abstract learning machinery. This will allows us to explain correctness of testing using Theorem 17. First note that given objects S and P and morphisms α : S → A and ω : Z → P , we can associate wrappers to both the known automaton U and the black-box V by composing with their reachability and observability maps: We now use several approximations in defining the tests of U against V , covering transition functions, initial states, and final states: Example 20. If U and V are DFAs, we can choose wrappers as in Example 2, namely by letting α = inc : S → A * be an inclusion and ω = res : 2 A * → 2 E a restriction. The approximations along w U are then given by ξ w U (s)(e) = L U (se), ξ w U init U (e) = L U (e), ξ w U δ U (s, a)(e) = L U (sae), and ξ w U out U (s) = L U (s), and analogously for w V . Thus, checking (4) here amounts to checking whether the DFAs accept exactly the same words from the set S · E ∪ E ∪ S · A · E ∪ S.
Our main result regarding conformance testing captures the properties of the wrappers that need to hold for the above tests to prove that U is equivalent to the black-box V .
Theorem 21. Given the above wrappers, suppose σ U ∈ E, π U ∈ M, and either σ V ∈ E and V is observable or π V ∈ M and V is reachable. Then U is isomorphic to V if and only if all the equalities (4) hold.
Proof. Assume first that U is isomorphic to V as witnessed by an isomorphism φ : U → V . By initiality, φ • rch U = rch V ; by finality, From this equality the conclusions (4) follow using Proposition 4. Now assume that the equalities (4) hold. From these equations we know that w V must be init-closed, δ-closed, δ-consistent, and out-consistent, since w U , satisfying σ U ∈ E and π U ∈ M, has these properties by Lemma 12. Note that (4) also implies that the hypothesis automata of w U and w V coincide. Moreover, σ U ∈ E and π U ∈ M imply that U is minimal because of their definition and Proposition 11 (and its dual). Using this, in combination with the assumptions for V , we can now apply Theorem 17 and conclude that U and V are isomorphic.
We now comment on the connection between testing and minimization algorithms. Minimization is a natural choice when looking for a set of words approximating U to be tested against V . Formally, recall from Section 5 that we can use reachability and state merging to find sets S, E ⊆ A * . Moreover, reachability analysis gives an inc : S → A * that makes σ U surjective and state merging gives a res : 2 A * → 2 E that makes π U injective (recall that A = A * and Z = 2 A * in the DFA setting). These, together with reachability and observability maps, give wrappers for U and V . The condition of Theorem 21 on w V may not hold right away, but these wrappers are convenient starting points for algorithmic techniques, as we now show. W-method. We instantiate the above framework to recover the W-method [14]. This algorithm assumes to be given an upper bound n on the number of states of the unknown DFA V . Assume for convenience that U and V are minimal DFAs. We apply our framework as follows: first, we build the wrapper w U = (σ U , π U ). We use the minimization algorithms from Section 5 to find S inc −→ A * and 2 A * res −→ 2 E with finite S, E ⊆ A * , which yield σ U = rch U • inc ∈ E and π U = res • obs U ∈ M. If at this point the equalities (4) do not hold, then we can conclude that U and V accept different languages, and the testing failed. If we assume they hold, then because σ U ∈ E and π U ∈ M this means that |img(ξ w V )| = |img(ξ w U )| = |U |. The image of ξ w V = π V • σ V is at least as big as the image of σ V , so |img(σ V )| ≥ |U |. By assumption we know that the size of V is at most n, and hence we update S to S · A ≤n−|U | , which yields σ V ∈ E because ε ∈ S. Now we have σ U ∈ E, π U ∈ M, and σ V ∈ E. Applying Theorem 21, we can find out whether U and V are isomorphic by testing (4) for the updated wrappers. Instantiating what the equalities in (4) mean (see Example 20), we recover the test sequences generated by the W-method.

Optimized Algorithms
When fixing a consistency defect in an observation table, we add a column to distinguish two currently equal rows. Unfortunately, adding a full column implies that a membership query is needed also for each other row. Kearns and Vazirani [20] avoid this redundancy by basing the learning algorithm on a classification tree rather than an observation table. We now show that CALF encompasses this optimized algorithm, which will allow us to derive optimizations for other algorithms. First we introduce a notion of classification tree (also called discrimination tree), close to the one by Isberner [18].
Definition 22 (Classification Tree). Given a finite S ⊆ A * , a classification tree τ on S is a labeled binary tree with internal nodes labeled by words from A * and leaves labeled by subsets of S.
The language classifier for τ is the function ω τ : 2 A * → PS that operates as follows. Given a language L ∈ 2 A * , starting from the root of the tree: if the current node is a leaf with label U ∈ PS, the function returns U ; if the current node is an internal node with label v ∈ A * , we repeat the process from the left subtree if v ∈ L and from the right subtree otherwise.
In the CALF terminology, each classification tree τ gives rise to a wrapper (S where inc is the inclusion and M is the minimal DFA for the language L that is to be learned. We define a function sift τ : A * → PS as the composition ω τ • obs M • rch M . This function sifts [20] words u ∈ A * through the tree by moving on a node with label v ∈ A * to the subtree corresponding to the value of L(uv). Applying Proposition 4, the approximated initial state map and dynamics of M can be rewritten using this function: ξ init = sift τ • ε : 1 → PS and ξ δ = sift τ • cat • (inc × id A ) : S × A → PS. Recall that ε : 1 → A * is the empty word and cat : A * × A → A * concatenates its arguments. The function ξ out : S → 2 is still the same as for an observation table: ξ out (s) = L(s). From these definitions we obtain the following notions of closedness and consistency. The wrapper is: δ-closed if for each t ∈ S · A there is an s ∈ S such that sift τ (s) = sift τ (t); δ-consistent if for all s 1 , s 2 ∈ S such that sift τ (s 1 ) = sift τ (s 2 ) we have sift τ (s 1 a) = sift τ (s 2 a) for any a ∈ A; C S L 2 0 1 7 29:14 CALF: Categorical Automata Learning Framework init-closed if there is an s ∈ S such that sift τ (s) = sift τ (ε); out-consistent if for all s 1 , s 2 ∈ S such that sift τ (s 1 ) = sift τ (s 2 ) we have L(s 1 ) = L(s 2 ). Now we can optimize the learning algorithm using Kearns and Vazirani classification trees as follows. Initially, the tree is just a leaf containing all words in S, which may be initialized to {ε}. When an out-consistency or δ-consistency defect is found, we have two words s 1 , s 2 ∈ S such that ξ(s 1 ) = ξ(s 2 ) = U , for some U ∈ PS. We also have a word v ∈ A * such that L(s 1 v) = L(s 2 v), 2 and we want to use this word to update the tree τ to distinguish ξ(s 1 ) and ξ(s 2 ). This is done by replacing the leaf with label U by a node that distinguishes based on the word v. Its left subtree is a leaf containing the words s ∈ U such that L(sv) = 0 while the s ∈ U in its right subtree are such that L(sv) = 1. This requires new membership queries, but only one for each word in S ∪ S · A that sifts into the leaf with label U ; the observation table approach needs queries for all elements of S ∪ S · A when a column is added.
The intention of having PS as the set of labels is that we maintain the trees in such a way that ξ : S → PS maps each word in S to the unique leaf it is contained in. As a result, the function ξ can be read directly from the tree. This means that, when adding a word to S, we need to add it also to the leaf of the tree that it sifts into. Words are added to S when processing a counterexample as in L and when fixing init-closedness or δ-closedness. These closedness defects occur when a word in {ε} ∪ S · A sifts into an empty set leaf. In that case we add the word to S.
Classification trees were originally developed for L , but we note that they can be used in ID as well. By the abstract nature of Theorem 17, no new correctness proof is necessary.
Transporting Optimizations to Minimization and Testing. Using our correspondence between learning and minimization, the above optimization for learning algorithms immediately inspires an optimization for the state merging phase of Section 5. The main difference is that we sift states of the automaton Q through the tree, rather than words. That is, when sifting a state q at a node with label v ∈ A * , the subtree we move to corresponds to whether v is accepted by q. Thus, instead of taking the labels of leaves from PS, we take them from PQ. The algorithm described above now creates a splitting tree [21,28] for Q.
Interestingly, in this case one does not actually have to represent the trees to perform the algorithm; tracking only the partitioning of Q induced by the tree is enough. This is because the classification of next states is contained in the classification of states: ξ δ = ξ • δ (using Proposition 4). An inconsistency consists in two states being in the same partition, but for some input a ∈ A the corresponding next states being in different partitions. One then splits the partition of the two states into one partition for each of the partitions obtained after reading a. This corresponds to (repeatedly 3 ) updating the tree to split the leaf. This algorithm that does not keep track of the tree is precisely Moore's reduction procedure [25].
The splitting tree algorithm described above can also be plugged into the W-method as it is described in Section 6. Note that the discussion about the correctness of the testing algorithm is not affected by this. The resulting algorithm is closely related to the HSI-method [22].

Conclusion
We have presented CALF, a categorical automata learning framework. CALF covers the basic definitions used in automata learning algorithms and unifies correctness proofs for several of them. We have shown that these proofs extend also to minimization and testing methods. CALF is general enough to capture optimizations for all of these algorithms and provides an abstract umbrella to transfer results between the three areas. We illustrated how an optimization known in learning can be transported to minimization and testing. We have also exploited the categorical nature of the framework by changing the category and deriving algorithms for weighted automata in Appendix A. This example shows the versatility of the framework: dynamics of weighted automata are naturally presented as coalgebras, and CALF can accommodate this perspective as well as the algebraic one, which is used traditionally for DFAs and adopted in the main text.
Related Work. Most of the present paper is based on the first author's Master's thesis [29].
Other frameworks have been developed to study automata learning algorithms, e.g. [6,18]. However, in both cases the results are much less general than ours and not applicable for example to settings where the automata have additional structure, such as weighted automata (Appendix A). Isberner [18] hints at the connection between algorithms for minimization and learning. For example, before introducing classification trees for learning, he explains them for minimization. Still, he does not provide a formal link between the two algorithms.
The relation between learning and testing was first explored by Berg et al. [7]. Their discussion, however, is limited to the case where the black-box DFA has at most as many states as the known DFA. This is because their correspondence is a stronger one that relates terminated learning algorithms to test sets of conformance testing algorithms, whereas we have provided algorithmic connections. Our Theorem 21, which allows reasoning about algorithms not making the above assumption, is completely new.
As mentioned in the introduction, a preliminary investigation of generalizing automata learning concepts using category theory was performed by Jacobs and Silva [19]. We were inspired by their work, but we note that they did not attempt to formulate anything as general as our wrappers; definitions are concrete and dependent on observation tables. As a result, there are no fully abstract proofs and no instantiations to optimizations such as the classification trees discussed in Section 7. Jacobs and Silva also investigated weighted automata, as we do in Appendix A, but only for the L algorithm. We note that Bergadano and Varricchio [8] first adapted L and ID for weighted automata. Future Work. Many directions for future research are left open. An interesting idea inspired by the relation between testing and learning is integrating testing algorithms into L . This could lead to optimizations that are unavailable when those components are kept separate. Further additions to CALF may include an investigation of the minimality of hypotheses and a characterization of the more elementary steps that are used in the algorithms. The only fully abstract correctness proofs for concrete algorithms at the moment are for the minimization algorithms and ID, where correctness follows from a condition that can be formulated on an abstract level. We would like to have an abstract characterization of progress for the other algorithms, which are of a more iterative nature. Finally, a concrete topic is optimizations for automata with additional structure, such as nondeterministic, weighted, and nominal automata. To the best of our knowledge, no analogue of classification trees exists for learning these classes. If such analogues turn out to exist, then the correspondences discussed in Section 5 and Section 6 would provide optimized learning and testing algorithms as well.
It is our long-term goal to exploit the practical aspects of the framework. For more details, see our project website http://calf-project.org.

A Linear Weighted Automata
So far we have only considered DFAs as examples of automata. In this appendix, we exploit the categorical nature of CALF by changing the base category in order to study linear weighted automata.
Let C be the category Vect op , the opposite of the category of vector spaces and linear maps over a field F. We need the opposite category because the dynamics of our automata will be coalgebras rather than the algebras that are found in Definition 15. We interpret everything in Vect rather than Vect op . The automata we consider are for I = Y = F and F = (−) A , where the latter for a finite set A and a vector space X is given by the set of functions X A with a pointwise vector space structure. On linear maps f : W → X we have f A : W A → X A given by f A (g)(a) = f (g(a)). Here an automaton, called a linear weighted automaton (LWA), is a vector space Q with linear maps as in the diagram.
Given a set U , let V (U ) be the free vector space generated by U , the elements of which are formal sums j∈J v j × u j for finite sets J, {v j } j∈J ⊆ F, and {u j } j∈J ⊆ U . The operation V (−) is a functor Set → Vect that assigns to a function f : U → W for sets U and W the linear map V (f ) : V (U ) → V (W ) given by V (f )(u) = f (u). The functor V is left adjoint to the forgetful functor Vect → Set that assigns to each vector space its underlying set. Given a vector space W and a function f : U → W , the linearization of f is the linear map Conversely, a linear map with domain V (U ) is completely determined by its definition on the elements of U . The adjunction implies that this is a bijective correspondence between functions U → W and linear maps V (U ) → W . Note that F is isomorphic to V (1), so the initial state map init : F → Q of an LWA Q is essentially an element of Q, namely init(1). Moreover, any linear map is determined by its value on the basis vectors of its domain, which gives us a finite representation for LWAs with a finite-dimensional state space. This representation is known as a weighted automaton. The initial input system in this setting is essentially the same as for DAs in Set, but enriched with a free vector space structure.
forms an initial input system. C S L 2 0 1 7 29:18 CALF: Categorical Automata Learning Framework Proof. Given an input system Q with initial state map init Q : V (1) → Q and dynamics δ Q : Q → Q A , define a linear map rch : V (A * ) → Q by rch(ε) = init Q (1) and rch(ua) = δ Q (rch(u))(a). Note that rch is an input system homomorphism. Any input system homo- )(a) and is therefore, by induction on the length of words, equal to rch.
forms a final output system.
We use the (surjective linear maps, injective linear maps) factorization system in Vect. The details are similar to those in Set, but now the image of a linear map f : U → V is a subspace of V . To see that the unique diagonals are the same as in Set, note the following.
A language in this setting is a linear map L : V (A * ) → F. One obtains the minimal LWA for the language L by taking the image of the observability map t : V (A * ) → F A * of the automaton V (A * ) with output map L. Note that if we take the initial state map of F A * to be t • init V (A * ) , then t is an LWA homomorphism. Its image is an LWA because each category of automata has a factorization system inherited from the base category. It must be the minimal LWA because by initiality and finality the factorization of t must be (rch M , obs M ).
The dimension of a vector space U is denoted dim(U ). The kernel of a linear map f : U → W is given by ker(f ) = {u ∈ U | f (u) = 0}. It is a standard result that if U is of finite dimension, then dim(U ) = dim(ker(f )) + dim(img(f )). (5) Learning. We recover adaptations of L and ID for LWAs as originally developed by Bergadano and Varricchio [8]. Jacobs and Silva [19] also instantiated their categorical reformulation of L to this setting. In active learning of LWAs, we assume there is a language L : V (A * ) → F such that the state space of the minimal LWA M accepting L is of finite dimension. Given a finite set E ⊆ A * , the function res : F A * → F E given by res(L)(e) = L(e) is a linear map. To select elements of V (A * ), we may take a finite subset S ⊆ A * and apply V to the inclusion inc : S → A * to obtain a linear map V (inc) : V (S) → V (A * ) and hence a wrapper All approximated linear maps are as expected: ξ : V (S) → F E is given by ξ(s)(e) = L(se), ξ δ : V (S) → (F E ) A is given by ξ δ (s)(a)(e) = L(sae), ξ out : V (S) → F is given by ξ out (s) = L(s), and ξ init : F → F E is given by ξ init (1)(e) = L(e). Although these maps can be represented in the same kind of observation table used for learning a DFA (except that we have a different output set here), the notions of closedness and consistency are different. This is because we have to deal with the larger domains of the actual linear maps. The characterizations of these properties can still be derived from Proposition 10, as a result of Proposition A.3. It follows directly that δ-closedness holds if and only if for all l ∈ V (S) and a ∈ A there is an l ∈ V (S) such that ξ(l ) = ξ δ (l)(a). To simplify this, we have the following result. are such that ξ(l j ) = ξ δ (s j )(a) for all j ∈ J, then ξ j∈J v j × l j = ξ δ j∈J v j × s j (a).

Proof. We have
Thus, δ-closedness really says that for all sa ∈ S · A there must be an l ∈ V (S) such that ξ(l) = ξ δ (s)(a). As for δ-consistency, this property requires that for all l 1 , l 2 ∈ V (S) such that ξ(l 1 ) = ξ(l 2 ) we must have ξ δ (l 1 )(a) = ξ δ (l 2 )(a) for all a ∈ A. Using subtraction, this says that for all l ∈ V (S) with ξ(l) = 0 we must have ξ δ (l)(a) = 0 for all a ∈ A, where 0 : E → F is given by 0(e) = 0 for all e ∈ E. Analogously, init-closedness requires there to be an l ∈ V (S) such that ξ(l) = ξ init (1) while out-consistency states that for all l ∈ V (S) such that ξ(l) = 0 we must have L(l) = 0.

CALF: Categorical Automata Learning Framework
Closedness can be determined simply by solving systems of linear equations. Consistency is less trivial. Define the transpose of a table for the language L given by S, E ⊆ A * as the table with row labels rev(E) and column labels rev(S) for the language rev(L), where rev reverses all words in a language. We will show that consistency of a Proof. Suppose there is an l ∈ V (S) such that ξ(l) = 0. For all a ∈ A and e ∈ E there are by closedness of the transposed table a finite set J, {v j } j∈J ⊆ F, and {e j } j∈J ⊆ E such that for every s ∈ S, Let K be a finite set and {v k } k∈K ⊆ F and {s k } k∈K ⊆ S such that l = k∈K v k × s k . Then Analogously, one can show that init-closedness of the transposed table implies init-consistency of the original one. If a closedness defect is found, we have a word u ∈ A * such that (res • obs M • rch M )(u) is not a linear combination of any row indexed by words from S. Because we have subtraction and scalar division, this also means that each of the rows indexed by S that is not a linear combination of other rows is also not a linear combination of other rows and (res • obs M • rch M )(u). Therefore, adding u to S increases the dimension of the hypothesis. The dimension of the hypothesis cannot exceed the dimension of the target M (see Appendix B), which is of finite dimension, so this process must terminate.
Note that the top part of a table in this setting can be seen as a matrix, and that transposing the table transposes this matrix. By fixing a closedness defect in the transpose of the table, the dimension of its hypothesis increases. This dimension is precisely the column rank of the original matrix. Since the column and row ranks of a matrix are equal, the dimension of the hypothesis of the original table must have increased.
The map σ : V (S) → M is surjective just if for each m ∈ M there is an l ∈ V (S) such that rch M (l) = m. Equivalently, the set {rch M (s) | s ∈ S} needs to span M . Note that this means the set needs to include one of the (finite) bases of M . Thus, we have an adaptation of ID for LWAs that assumes to be given such a finite set S and enforces out-consistency and δ-consistency to obtain, by Theorem 17(1), a hypothesis isomorphic to M .
As for L , Proposition 18 carries over almost immediately. Due to the similarity, we omit the proof.
Proposition A.6. If for every prefix p of a word z ∈ A * there exists an l ∈ V (S) such that rch M (l) = rch M (p), then L H (z) = L M (z).

Corollary 7.
If z ∈ A * is a counterexample, i.e., L H (z) = L M (z), then adding all prefixes of z to S will increase the dimension of img(rch M • inc).
Once the dimensions of img(rch M • inc) and M coincide, rch M • inc is surjective and we can apply Theorem 17(1). Thus, the number of required counterexamples is bounded by the dimension of M .
Reachability Analysis. Let Q be a finite-dimensional LWA and R its reachable part. Given a finite subset S ⊆ R, we have a wrapper (V (S) σ − → R, R π − → Q) in Vect, where σ and π are the inclusions. This wrapper is init-closed if there is l ∈ V (S) such that ξ(l) = init Q (1), which can be satisfied by initializing S = {ε}. The wrapper is δ-closed if for all s ∈ S and a ∈ A there is an l ∈ V (S) such that ξ(l) = δ Q (ξ(s))(a). If for some sa this is not the case, we add it to S. As in learning, the dimension of the hypothesis increases by doing so, and therefore the process terminates. Using Theorem 17(2), the final hypothesis is isomorphic to R. −→ F E ). The linear map ξ : Q → F E gives the output of each state on the words in E. The wrapper is out-consistent if for all q 1 , q 2 ∈ Q such that ξ(q 1 ) = ξ(q 2 ) we have out(q 1 ) = out(q 2 ). If the last equation fails, we may add ε to E to distinguish ξ(q 1 ) and ξ(q 2 ). The wrapper is δ-consistent if for all q 1 , q 2 ∈ Q and a ∈ A such that ξ(q 1 ) = ξ(q 2 ) we have ξ(δ(q 1 )(a)) = ξ(δ(q 2 )(a)). If this last equation fails on some e ∈ E, we may add ae to E to distinguish ξ(q 1 ) and ξ(q 2 ). As in learning, this decreases the dimension of the kernel of ξ, which guarantees termination. Using Theorem 17(1), the final hypothesis is isomorphic to O.
Testing. Consider a known finite-dimensional LWA X and an unknown finite-dimensional LWA Z, both of which are minimal. Using the minimization algorithms (but with S for the reachability analysis a subset of A * ), we can find finite S, E ⊆ A * such that ε ∈ S and the wrapper w X = (σ X , π X ) = (V (S) satisfies σ X ∈ E and π X ∈ M. Define w Z = (σ Z , π Z ) analogously. If at this point the equalities given by Theorem 21 do not hold, we can conclude that X and Z accept different languages. Assume these equalities do hold. By Corollary 14 this implies dim(img(ξ w Z )) = dim(U ). C S L 2 0 1 7 29:22

CALF: Categorical Automata Learning Framework
Assuming a given upperbound n on the dimension of Z, updating S to S · A ≤n−dim(X) yields σ Z ∈ E. Applying Theorem 21, we can find out whether X and Z are isomorphic by testing (7) for the updated wrappers. That is, we have an adaptation of the W-method for LWAs.

B
The Hypothesis is Smaller than the Target Given a wrapper (S σ − → T, T π − → P ) in an arbitrary category C with an (E, M) factorization system, the hypothesis can be defined using three successive factorizations, as shown on the right. We now explain for the discussed concrete settings why the hypothesis is always "smaller" than the target, for the appropriate notion of size in each category.
In the Category of Sets. We know that if T is a finite set, then J, being a subset of T , is a finite set with |J| ≤ |T |. Because there is a surjective function J → H, we conclude that H is finite and |H| ≤ |J| ≤ |T |.
In the Category of Vector Spaces. Assume T is of finite dimension. Since J is a subspace of T , we have that J is a finite-dimensional vector space with dim(J) ≤ dim(T ). Note that there exists a surjective linear map x : J → H, so H is finite-dimensional and dim(img(x)) = dim(H). It then follows from (5) in Appendix A that dim(ker(x)) = dim(J) − dim(H), so we must have dim(H) ≤ dim(J) ≤ dim(T ).


The moduli space of two-convex embedded tori

In this short article we investigate the topology of the moduli space of two-convex embedded tori $S^{n-1}\times S^1\subset \mathbb{R}^{n+1}$. We prove that for $n \geq 3$ this moduli space is path-connected, and that for $n = 2$ the connected components of the moduli space are in bijective correspondence with the knot classes associated to the embeddings. Our proof uses a variant of mean curvature flow with surgery developed in our earlier article (arXiv:1607.05604) where neck regions are deformed to tiny strings instead of being cut out completely, an approach which preserves the global topology, embeddedness, as well as two-convexity.

Introduction
The goal of this short article is to extend the results from our previous paper [3] to the case of two-convex embedded tori. In our previous paper we considered the moduli space of two-convex embedded spheres, i.e. the space M 2−conv (S n ) = Emb 2−conv (S n , R n+1 )/Diff(S n ) (1.1) Theorem 1.3. The path-components of the moduli space of two-convex embedded tori are given by π 0 M 2−conv (S n−1 × S 1 ) ∼ = K (M 2−conv (S 1 × S 1 )) , n = 2, 0, n ≥ 3, (1.4) where K denotes the set of knot classes. This means that M 2−conv (S n−1 × S 1 ) is pathconnected for n ≥ 3, while for n = 2 we have that two mean-convex embedded tori are in the same path-component of their moduli space if and only if they have the same knot class.
We recall that for n = 2 the notion of two-convexity simply becomes the more basic notion of mean-convexity, i.e. the property that the mean curvature vector points inwards at every point. The knot class of an embedded torus T ⊂ R 3 is defined as follows: Choose an embedding map ϕ : S 1 × S 1 → R 3 with ϕ(S 1 × S 1 ) = T such that ϕ can be extended to an embeddingφ : D 2 × S 1 → R 3 of the solid torus bounded by T . The knot class of T is then defined as the knot equivalence class of (1.5) The knot class of an embedded torus is of course well defined, i.e. independent of the choice of extendible parameterization, and preserved under isotopies (see Section 2).
The result of Theorem 1.3 is new even in the seemingly classical case n = 2. While the space of embedded tori in R 3 is a well studied classical object, it seems that none of the known topological methods deforming such tori into one another can actually preserve mean-convexity, i.e. the only method we know to prove Theorem 1.3 even in dimension n = 2 is by using our geometric analytic approach based on mean curvature flow.
Let us now outline the main steps of the proof of Theorem 1.3, following the framework from our previous article [3].
Given a 2-convex embedded closed hypersurface M 0 ⊂ R n+1 , we consider its mean curvature flow with surgery {M t } t∈[0,∞) as provided by the existence theorem from [5,Thm. 1.21]. The flow always becomes extinct in finite time T < ∞. Around all but finitely many times the flow is a smooth mean curvature flow, but at some finite non-empty collection of times surgeries and/or discarding will occur.
By the canonical neighborhood theorem [5,Thm. 1.22] each discarded component is either a convex sphere of controlled geometry, a capped-off chain of ε-necks or an ε-loop. This information is sufficient to construct an explicit 2-convex isotopy from any discarded component to what we call a marble graph (see Section 3). Roughly speaking, a marble graph is a family of disjoint spheres, smoothly glued to one another along tubular neighborhoods of some admissible curves.
While surgeries disconnect the hypersurfaces into different connected components, for our topological application we eventually have to connect the pieces again. To this end, we use the 2-convex connected sum operation from [3]. In this construction, two 2-convex hypersurfaces are glued together along tiny tubes around admissible curves (so-called strings) connecting the hypersurfaces (see Section 2 for details). If the string radius r s is chosen to be much smaller than the surgery scales used in the mean curvature flow, then these different scales barely interact. As in [3], we can therefore argue by backwards induction on the surgery times that at each time every connected component is isotopic via 2-convex embeddings to a marble graph, see Theorem 3.3. In fact, this result holds for any embedded 2-convex closed hypersurface in R n+1 without topological assumption.
If the initial hypersurface M 0 has the topology of a torus, it must thus be isotopic via 2-convex embeddings to a marble circuit -a marble graph with only one loop (see Section 3). Having constructed a 2-convex isotopy from the original torus to a marble circuit, in Section 4 we finally show that such a circuit is isotopic (again via 2-convex embeddings) to an arbitrarily thin tubular neighborhood of a knot γ. Finally, it is easy to see that such thin tubular neighborhoods are always 2-convex isotopic for n ≥ 3, while for n = 2 they are mean-convex isotopic if and only if they represent the same knot class.

Preliminaries
The goal of this section is to collect and prove various preliminary results.
We start by explaining that the knot class of an embedded torus is well defined.
Definition 2.1 (Knot class). Two embedded closed curves γ i : S 1 → R 3 , i = 1, 2 are said to belong to the same (non-oriented) knot equivalence class if there exists an ambient isotopy F : where T is a solid torus in R 3 , the knot class of F 1 (1, e iθ ) is the same as the knot class of F 2 (1, e iθ ).
For the proof of Proposition 2.2 we need the following lemma. Lemma 2.3. Let ι : S 1 × S 1 → D 2 × S 1 be the standard inclusion and let φ : S 1 × S 1 → S 1 × S 1 be a diffeomorphism. Then there exists a diffeomorphism φ : if and only if the map p 2 (φ(·, 1)) : S 1 → S 1 , where p 2 is the projection to the second component, has vanishing degree.
Restrict φ to a map φ ∈ Diff(S 1 ×S 1 ) such that φ • ι = ι• φ. By the proof of the previous lemma we know that φ is isotopic to a map of the form φ A (e 2πix , e 2πiy ) = (e 2πi(ax+by) , e 2πidy ) , where a, d ∈ {±1} and b ∈ Z. After possibly reversing orientation (which is allowed by our definition of knot equivalence) we can assume that d = +1. By the isotopy extension property we thus see that in D 2 × S 1 the knots φ(1, e 2πis ) and (e 2πibs , e 2πis ) are equivalent.
But in D 2 × S 1 the knot (e 2πibs , e 2πis ) is clearly equivalent to the knot (0, e 2πis ), which is in turn equivalent to the knot (1, e 2πis ). This proves the assertion.
For the sake of convenience, in this paper, instead of closed embedded hypersurfaces M ⊂ R n+1 we often talk about the compact domain K bounded by M. These two points of view are of course equivalent, since K determines M = ∂K, and vice versa.
Given a solid torus T ⊂ R 3 by Proposition 2.2 we can associate to it a knot class. Given a family of tori T we denote by K(T ) the set of knot classes. Clearly if T 1 , T 2 ∈ T are isotopic, then they are in the same knot class. The far less obvious part of the statement of Theorem 1.3, which we will prove in the bulk of the paper, is that whenever two mean-convex tori T 1 , T 2 have the same knot class, then there exists a mean-convex isotopy between them. Generalizing mean-convex domains in R 3 , we actually consider 2-convex domains in R n+1 for general n, so let us now discuss some basic notions about the domains we consider.
at all points p ∈ ∂K. Here, λ 1 ≤ λ 2 ≤ . . . ≤ λ n denote the principal curvatures, i.e. the eigenvalues of the second fundamental form A of ∂K.
Here smoothness is taken with respect to the smooth topology of submanifolds with boundary in R n+1 . We say that two 2-convex domains K, The goal for the rest of this section is to recall the gluing theorem (and some other required definitions) from [3]. The input for the gluing map is a controlled configuration of 2-convex domains and curves given by the following three definitions.
We first recall that a 2-convex domain K ⊂ R n+1 is called α-noncollapsed (see [9,1,4]) if each boundary point p ∈ ∂K admits interior and exterior balls tangent at p of radius at least α/H(p).
We write A = (α, β, c H , C A ) to keep track of the constants. We denote by D the set of all (possibly disconnected) 2-convex smooth compact domains K ⊂ R n+1 , and we denote by We denote by C b the set of all b-controlled curves γ ⊂ R n+1 . Definition 2.14 (Controlled configuration of domains and curves). We call a pair (D, γ) ∈ D A × C b an (A, b)-controlled configuration if the following holds.
(a) The interior of γ lies entirely in R n+1 \ D. (b) The endpoints of γ satisfy the following properties: • If p ∈ ∂γ ∩ ∂D, then γ touches ∂D orthogonally there.
The gluing map from Theorem 2.16 below transforms an (A, b)-controlled configuration (D, γ) ∈ X A,b into a 2-convex domain K ∈ D. In order to state precisely how K looks like at loose ends of γ, we also need the following definition of capped-off tubes from [ A left capped-off tube CN − r (γ, p) is defined analogously. If p is an endpoint of the curve γ, we simply talk about the capped-off tube CN r (γ, p) at p, meaning CN + r (γ, p) if p = γ(a 1 ) and CN − r (γ, p) if p = γ(a 0 ).
We can now recall the main gluing theorem from [3].
(2) We have where N r (γ) denotes the (solid) r-tubular neighborhood of γ. The collection of balls {B δ(r) (p)} p∈∂γ is disjoint. (3) If p ∈ ∂γ \ ∂D and γ p denotes the connected component of γ containing p as its endpoint, then where CN r (γ p , p) denotes the capped-off r-tube around γ p at p. (4) The construction is local: Moreover, in the special case that γ ∩ B δ(r) (p) is a straight line and that D ∩ B δ(r) (p) = B R (q) ∩ B δ(r) (p) for some q ∈ R n+1 and R > r, then G r (D, γ) ∩ B δ(r) (p) is given by the explicit rotationally symmetric construction from [3, Prop. 4.2].

Transforming 2-convex domains to marble graphs
Using the gluing map from Theorem 2.16, we can now define marble graphs by extending our concept of a marble tree from [3]. (1) D = iB rm (p i ) is a union of finitely many balls ("marbles") of radius r m .
(2) The curve γ is such that: • there are no loose ends, i.e. ∂γ \ ∂D = ∅, • γ ∩B 3rm (p i ) is a union of straight rays for all i, If D ∪ γ is contractible, then G is called a marble tree. If D ∪ γ is homotopy equivalent to S 1 then G is called a marble circuit.
Remark 3.2. Note that by the moreover-part of Theorem 2.16 and by the structure of (D, γ) as in Definition 3.1, G does not depend on the precise value of the control parameters. We can thus freely adjust the control parameters and shrink r m , r s whenever needed.
The goal of this section is to prove the following structure theorem for 2-convex domains.
Theorem 3.3. Every 2-convex domain is 2-convex isotopic to a marble graph.
Proof. The proof of this theorem uses three steps, generalizing the argument from our previous article [3]. Hence, at some points we only outline the argument and give precise references to steps that have been carried out already in our previous article.
Step 1: Mean curvature flow with surgery. The theory of mean curvature flow with surgery was first introduced by Huisken-Sinestrari [7] for 2-convex hypersurfaces M n ⊂ R n+1 with n ≥ 3. Later, a theory for surfaces was developed by Brendle-Huisken [2] and an approach which works in all dimensions was given by Haslhofer-Kleiner [5]. We follow the framework of the last mentioned article here.
Loosely speaking, a mean curvature flow with surgery starting at a 2-convex domain K 0 is a collection of finitely many smooth 2-convex mean curvature flows t i by surgeries and/or discarding of connected components. More precisely, one first replaces finitely many (possibly zero) strong δ-necks with center p j i and radius r neck by pairs of opposing standard caps K st , obtaining the post-surgery domain for an existence result of such a mean curvature flow with surgery. By comparison with spheres, the flow always becomes extinct in finite time, that is K + t ℓ = ∅. In particular, at the last singular time t ℓ , there is only discarding of all the remaining components and no surgery.
The existence theorem is accompanied by the canonical neighborhood theorem, which gives a precise description of the regions of high curvature that are discarded. The upshot, see [5, Cor. 1.25] and in particular its proof, is that all discarded components are diffeomorphic to D n+1 or D n × S 1 . Moreover, the components that are diffeomorphic to D n+1 are either (a) convex or (b) capped ε-tubes and the components diffeomorphic to D n × S 1 are (c) ε-tubular loops. The precise definitions for the cases (b) and (c) are as follows. (1) A capped ε-tube is a 2-convex compact domain K ⊂ R n+1 diffeomorphic to a ball, together with a controlled connected curve γ ⊂ K with endpoints on ∂K such that: (a) Ifp ± denote the endpoints of γ then K ∩B 2CH −1 (p ± ) (p ± ) is ε-close (after rescaling to unit size) to either (a) a (C, ε)-cap or (b) a standard-cap K st . Here, a (C, ε)-cap is a strictly convex domain K ⊂ R n+1 such that every point outside some compact subset of size C < ∞ is the center of an ε-neck of radius 1.
is the center of an ε-neck with axis given by ∂ s γ(p). Moreover, if r denotes the radius of the ε-neck with center p, then γ is ε −2 r-controlled in B ε −1 r (p). (2) An ε-tubular loop is a 2-convex compact domain K ⊂ R n+1 which deformation retracts to S 1 , together with a controlled closed curve γ ⊂ K such that every point p ∈ γ is the center of an ε-neck with axis given by ∂ s γ(p). Moreover, if r denotes the radius of the ε-neck with center p, then γ is ε −2 r-controlled in B ε −1 r (p).
By this theory, we can evolve any 2-convex domain K 0 by mean curvature flow with surgery until it becomes extinct, preserving 2-convexity and having a precise description of all the discarded components during the process. For a more detailed summary of the essential results described above, we refer to Sections 6 and 8 in our previous article [3].
Step 2: Isotopies for surgery necks and discarded components. In [3], we explained how to geometrically undo the surgery by gluing the two surgery caps back together along a tiny string as described in the gluing construction in Theorem 2.16 above.
Lemma 3.5 (Combination of Lemma 6.4 and Proposition 6.5 from [3]). For small enough δ, if K ♯ is obtained from K by replacing a strong δ-neck (with center 0 and radius 1) by a pair of standard caps (with cap separation parameter Γ), then there is an almost straight line γ between the tips of the standard caps and for r s small enough, there exists an isotopy between K and G rs (K ♯ , γ) that preserves 2-convexity and is trivial outside B 6Γ (0). Lemma 3.5 allowed us to construct an isotopy from a capped ε-tube to a marble graph. Lemma 3.6 (Isotopy for capped ε-tubes, Proposition 7.4 of [3]). For ε small enough, every capped ε-tube (see Definition 3.4) is 2-convex isotopic to a marble tree. Moreover, there exists a finite collection I of ε-neck points with |p−q| ≥ 100 max{ε −1 , Γ} max{H −1 (p), H −1 (q)} for every pair p, q ∈ I, such that the isotopy is monotone outside p∈I B 6ΓH −1 (p) (p).
Similar to this lemma, we now prove a version for ε-tubular loops. This result was not needed for the argument in [3], as there our topological assumption ruled out discarded components of this type. Lemma 3.7 (Isotopy for ε-tubular loops). For ε small enough, every ε-tubular loop (see Definition 3.4) is 2-convex isotopic to a marble circuit. Moreover, there exists a finite collection I of ε-neck points with |p−q| ≥ 100 max{ε −1 , Γ} max{H −1 (p), H −1 (q)} for every pair p, q ∈ I, such that the isotopy is monotone outside p∈I B 6ΓH −1 (p) (p).
Proof. In the following, we assume that ε and r s are small enough. We denote by K an ε-tubular loop as in Definition 3.4. The isotopy from K to a marble circuit is constructed in two steps. First, let I ⊂ γ be a maximal collection of ε-neck points such that for any pair p, q ∈ I the distance between the points is at least 100 max{ε −1 , Γ} max{H −1 (p), H −1 (q)}.
For each p ∈ I, we replace the ε-neck with center p by a pair of standard caps as described in [5,Def. 2.4] and denote the post-surgery domain by K ♯ . This is possible by [5,Prop. 3.10]. Let γ be the disjoint union of almost straight curves connecting the opposing standard caps as in [3,Lem. 6.4]. Note that γ is Hausdorff close to γ \ K ♯ . Then, by Lemma 3.5, there exists a 2-convex isotopy between K and G rs (K ♯ , γ).
Note that each connected component of K ♯ is a small perturbation of a capped-off cylinder (capped-off on both sides) and can therefore be deformed monotonically to a (slightly smaller) capped-off cylinder as described in Definition 2.15. Then, letting this capped-off cylinder flow by mean curvature, it will instantaneously become strictly convex, so it is certainly 2-convex isotopic to a round ball. 1] be the union of the above isotopies between the connected components of K ♯ and balls. Denote by r min the smallest radius among these balls and let {K ♯ t } t∈ [1,2] be an isotopy that concatenates smoothly at t = 1 and shrinks all balls further to a smaller radius, say r min /10. Moreover, let { γ t } t∈[0,2] be the family of curves which follows K ♯ t by normal motion starting at γ 0 = γ. Then {G rs (K ♯ t , γ t )} t∈[0,2] provides the second part of the 2-convex isotopy we want to construct, transforming G rs (K ♯ , γ) to a marble circuit.
Remark 3.8. It is trivial to see that also discarded components of type (a) can be transformed to marble graphs. In fact, if K ⊂ R n+1 is a smooth compact convex domain, we can simply choose a single marbleB rm ⊂ K and then {K t } t∈[0,1] given by K t := tB rm + (1 −t)K is a monotone convex isotopy (trivial outside K), with K 0 = K and K 1 =B rm .
Step 3: Gluing isotopies together using backwards induction. We now fix ε small enough such that all applications of the previous lemmas as well as the application of [3,Lem. 9.4] below are justified. Depending on ε and the parameters of the initial domain K 0 we then choose the surgery parameters from [5] precise enough, namely the neck precision parameter δ small enough, and the trigger-curvature, neck-curvature and thick-curvature, as well as their ratios, large enough.
Consider the evolution by mean curvature flow with surgery as described in Step 1, with initial condition K 0 . Recall that at each t i finitely many δ-necks with center p j i and radius r neck are replaced by a pair of standard caps. Let B j i := B 10Γr neck (p j i ), and observe that these balls are pairwise disjoint (see [5,Prop. 2.5]). Similarly, for each discarded component C j i which is either a capped ε-tube or an ε-tubular loop, by Lemma 3.6 or Lemma 3.7, respectively, there is a finite collection of ε-neck points, whose centers and radii we denote by p jk i and r jk i . We then set B jk i := B 10Γr jk i (p jk i ). The isotopy which we will construct will be monotone outside the set of pairwise disjoint balls Now, let A i be the assertion that every connected component of K i = K − t i is 2-convex isotopic to a marble graph. Since at time t ℓ there is only discarding and no surgery, we know that A ℓ holds, having shown in Step 2 that all discarded components are isotopic to marble graphs. We now prove the following (backwards) inductive step.
Claim 3.10. If 0 < i < ℓ and A i+1 holds, so does A i .
Proof. Smooth evolution by mean curvature flow provides a monotone isotopy between K + t i and K − t i+1 . Recall that K + t i is obtained from K i = K − t i by performing surgery on a collection of disjoint δ-necks and/or discarding connected components that are entirely covered by canonical neighborhoods. By the inductive hypothesis, the connected components of K − t i+1 and hence of K + t i are isotopic to marble graphs, and by Step 2 the discarded components are isotopic to marble graphs as well. It follows that all components of K ♯ t i are isotopic to marble graphs.
Let {L t } t∈[0,1] denote such an isotopy deforming L 0 = K ♯ t i into a union of marble graphs L 1 , which is monotone outside X. We now want to glue together the isotopies of the components. If there was only discarding at time t i there is no need to glue, hence we can assume that L 0 has at least two components.
For each surgery neck at time t i , select an almost straight line γ j i between the tips of the corresponding pair of standard caps and set γ 0 = j γ j i . By Lemma 3.5, the domain with an isotopy that is trivial outside X. Finally, to get an isotopy G rs (L t , γ t ) it remains to construct a suitable family of curves {γ t } t∈[0,1] along which we can do the gluing. We start with γ 0 and then essentially define γ t by following the points where γ t touches ∂L t via normal motion. It can happen at finitely many times t that γ t hits ∂X. In this case, we modify γ t according to [3,Lem. 9.4] to avoid the surgery regions. Then G rs (L t , γ t ) t∈[0,1] gives the desired 2-convex isotopy.
By backwards induction on i, we then in particular obtain that A 1 holds, i.e. K 1 = K − t 1 is 2-convex isotopic to a marble graph. Finally, smooth mean curvature flow provides a 2convex isotopy between K 1 and K 0 (in particular, K 1 has only one connected component). We conclude that K 0 is 2-convex isotopic to a marble graph, proving the theorem.

Deforming marble circuits and conclusion of the proof
We will now prove the following deformation theorem for marble circuits. Proof. The proof is a generalization of the proof of [3,Thm. 5.2], where we showed that every marble tree is 2-convex isotopic to a round ball. Our previous proof was based on two basics steps: rearrangements and marble reduction. Given some p ∈ D ∩ γ, the rearrangement step allowed us to push all other curves out of the hemisphere with pole p (see [3,Lem. 5.3]). The reduction step allowed us (after applying rearrangements) to remove a leaf of the marble tree via 2-convex isotopies (see [3,Prop. 5.5]).
By repeatedly choosing a leaf, rearranging and applying reduction, we thus see that every marble circuit is isotopic to a marble circuit G rs (D, γ) with the property that for every connected component B of D, B ∩ γ consists exactly of two antipodal points.
After possibly shrinking r m and r s as in Remark 3.2 and then rescaling the configuration so that r m = 1, the moreover-part of Theorem 2.16 implies that for each p ∈ B ∩ γ the configuration around p is given by the explicit rotationally symmetric gluing model C ̺ −1 (rs) from [3,Prop. 4.2]. We can then use the isotopy (C δ ) δ∈(̺ −1 (rs),0.99) around p, while increasing the string radius r s to ̺(0.99) elsewhere. Finally, using a linear isotopy (see [3,Prop. 3.12]), this can be perturbed to a solid tube of radius one, which we can deform radially to an arbitrarily thin torus.
We can now finish the proof of our main theorem.
Proof of Theorem 1.3. Let T, T ′ ⊂ R n+1 be two 2-convex tori. If n = 2, we assume in addition that T and T ′ have the same knot class. We recall from Section 2, the knot class of a torus is invariant under isotopies.
By Theorem 3.3 and the topological assumption, T and T ′ are 2-convex isotopic to marble circuits C and C ′ , respectively. By Theorem 4.1 the marble circuits C and C ′ are 2-convex isotopic to (solid) thin tori N r (γ) and N r (γ ′ ), for some closed embedded curves γ, γ ′ . In the case n = 2, there exists and ambient isotopy deforming γ to γ ′ since we assumed that T and T ′ have the same knot class. In the case n ≥ 3, there also exists an ambient isotopy deforming γ to γ ′ since there are no nontrivial knots in R n+1 for any n ≥ 3. Finally, by choosing r very small, it is easy to see that such an ambient isotopy gives rise to a 2-convex isotopy between N r (γ) and N r (γ ′ ).