Search

Among sub-optimal Multi-Agent Path Finding (MAPF) solvers, rule-based algorithms are particularly appealing since they are complete. Even in crowded scenarios, they allow finding a feasible solution that brings each agent to its target, preventing deadlock situations. However, generally, rule-based algorithms provide much longer solutions than the shortest one. The main contribution of this paper is introducing a new local search procedure for improving a known feasible solution. We start from a feasible sub-optimal solution, and perform a local search in a neighborhood of this solution. If we are able to find a shorter solution, we repeat this procedure until the solution cannot be shortened anymore. At the end, we obtain a solution that is still sub-optimal, but generally of much better quality than the initial one. We propose two different local search policies. In the first, we explore all paths in which the agents positions remain in a neighborhood of the corresponding positions of the reference solution. In the second, we set an upper limit to the number of agents that can change their path with respect to the reference solution. These two different policies can also be alternated. We explore the neighborhoods by dynamic programming. The fact that our search is local is fundamental in terms of time complexity. Indeed, if the dynamic programming approach is applied to the full MAPF problem, the number of explored states grows exponentially with the number of agents. Instead, the introduction of a locality constraint allows exploring the neghborhoods in a time that grows polynomially with respect to the number of agents., Comment: arXiv admin note: text overlap with arXiv:2304.01765

We consider a road network represented by a directed graph. We assume to collect many measurements of traffic flows on all the network arcs, or on a subset of them. We assume that the users are divided into different groups. Each group follows a different path. The flows of all user groups are modeled as a set of independent Poisson processes. Our focus is estimating the paths followed by each user group, and the means of the associated Poisson processes. We present a possible solution based on a Dynamic Programming algorithm. The method relies on the knowledge of high order cumulants. We discuss the theoretical properties of the introduced method. Finally, we present some numerical tests on well-known benchmark networks, using synthetic data.

The behavior of cyclists when choosing the path to follow along a road network is not uniform. Some of them are mostly interested in minimizing the travelled distance, but some others may also take into account other features such as safety of the roads or pollution. Individuating the different groups of users, estimating the numerical consistency of each of these groups, and reporting the weights assigned by each group to different characteristics of the road network, is quite relevant. Indeed, when decision makers need to assign some budget for infrastructural interventions, they need to know the impact of their decisions, and this is strictly related to the way users perceive different features of the road network. In this paper, we propose an optimization approach to detect the weights assigned to different road features by various user groups, leveraging knowledge of the true paths followed by them, accessible, for example, through data collected by bike-sharing services.

The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(knc + n^2), where n is the number of nodes, $k$ is the number of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n^3), which is equal to our result in the worst case, but does not capture the dependency on c and k.

In a previous paper we introduced the concept of semiseparable functor. Here we continue our study of these functors in connection with idempotent (Cauchy) completion. To this aim, we introduce and investigate the notions of (co)reflection and bireflection up to retracts. We show that the (co)comparison functor attached to an adjunction whose associated (co)monad is separable is a coreflection (reflection) up to retracts. This fact allows us to prove that a right (left) adjoint functor is semiseparable if and only if the associated (co)monad is separable and the (co)comparison functor is a bireflection up to retracts, extending a characterization pursued by X.-W. Chen in the separable case. Finally, we provide a semi-analogue of a result obtained by P. Balmer in the framework of pre-triangulated categories.

