**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Unique decomposition of homogeneous languages and application to isothetic regions

Abstract

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of homogeneous languages of length n is an element of N. One recovers the isothetic regions from (Haucourt 2017, to appear (online since October 2017)) by considering the alphabet of connected subsets of the space vertical bar G vertical bar, viz the geometric realization of a finite graph G. Factoring the geometric model of a conservative program amounts to parallelize it, and there exists an efficient factoring algorithm for isothetic regions. Yet, from the theoretical point of view, one wishes to go beyond the class of conservative programs, which implies relaxing the finiteness hypothesis on the graph G. Provided that the collections of n-dimensional isothetic regions over G (denoted by R-n vertical bar G vertical bar) are co -unital distributive lattices, the prime decomposition of isothetic regions is given by an algorithm which is, unfortunately, very inefficient. Nevertheless, if the collections R-n vertical bar G vertical bar satisfy the stronger property of being Boolean algebras, then the efficient factoring algorithm is available again. We relate the algebraic properties of the collections R-n vertical bar G vertical bar to the geometric properties of the space I GI. On the way, the algebraic structure R-n vertical bar G vertical bar is proven to be the universal tensor product, in the category of semilattices with zero, of n copies of the algebraic structure R-1 vertical bar G vertical bar.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related concepts (29)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Permutation group