We propose an infinitesimal counterpart to the notion of braided category. The corresponding infinitesimal braidings are natural transformations which are compatible with an underlying braided monoidal structure in the sense that they constitute a first-order deformation of the braiding. This extends previously considered infinitesimal symmetric or Cartier categories, where involutivity of the braiding and an additional commutativity of the infinitesimal braiding with the symmetry are required. The generalized pre-Cartier framework is then elaborated in detail for the categories of (co)quasitriangular bialgebra (co)modules and we characterize the resulting infinitesimal $\mathcal{R}$-matrices (resp. $\mathcal{R}$-forms) on the bialgebra. It is proven that the latter are Hochschild $2$-cocycles and that they satisfy an infinitesimal quantum Yang-Baxter equation, while they are Hochschild $2$-coboundaries under the Cartier (co)triangular assumption in the presence of an antipode. We provide explicit examples of infinitesimal braidings, particularly on quantum $2\times 2$-matrices, $\mathrm{GL}_q(2)$, Sweedler's Hopf algebra and via Drinfel'd twist deformation. As conceptual tools to produce examples of infinitesimal braidings we prove an infinitesimal version of the FRT construction and we provide a Tannaka-Krein reconstruction theorem for pre-Cartier coquasitriangular bialgebras. We comment on the deformation of infinitesimal braidings and construct a quasitriangular structure on formal power series of Sweedler's Hopf algebra., Comment: 38 pages; conceptualized proof of Prop. 2.7; improved formulations in Def. 2.1, Def. 3.1 and in Thm. 2.6, Thm. 3.2; connection to matched pairs discussed before Lem. 3.16; adjusted relations for $\mathrm{M}_q(2)$ and computations on pages 21-23; minor typo corrections

Among sub-optimal MAPF solvers, rule-based algorithms are particularly appealing since they are complete. Even in crowded scenarios, they allow finding a feasible solution that brings each agent to its target, preventing deadlock situations. However, generally, rule-based algorithms provide solutions that are much longer than the optimal one. The main contribution of this paper is the introduction of an iterative local search procedure in MAPF. We start from a feasible suboptimal solution and we perform a local search in a neighborhood of this solution, to find a shorter one. Iteratively, we repeat this procedure until the solution cannot be shortened any longer. At the end, we obtain a solution, that is still sub-optimal, but, in general, of much better quality than the initial one. We use dynamic programming for the local search procedure. Under this respect, the fact that our search is local is fundamental to reduce the time complexity of the algorithm. Indeed, if we apply a standard dynamic programming the number of explored states grows exponentially with the number of agents. As we will see, the introduction of a locality constraint allows solving the (local) dynamic programming problem in a time that grows only polynomially with respect to the number of agents.

We discuss C-MP and C-MAPF, generalizations of the classical Motion Planning (MP) and Multi-Agent Path Finding (MAPF) problems on a directed graph G. Namely, we enforce an upper bound on the number of agents that occupy each member of a family of vertex subsets. For instance, this constraint allows maintaining a safety distance between agents. We prove that finding a feasible solution of C-MP and C-MAPF is NP-hard, and we propose a reduction method to convert them to standard MP and MAPF. This reduction method consists in finding a subset of nodes W and a reduced graph G/W, such that a solution of MAPF on G/W provides a solution of C-MAPF on G. Moreover, we study the problem of finding W of maximum cardinality, which is strongly NP-hard.

On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, given a MAPF problem with at least two holes, we present an algorithm that checks the problem feasibility in linear time with respect to the number of nodes, and provides a feasible solution in polynomial time.

In this paper we introduce and investigate the notion of semiseparable functor. One of its first features is that it allows a novel description of separable and naturally full functors in terms of faithful and full functors, respectively. To any semiseparable functor we attach an invariant, given by an idempotent natural transformation, which controls when the functor is separable and yields a characterization of separable functors in terms of (dual) Maschke and conservative functors. We prove that any semiseparable functor admits a canonical factorization as a naturally full functor followed by a separable functor. Here the main tool is the construction of the coidentifier category attached to the associated idempotent natural transformation. Then we move our attention to the semiseparability of functors that have an adjoint. First we obtain a Rafael-type Theorem. Next we characterize the semiseparability of adjoint functors in terms of the (co)separability of the associated (co)monads and the natural fullness of the corresponding (co)comparison functor. We also focus on functors that are part of an adjoint triple. In particular, we describe bireflections as semiseparable (co)reflections, or equivalently, as either Frobenius or naturally full (co)reflections. As an application of our results, we study the semiseparability of functors traditionally attached to ring homomorphisms, coalgebra maps, corings and bimodules, introducing the notions of semicosplit coring and semiseparability relative to a bimodule which extend those of cosplit coring and Sugano's separability relative to a bimodule, respectively.

Liftable pairs of adjoint functors between braided monoidal categories in the sense of \cite{GV-OnTheDuality} provide auto-adjunctions between the associated categories of bialgebras. Motivated by finding interesting examples of such pairs, we study general pre-rigid monoidal categories. Roughly speaking, these are monoidal categories in which for every object $X$, an object $X^{\ast}$ and a nicely behaving evaluation map from $X^{\ast}\otimes X$ to the unit object exist. A prototypical example is the category of vector spaces over a field, where $X^{\ast}$ is not a categorical dual if $X$ is not finite-dimensional. We explore the connection with related notions such as right closedness, and present meaningful examples. We also study the categorical frameworks for Turaev's Hopf group-(co)algebras in the light of pre-rigidity and closedness, filling some gaps in literature along the way. Finally, we show that braided pre-rigid monoidal categories indeed provide an appropriate setting for liftability in the sense of loc. cit. and we present an application, varying on the theme of vector spaces, showing how -- in favorable cases -- the notion of pre-rigidity allows to construct liftable pairs of adjoint functors when right closedness of the category is not available.

The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: the nodes represent positions of a mobile vehicle and the arcs are associated to pre-assigned geometric paths that connect these positions. BASP consists in finding the minimum-time path between two nodes. Differently from SP, we require that the vehicle satisfy bounds on maximum and minimum acceleration and speed, that depend on the vehicle position on the currently traveled arc. We prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data., Comment: 39 pages

It is known that the so-called monadic decomposition, applied to the adjunction connecting the category of bialgebras to the category of vector spaces via the tensor and the primitive functors, returns the usual adjunction between bialgebras and (restricted) Lie algebras. Moreover, in this framework, the notions of augmented monad and combinatorial rank play a central role. In order to set these results into a wider context, we are led to substitute the monadic decomposition by what we call the adjoint decomposition. This construction has the advantage of reducing the computational complexity when compared to the first one. We connect the two decompositions by means of an embedding and we investigate its properties by using a relative version of Grothendieck fibration. As an application, in this wider setting, by using the notion of augmented monad, we introduce a notion of combinatorial rank that, among other things, is expected to give some hints on the length of the monadic decomposition.

In this paper we set up the foundations around the notions of formal differentiation and formal integration in the context of commutative Hopf algebroids and Lie-Rinehart algebras. Specifically, we construct a contravariant functor from the category of commutative Hopf algebroids with a fixed base algebra to that of Lie-Rinehart algebras over the same algebra, the differentiation functor, which can be seen as an algebraic counterpart to the differentiation process from Lie groupoids to Lie algebroids. The other way around, we provide two interrelated contravariant functors form the category of Lie-Rinehart algebras to that of commutative Hopf algebroids, the integration functors. One of them yields a contravariant adjunction together with the differentiation functor. Under mild conditions, essentially on the base algebra, the other integration functor only induces an adjunction at the level of Galois Hopf algebroids. By employing the differentiation functor, we also analyse the geometric separability of a given morphism of Hopf algebroids. Several examples and applications are presented along the exposition., Comment: Minor changes. Comments are very welcome!

Prompted by an example related to the tensor algebra, we introduce and investigate a stronger version of the notion of separable functor that we call heavily separable. We test this notion on several functors traditionally connected to the study of separability.

In this paper we investigate a family of algebras endowed with a suitable non-degenerate bilinear form that can be used to define two different notions of dual for a given right ideal. We apply our results to the classification of the right ideals and their duals in the cyclic group algebra, in the Taft algebra and in another example of Hopf algebra arising as bosonization.

We prove in a very general framework several versions of the classical Poincar\'e-Birkhoff-Witt Theorem, which extend results from [BeGi, BrGa, CS, HvOZ, WW]. Applications and examples are discussed in the last part of the paper.