In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G (which are thought of as bijective

Space

Space is a three-dimensional continuum containing positions and directions. In classical physics, physical space is often conceived in three linear dimensions. Modern physicists usually consider it,

Related publications (5)

Loading

Loading

Loading

K-Theory was originally defined by Grothendieck as a contravariant functor from a subcategory of schemes to abelian groups, known today as K0. The same kind of construction was then applied to other fields of mathematics, like spaces and (not necessarily commutative) rings. In all these cases, it consists of some process applied, not directly to the object one wants to study, but to some category related to it: the category of vector bundles over a space, of finitely generated projective modules over a ring, of locally free modules over a scheme, for instance. Later, Quillen extracted axioms that all these categories satisfy and that allow the Grothendieck construction of K0. The categorical structure he discovered is called today a Quillen-exact category. It led him not only to broaden the domain of application of K-theory, but also to define a whole K-theory spectrum associated to such a category. Waldhausen next generalized Quillen's notion of an exact category by introducing categories with weak equivalences and cofibrations, which one nowadays calls Waldhausen categories. K-theory has since been studied as a functor from the category of suitably structured (Quillen-exact, Waldhausen, symmetric monoidal) small categories to some category of spectra1. This has given rise to a huge field of research, so much so that there is a whole journal devoted to the subject. In this thesis, we want to take advantage of these tools to begin studying K-theory from another perspective. Indeed, we have the impression that, in the generalization of topological and algebraic K-theory that has been started by Quillen, something important has been left aside. K-theory was initiated as a (contravariant) functor from the various categories of spaces, rings, schemes, …, not from the category of Waldhausen small categories. Of course, one obtains information about a ring by studying its Quillen-exact category of (finitely generated projective) modules, but still, the final goal is the study of the ring, and, more globally, of the category of rings. Thus, in a general theory, one should describe a way to associate not only a spectrum to a structured category, but also a structured category to an object. Moreover, this process should take the morphisms of these objects into account. This gives rise to two fundamental questions. What kind of mathematical objects should K-theory be applied to? Given such an object, what category "over it" should one consider and how does it vary over morphisms? Considering examples, we have made the following observations. Suppose C is the category that is to be investigated by means of K-theory, like the category of topological spaces or of schemes, for instance. The category associated to an object of C is a sub-category of the category of modules over some monoid in a monoidal category with additional structure (topological, symmetric, abelian, model). The situation is highly "fibred": not only morphisms of C induce (structured) functors between these sub-categories of modules, but the monoidal category in which theses modules take place might vary from one object of C to another. In important cases, the sub-categories of modules considered are full sub-categories of "locally trivial" modules with respect to some (possibly weakened notion of) Grothendieck topology on C . That is, there are some specific modules that are considered sufficiently simple to be called trivial and locally trivial modules are those that are, locally over a covering of the Grothendieck topology, isomorphic to these. In this thesis, we explore, with K-theory in view, a categorical framework that encodes these kind of data. We also study these structures for their own sake, and give examples in other fields. We do not mention in this abstract set-theoretical issues, but they are handled with care in the discussion. Moreover, an appendix is devoted to the subject. After recalling classical facts of Grothendieck fibrations (and their associated indexed categories), we provide new insights into the concept of a bifibration. We prove that there is a 2-equivalence between the 2-category of bifibrations over a category ℬ and a 2-category of pseudo double functors from ℬ into the double category of adjunctions in CAT. We next turn our attention to composable pairs of fibrations , as they happen to be fundamental objects of the theory. We give a characterization of these objects in terms of pseudo-functors ℬop → FIBc into the 2-category of fibrations and Cartesian functors. We next turn to a short survey about Grothendieck (pre-)topologies. We start with the basic notion of covering function, that associate to each object of a category a family of coverings of the object. We study separately the saturation of a covering function with respect to sieves and to refinements. The Grothendieck topology generated by a pretopology is shown to be the result of these two steps. We define then, inspired by Street [89], the notion of (locally) trivial objects in a fibred category P : ℰ → ℬ equipped with some notion of covering of objects of the base ℬ. The trivial objects are objects chosen in some fibres. An object E in the fibre over B ∈ ℬ is locally trivial if there exists a covering {fi : Bi → B}i ∈ I such the inverse image of E along fi is isomorphic to a trivial object. Among examples are torsors, principal bundles, vector bundles, schemes, locally constant sheaves, quasi-coherent and locally free sheaves of modules, finitely generated projective modules over commutative rings, topological manifolds, … We give conditions under which locally trivial objects form a subfibration of P and describe the relationship between locally trivial objects with respect to subordinated covering functions. We then go into the algebraic part of the theory. We give a definition of monoidal fibred categories and show a 2-equivalence with monoidal indexed categories. We develop algebra (monoids and modules) in these two settings. Modules and monoids in a monoidal fibred category ℰ → ℬ happen to form a pair of fibrations . We end this thesis by explaining how to apply this categorical framework to K-theory and by proposing some prospects of research. ______________________________ 1 Works of Lurie, Toën and Vezzosi have shown that K-theory really depends on the (∞, 1)-category associated to a Waldhausen category [94]. Moreover, topological K-theory of spaces and Banach algebras takes the fact that the Waldhausen category is topological in account [62, 70].

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view.Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B involves gluing the branches back together. We are able to define combinatorial equivalence classes of merge trees and barcodes that allow us to completely solve this inverse problem. A barcode can be associated with an element in the symmetric group, and the number of trees with the same barcode, the tree realization number, depends only on the permutation type. We compare these combinatorial definitions of barcodes and trees to those of phylogenetic trees, thus describing the subtle differences between these spaces. The result is a clear combinatorial distinction between the phylogenetic tree space and the merge tree space.The representation of a barcode by a permutation not only gives a formula for the tree realization number, but also opens the door to deeper connections between inverse problems in topological data analysis, group theory, and combinatorics.Based on the combinatorial classes of barcodes, we construct a stratification of the barcode space. We define coordinates that partition the space of barcodes into regions indexed by the averages and the standard deviations of birth and death times and by the permutation type of a barcode. By associating to a barcode the coordinates of its region, we define a new invariant of barcodes.These equivalence classes define a stratification of the space of barcodes with n bars where the strata are indexed by the symmetric group on n letters and its parabolic subgroups.We study the realization numbers computed from barcodes with uniform permutation type (i.e., drawn from the uniform distribution on the symmetric group) and establish a fundamental null hypothesis for this invariant. We show that the tree realization number can be used as a statistic to distinguish distributions of trees by comparing neuronal trees to random barcode distributions.

In homological algebra, to understand commutative rings R, one studies R-modules, chain complexes of R-modules and their monoids, the differential graded R-algebras. The category of R-modules has a rich structure, but too rigid to efficiently work with homological invariants and homotopy invariant properties. It appears more appropriate to operate in the derived category D(R), which is the homotopy category of differential graded R-modules. Algebra of symmetric spectra offers a generalization of homological algebra. In this frame, spectra are objects that take the place of abelian groups; in particular, the analogue of the initial ring Z is the sphere spectrum S. Tensoring over S endows the category of spectra with a symmetric monoidal smash product, analogous to the tensor product of abelian groups. Thus, spectra are S-modules, and ring spectra, which extend the notion of rings, are the S-algebras. To any discrete ring R, one can associate the Eilenberg-Mac Lane ring spectrum HR, which is commutative if R is.

2010