Let $\mathcal{A}$ and $\mathcal{B}$ be monoidal categories and let $R:\mathcal{A} \rightarrow \mathcal{B}$ be a lax monoidal functor. If $R$ has a left adjoint $L$, it is well-known that the two adjoints induce functors $\overline{R}={\sf Alg}(R):{\sf Alg}(\mathcal{A})\rightarrow {\sf Alg }(\mathcal{B})$ and $\underline{L}={\sf Coalg(L)}:{\sf Coalg}(\mathcal{B})\rightarrow {\sf Coalg}(\mathcal{A})$ respectively. The pair $(L,R)$ is called "liftable" if the functor $\overline{R}$ has a left adjoint and if the functor $\underline{L}$ has a right adjoint. A pleasing fact is that, when $\mathcal{A}$, $\mathcal{B}$ and $R$ are moreover braided, a liftable pair of functors as above gives rise to an adjunction at the level of bialgebras. In this note, sufficient conditions on the category $\mathcal{A}$ for $\overline{R}$ to possess a left adjoint, are given. Natively these conditions involve the existence of suitable colimits that we interpret as objects which are simultaneously initial in four distinguished categories (among which the category of epi-induced objects), allowing for an explicit construction of $\overline{L}$, under the appropriate hypotheses. This is achieved by introducing a relative version of the notion of weakly coreflective subcategory, which turns out to be a useful tool to compare the initial objects in the involved categories. We apply our results to obtain an analogue of Sweedler's finite dual for the category of vector spaces graded by an abelian group $G$ endowed with a bicharacter. When the bicharacter on $G$ is skew-symmetric, a lifted adjunction as mentioned above is explicitly described, inducing an auto-adjunction on the category of bialgebras "colored" by $G$., Comment: The previous verision has been revised by means of weak coreflections and initial objects. The study of pre-rigid categories has been extrapolated and expanded to become an independent research line (arXiv:2201.03952)

We give a description of the category of restricted Lie algebras over a field $\Bbbk $ of prime characteristic by means of monadic decomposition of the functor that computes the $\Bbbk $-vector space of primitive elements of a $\Bbbk $-bialgebra.

We prove that a finite-dimensional Hopf algebra with the dual Chevalley Property over a field of characteristic zero is quasi-isomorphic to a Radford-Majid bosonization whenever the third Hochschild cohomology group in the category of Yetter-Drinfeld modules of its diagram with coefficients in the base field vanishes. Moreover we show that this vanishing occurs in meaningful examples where the diagram is a Nichols algebra.

The aim of this paper is to establish a contravariant adjunction between the category of quasi-bialgebras and a suitable full subcategory of dual quasi-bialgebras, adapting the notion of finite dual to this framework. Various functorial constructions involving non-associative algebras and non-coassociative coalgebras are then carried out. Several examples illustrating our methods are expounded as well.

In this paper Hom-Lie algebras, Lie color algebras, Lie superalgebras and other type of generalized Lie algebras are recovered by means of an iterated construction, known as monadic decomposition of functors, which is based on Eilenberg-Moore categories. To this aim we introduce the notion of Milnor-Moore category as a monoidal category for which a Milnor-Moore type Theorem holds. We also show how to lift the property of being a Milnor-Moore category whenever a suitable monoidal functor is given and we apply this technique to provide examples.

In this paper, the theory to construct quantum lines for general dual quasi-bialgebras is developed followed by some specific examples where the dual quasi-bialgebras are pointed with cyclic group of points.

In this paper we introduce and study Miyashita action in the context of monoidal categories aiming by this to provide a common framework of previous studies in the literature. We make a special emphasis of this action on Azumaya monoids. To this end, we develop the theory of invertible bimodules over different monoids (a sort of Morita contexts) in general monoidal categories as well as their corresponding Miyashita action. Roughly speaking, a Miyashita action is a homomorphism of groups from the group of all isomorphic classes of invertible subobjects of a given monoid to its group of automorphisms. In the symmetric case, we show that for certain Azumaya monoids, which are abundant in practice, the corresponding Miyashita action is always an isomorphism of groups. This generalizes Miyashita's classical result and sheds light on other applications of geometric nature which can not be treated using the classical theory. In order to illustrate our methods, we give a concrete application to the category of comodules over commutative (flat) Hopf algebroids. This obviously includes the special cases of split Hopf algebroids (action groupoids), which for instance cover the situation of the action of an affine algebraic group on an affine algebraic variety.

We give a necessary and sufficient smoothness condition for the scheme parameterizing the n-dimensional representations of a finitely generated associative algebra over an algebraically closed field of characteristic zero. In particular, our result implies that the points M of the above scheme, satisfying $Ext_A ^2(M,M)=0$, are regular. This generalizes well-known results on finite-dimensional algebras to finitely generated algebras., Comment: 15 pages. Accepted for publication in Annales De L'Institut Fourier

In this paper we investigate the categories of braided objects, algebras and bialgebras in a given monoidal category, some pairs of adjoint functors between them and their relations. In particular we construct a braided primitive functor and its left adjoint, the braided tensor bialgebra functor, from the category of braided objects to the one of braided bialgebras. The latter is obtained by a specific elaborated construction introducing a braided tensor algebra functor as a left adjoint of the forgetful functor from the category of braided algebras to the one of braided objects. The behaviour of these functors in the case when the base category is braided is also considered.

We describe all the quasi-bialgebra structures of a group algebra over a torsion-free abelian group. They all come out to be triangular in a unique way. Moreover, up to an isomorphism, these quasi-bialgebra structures produce only one (braided) monoidal structure on the category of their representations. Applying these results to the algebra of Laurent polynomials, we recover two braided monoidal categories introduced in \cite{CG} by S. Caenepeel and I. Goyvaerts in connection with Hom-structures (Lie algebras, algebras, coalgebras, Hopf algebras).

We show that the functor from bialgebras to vector spaces sending a bialgebra to its subspace of primitives has monadic length at most 2., Comment: The new version of the file simplifies the exposition of the original one while the former is more detailed

In this paper, we associate a dual quasi-bialgebra, called bosonization, to every dual quasi-bialgebra $H$ and every bialgebra $R$ in the category of Yetter-Drinfeld modules over $H$. Then, using the fundamental theorem, we characterize as bosonizations the dual quasi-bialgebras with a projection onto a dual quasi-bialgebra with a preantipode. As an application we investigate the structure of the graded coalgebra $grA$ associated to a dual quasi-bialgebra $A$ with the dual Chevalley property (e.g. $A$ is pointed)., Comment: arXiv admin note: substantial text overlap with arXiv:1012.1956

Let $A$ be a Hopf algebra over a field $K$ of characteristic zero such that its coradical $H$ is a finite dimensional sub-Hopf algebra. Our main theorem shows that there is a gauge transformation $\zeta $ on $A$ such that $A^{\zeta}\cong Q#H$ where $A^\zeta$ is the dual quasi-bialgebra obtained from $A$ by twisting its multiplication by $\zeta$, $Q$ is a connected dual quasi-bialgebra in $^H_H\mathcal{YD}$ and $Q #H $ is a dual quasi-bialgebra called the bosonization of $Q$ by $H$.

It is known that a dual quasi-bialgebra with antipode $H$, i.e. a dual quasi-Hopf algebra, fulfils a fundamental theorem for right dual quasi-Hopf $H$-bicomodules. The converse in general is not true. We prove that, for a dual quasi-bialgebra $H$, the structure theorem amounts to the existence of a suitable map $S:H\rightarrow H$ that we call a preantipode of $H$.

Let $A$ be a Hopf algebra over a field $K$ of characteristic 0 and suppose there is a coalgebra projection $\pi$ from $A$ to a sub-Hopf algebra $H$ that splits the inclusion. If the projection is $H$-bilinear, then $A$ is isomorphic to a biproduct $R #_{\xi}H$ where $(R,\xi)$ is called a pre-bialgebra with cocycle in the category $_{H}^{H}\mathcal{YD}$. The cocycle $\xi$ maps $R \otimes R$ to $H$. Examples of this situation include the liftings of pointed Hopf algebras with abelian group of points $\Gamma$ as classified by Andruskiewitsch and Schneider [AS1]. One asks when such an $A$ can be twisted by a cocycle $\gamma:A\otimes A\rightarrow K$ to obtain a Radford biproduct. By results of Masuoka [Ma1, Ma2], and Gr\"{u}nenfelder and Mastnak [GM], this can always be done for the pointed liftings mentioned above. In a previous paper [ABM1], we showed that a natural candidate for a twisting cocycle is {$\lambda \circ \xi$} where $\lambda\in H^{\ast}$ is a total integral for $H$ and $\xi$ is as above. We also computed the twisting cocycle explicitly for liftings of a quantum linear plane and found some examples where the twisting cocycle we computed was different from {$\lambda \circ \xi$}. In this note we show that in many cases this cocycle is exactly $\lambda\circ\xi$ and give some further examples where this is not the case. As well we extend the cocycle computation to quantum linear spaces; there is no restriction on the dimension.

We continue our investigation of the general notion of universal enveloping algebra introduced in [A. Ardizzoni, \emph{A Milnor-Moore Type Theorem for Primitively Generated Braided Bialgebras}, J. Algebra \textbf{327} (2011), no. 1, 337--365]. Namely we study when such an algebra is of PBW type, meaning that a suitable PBW type theorem holds. We discuss the problem of finding a basis for a universal enveloping algebra of PBW type: As an application we recover the PBW basis both of an ordinary universal enveloping algebra and of a restricted enveloping algebra. We prove that a universal enveloping algebra is of PBW type if and only if it is cosymmetric. We characterize braided bialgebra liftings of Nichols algebras as universal enveloping algebras of PBW type.

Let $\lL(A)$ denote the coendomorphism left $R$-bialgebroid associated to a left finitely generated and projective extension of rings $R \to A$ with identities. We show that the category of left comodules over an epimorphic image of $\lL(A)$ is equivalent to the category of chain complexes of left $R$-modules. This equivalence is monoidal whenever $R$ is commutative and $A$ is an $R$-algebra. This is a generalization, using entirely new tools, of results by B. Pareigis and D. Tambara for chain complexes of vector spaces over fields. Our approach relies heavily on the non commutative theory of Tannaka reconstruction, and the generalized faithfully flat descent for small additive categories, or rings with enough orthogonal idempotents., Comment: The title has been changed, the first part is removed and the construction of the coendomorphim bialgebroid is now freely used in the statement of the main Theorems

A braided bialgebra is called primitively generated if it is generated as an algebra by its space of primitive elements. We prove that any primitively generated braided bialgebra is isomorphic to the universal enveloping algebra of its infinitesimal braided Lie algebra, notions hereby introduced. This result can be regarded as a Milnor-Moore type theorem for primitively generated braided bialgebras and leads to the introduction of a concept of braided Lie algebra for an arbitrary braided vector space.

In this paper, the notion of universal enveloping algebra introduced in [A. Ardizzoni, \emph{A First Sight Towards Primitively Generated Connected Braided Bialgebras}, submitted. (arXiv:0805.3391v3)] is specialized to the case of braided vector spaces whose Nichols algebra is quadratic as an algebra. In this setting a classification of universal enveloping algebras for braided vector spaces of dimension not greater than 2 is handled. As an application, we investigate the structure of primitively generated connected braided bialgebras whose braided vector space of primitive elements forms a Nichols algebra which is quadratic algebra.

Let $H$ be a Hopf algebra over a field $K$ of characteristic $0$ and let $A$ be a bialgebra or Hopf algebra such that $H$ is isomorphic to a sub-Hopf algebra of $A$ and there is an $H$-bilinear coalgebra projection $\pi$ from $A$ to $H$ which splits the inclusion. Then $A \cong R \#_\xi H$ where $R$ is the pre-bialgebra of coinvariants. In this paper we study the deformations of $A$ by an $H$-bilinear cocycle. If $\gamma$ is a cocycle for $A$, then $\gamma$ can be restricted to a cocycle $\gamma_R$ for $R$, and $A^\gamma \cong R^{\gamma_R} \#_{\xi_\gamma} H$. As examples, we consider liftings of $\mathcal{B}(V) \# K[\Gamma]$ where $\Gamma$ is a finite abelian group, $V$ is a quantum plane and $\mathcal{B}(V)$ is its Nichols algebra, and explicitly construct the cocycle which twists the Radford biproduct into the lifting., Comment: J. Algebra, to appear

The main aim of this paper is to investigate the structure of primitively generated connected braided bialgebras $A$ with respect to the braided vector space $P$ consisting of their primitive elements. When the Nichols algebra of $P$ is obtained dividing out the tensor algebra $T(P) $ by the two-sided ideal generated by its primitive elements of degree at least two, we show that $A$ can be recovered as a sort of universal enveloping algebra of $P$. One of the main applications of our construction is the description, in terms of universal enveloping algebras, of connected braided bialgebras whose associated graded coalgebra is a quadratic algebra.

In this paper we continue the investigation started in [A.M.St.-Small], dealing with bialgebras $A$ with an $H$-bilinear coalgebra projection over an arbitrary subbialgebra $H$ with antipode. These bialgebras can be described as deformed bosonizations $R#_{\xi} H$ of a pre-bialgebra $R$ by $H$ with a cocycle $\xi$. Here we describe the behavior of $\xi$ in the case when $R$ is f.d. and thin i.e. it is connected with one dimensional space of primitive elements. This is used to analyze the arithmetic properties of $A$. Meaningful results are obtained when $H$ is cosemisimple. By means of Ore extension construction, we provide some examples of atypical situations (e.g. the multiplication of $R$ is not $H$-colinear or $\xi$ is non-trivial).

We investigate the notion of associated graded coalgebra (algebra) of a bialgebra with respect to a subbialgebra (quotient bialgebra) and characterize those which are bialgebras of type one in the framework of abelian braided monoidal categories.

Braided bialgebras of type one in abelian braided monoidal categories are characterized as braided graded bialgebras which are strongly $\mathbb{N}$-graded both as an algebra and as a coalgebra.

The notion of a formally smooth bimodule is introduced and its basic properties are analyzed. In particular it is proven that a $B$-$A$ bimodule $M$ which is a generator left $B$-module is formally smooth if and only if the $M$-Hochschild dimension of $B$ is at most one. It is also shown that modules $M$ which are generators in the category $\sigma[M]$ of $M$-subgenerated modules provide natural examples of formally smooth bimodules., Comment: 17 pages

Comodule algebras of a Hopf algebroid H with a bijective antipode, i.e. algebra extensions B\subseteq A by H, are studied. Assuming that a lifted canonical map is a split epimorphism of modules of the non-commutative base algebra of H, relative injectivity of the H-comodule algebra A is related to the Galois property of the extension B\subseteq A and also to the equivalence of the category of relative Hopf modules to the category of B-modules. This extends a classical theorem by H.-J. Schneider on Galois extensions by a Hopf algebra. Our main tool is an observation that relative injectivity of a comodule algebra is equivalent to relative separability of a forgetful functor, a notion introduced and analysed hereby. In the first version of this submission, we heavily used the statement that two constituent bialgebroids in a Hopf algebroid possess isomorphic comodule categories. This statement was based on \cite[Brz3,Theorem 2.6], whose proof turned out to contain an unjustified step. In the revised version we return to an earlier definition of a comodule of a Hopf algebroid, that distinguishes between comodules of the two constituent bialgebroids, and modify the statements and proofs in the paper accordingly., Comment: LaTeX file 34 pages. v2:Substantial revision, distinguishing between comodules of both constituent bialgebroids in a Hopf algebroid

We show that, under some mild conditions, a bialgebra in an abelian and coabelian braided monoidal category has a weak projection onto a formally smooth (as a coalgebra) sub-bialgebra with antipode; see Theorem 1.12. In the second part of the paper we prove that bialgebras with weak projections are cross product bialgebras; see Theorem 2.12. In the particular case when the bialgebra $A$ is cocommutative and a certain cocycle associated to the weak projection is trivial we prove that $A$ is a double cross product, or biproduct in Madjid's terminology. The last result is based on a universal property of double cross products which, by Theorem 2.15, works in braided monoidal categories. We also investigate the situation when the right action of the associated matched pair is trivial.

The paper is devoted to prove a version of Milnor-Moore Theorem for connected braided bialgebras that are infinitesimally cocommutative. Namely in characteristic different from 2, we prove that, for a given connected braided bialgebra $A$ having a $\lambda $-cocommutative infinitesimal braiding for some regular element $\lambda \neq 0$ in the base field, then the infinitesimal braiding of $A$ is of Hecke-type of mark $\lambda$ and $A$ is isomorphic as a braided bialgebra to the symmetric algebra of the braided subspace of its primitive elements.

The construction of the cotensor coalgebra for an "abelian monoidal" category $\M$ which is also cocomplete, complete and AB5, was performed in [A. Ardizzoni, C. Menini and D. \c{S}tefan, \emph{Cotensor Coalgebras in Monoidal Categories}, Comm. Algebra, to appear]. It was also proved that this coalgebra satisfies a meaningful universal property which resembles the classical one. Here the lack of the coradical filtration for a coalgebra $E$ in $\M$ is filled by considering a direct limit $\widetilde{D}$ of a filtration consisting of wedge products of a subcoalgebra $D$ of $E$. The main aim of this paper is to characterize hereditary coalgebras $\widetilde{D}$, where $D$ is a coseparable coalgebra in $\M$, by means of a cotensor coalgebra: more precisely, we prove that, under suitable assumptions, $\widetilde{D}$ is hereditary if and only if it is formally smooth if and only if it is the cotensor coalgebra $T^c_{D}(D\w D/D)$ if and only if it is a cotensor coalgebra $T^c_{D}(N)$, where $N$ is a certain $D$-bicomodule in $\M$. Because of our choice, even when we apply our results in the category of vector spaces, new results are obtained.

We prove Heyneman-Radford Theorem in the framework of Monoidal Categories.

We introduce the concept of cotensor coalgebra for a given bicomodule over a coalgebra in an abelian monoidal category. Under some further conditions we show that such a cotensor coalgebra exists and satisfies a meaningful universal property. We prove that this coalgebra is formally smooth whenever the comodule is relative injective and the coalgebra itself is formally smooth.

The natural problem we approach in the present paper is to show how the notion of formally smooth (co)algebra inside monoidal categories can substitute that of (co)separable (co)algebra in the study of splitting bialgebra homomorphisms. This is performed investigating the relation between formal smoothness and separability of certain functors and led to other results related to Hopf algebra theory. Between them we prove that the existence of $ad$-(co)invariant integrals for a Hopf algebra $H$ is equivalent to the separability of some forgetful functors. In the finite dimensional case, this is also equivalent to the separability of the Drinfeld Double $D(H)$ over $H$. Hopf algebras which are formally smooth as (co)algebras are characterized. We prove that given a bialgebra surjection $\pi :E\to H$ with nilpotent kernel such that $H$ is a Hopf algebra which is formally smooth as a $K$-algebra, then $\pi $ has a section which is a right $H$-colinear algebra homomorphism. Moreover, if $H$ is also endowed with an $ad$-invariant integral, then this section can be chosen to be $H$-bicolinear. We also deal with the dual case.

We introduce and discuss the notion of naturally full functor. The definition is similar to the definition of separable functor: a naturally full functor is a functorial version of a full functor, while a separable functor is a functorial version of a faithful functor. We study general properties of naturally full functors. We also discuss when functors between module categories and between categories of comodules over a coring are naturally full., Comment: 27 pages