Inequalities for Gondran-Minoux rank and idempotent semirings

The rank-sum, rank-product, and rank-union inequalities for Gondran-Minoux rank of matrices over idempotent semirings are considered. We prove these inequalities for matrices over quasi-selective semirings without zero divisors, which include matrices over the max-plus semiring. Moreover, it is shown that the inequalities provide the linear algebraic characterization for the class of quasi-selective semirings. Namely, it is proven that the inequalities hold for matrices over an idempotent semiring S without zero divisors if and only if S is quasi-selective. For any idempotent semiring which is not quasi-selective it is shown that the rank-sum, rank-product, and rank-union inequalities do not hold in general. Also, we provide an example of a selective semiring with zero divisors such that the rank-sum, rank-product, and rank-union inequalities do not hold in general.     

Locally Closed Semirings and Iteration Semirings

Locally closed semirings, iteration semirings and Conway semirings play an important role in the algebraic theory of semirings and theoretical computer science. Z. ésik and W. Kuich showed that a locally closed commutative semiring is an iteration semiring (is also a Conway semiring). By study of polynomial semirings and matrix semirings, we obtain new expressions of certain polynomials and show that all matrix semirings over a locally closed semiring are also locally closed, and so a locally closed semiring (which need not be commutative) is an iteration semiring.     

一类后缀码的代数性质

利用自由含幺半群X*上的一个偏序关系,介绍了一类特殊的后缀码.通过定义这类后缀码上的两种二元运算,研究了这类后缀码的代数性质.证明了该子类在这两种运算下形成一个加法导出是半格的半环,并且满足吸收律.从而提供了一个满足吸收律的半格序半群的例子.     

Locally Closed Semirings and Iteration Semirings

Locally closed semirings, iteration semirings and Conway semirings play an important role in the algebraic theory of semirings and theoretical computer science. Z. ésik and W. Kuich showed that a locally closed commutative semiring is an iteration semiring (is also a Conway semiring). By study of polynomial semirings and matrix semirings, we obtain new expressions of certain polynomials and show that all matrix semirings over a locally closed semiring are also locally closed, and so a locally closed semiring (which need not be commutative) is an iteration semiring.     

nvolutorial Płonka sums

The construction of the sum of a direct (semilattice ordered) system of algebras introduced by J. Plonka – later known as the Plonka sum – is one of the most important methods of composition in universal algebra, having a number of applications in different algebraic theories, such as semigroup theory, semiring theory, etc. In this paper we present a more general way for constructing algebras with involution, that is, algebraic systems equipped with a unary involutorial operation which is at the same time an antiautomorphism of the underlying algebra. It is the sum – involutorial Plonka sum, as we call it – of an involution semilattice ordered system of algebras. We investigate its basic properties, as well as the problem of its subdirect decomposition.     

Banzhaf index for multiple voting systems. An application to the European Union

Multi-criteria simple games constitute an extension of the basic framework of voting systems and collective decision-making. The study of power index plays an important role in the theory of multi-criteria simple games. Thus, in this paper, we propose the extended Banzhaf index for these games, as the natural generalization of this index in conventional simple games. This approach allows us to compare various criteria simultaneously. An axiomatic characterization of this power index is established. The Banzhaf index is computed by taking into account the minimal winning coalitions of each class. Since this index depends on the number of ways in which each player can effect a swing, one of the main difficulties for finding this index is that it involves a large number of computations. We propose a combinatorial procedure, based on generating functions, to obtain the Banzhaf index more efficiently for weighted multi-criteria simple games. As an application, the distribution of voting power in the European Union is calculated.     

Hyperoctahedral Chen calculus for effective Hamiltonians

We tackle the problem of unraveling the algebraic structure of computations of effective Hamiltonians. This is an important subject in view of applications to chemistry, solid state physics or quantum field theory. We show, among other things, that the correct framework for these computations is provided by the hyperoctahedral group algebras. We define several structures on these algebras and give various applications. For example, we show that the adiabatic evolution operator (in the time-dependent interaction representation of an effective Hamiltonian) can be written naturally as a Picard-type series and has a natural exponential expansion.     

Ricci structure and volume growth for left invariant Riemannian metrics on nilpotent and some solvable Lie groups

We discuss left invariant Riemannian metrics on Lie groups, and the Ricci structures they induce. A computational approach is used to manipulate the curvature tensors, and construct perturbations which preserve the Ricci structure but not the (algebraic) Lie structure. We show that this method can lead to significant changes in the growth of volume. We also show that this approach may be used to reduce the complexity of some curvature computations in Lie groups.     

Noncommuting graphs of matrices over semirings

We study diameters and girths of noncommuting graphs of semirings. For a noncommutative semiring that is either multiplicatively or additively cancellative, we find the diameter and the girth of its noncommuting graph and prove that it is Hamiltonian. Moreover, we find diameters and girths of noncommuting graphs of all nilpotent matrices over a semiring, all invertible matrices over a semiring, all noninvertible matrices over a semiring, and the full matrix semiring. In nearly all cases we prove that diameters are less than or equal to 2 and girths are less than or equal to 3, except in the case of 2×2 nilpotent matrices.     

Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures

In this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists.     

Quantization in Geometric Pluripotential Theory

The space of Kähler metrics, on the one hand, can be approximated by subspaces of algebraic metrics, while, on the other hand, it can also be enlarged to finite-energy spaces arising in pluripotential theory. The latter spaces are realized as metric completions of Finsler structures on the space of Kähler metrics. The former spaces are the finite-dimensional spaces of Fubini-Study metrics of Kähler quantization. The goal of this article is to draw a connection between the two. We show that the Finsler structures on the space of Kähler potentials can be quantized. More precisely, given a Kähler manifold polarized by an ample line bundle we endow the space of Hermitian metrics on powers of that line bundle with Finsler structures and show that the resulting path length metric spaces recover the corresponding metric completions of the Finsler structures on the space of Kähler potentials. This has a number of applications, among them a new Lidskii-type inequality on the space of Kähler metrics, a new approach to the rooftop envelopes and Pythagorean formulas of Kähler geometry, and approximation of finite-energy potentials, as well as geodesic segments by the corresponding smooth algebraic objects. © 2019 Wiley Periodicals, Inc.     

Negotiation support systems: A multi-criteria and multi-agent approach

This research concerns the development of an Negotiation Support Systems (NSS) based on a multi-criteria conceptual framework of the negotiation and developed according to a multi-agent architecture from Distributed Artificial Intelligence (DAI). A first prototype of such a system, NegocIAD, has already been developed [8], but the weakness of its assistance to the negotiation process have led us to revise the conceptual framework in order to define a more relevant assistance to the negotiation process. This paper presents this new conceptual framework defined in order to develop a new prototype. First, we point out the originality of our multi-criteria and multi-agent approach, the general architecture and the limitations of NegocIAD. Then we present the new multi-criteria conceptual framework mainly based on the definition and the use of projection plans (group Gaia plans) emerging from principal component analysis (PCA) already proposed in a single decision maker context in extension of the Promethee method. In the next part, we develop the possible levels of use of these plans during the negotiation process and the type of assistance provided to the mediator. This assistance is mainly based on the elaboration and the interpretation of group Gaia plans for which we propose a set of interpretation rules and the outline of a method to make use of these rules for a relevant support to the mediator in the management of the negotiation process. Finally, we conclude on the perspectives of our future researches and developments for the new generation of our prototype in a multi-agent architecture context.     

Geometric groups. I

We define a geometry on a group to be an abelian semigroup of symmetric open sets with certain properties. Examples include well-known structures such as invariant Riemannian metrics on Lie groups, hyperbolic groups, and valuations on fields. In this paper we are mostly concerned with geometries where the semigroup is isomorphic to the positive reals, which for Lie groups come from invariant Finsler metrics. We explore various aspects of these geometric groups, including a theory of covering groups for arcwise connected groups, algebraic expressions for invariant metrics and inner metrics, construction of geometries with curvature bounded below, and finding geometrically significant curves in path homotopy classes.

     

A new centrality measure of nodes in multilayer networks under the framework of tensor computation

One challenging issue in information science, biological systems and many other field is to determine the most central agents in multilayer networked systems characterized by different types of interrelationships. In this paper, using a fourth-order tensor to represent multilayer networks, we propose a new centrality measure, referred to as the Singular Vector of Tensor (SVT) centrality, which is used to quantitatively evaluate the importance of nodes connected by different types of links in multilayer networks. First, we present a novel iterative method to obtain four alternative metrics that can quantify the hub and authority scores of nodes and layers in multilayer networked systems. Moreover, we use the theory of multilinear algebra to prove that the four metrics converge to four singular vectors of the adjacency tensor of the multilayer network under reasonable conditions. Furthermore, a novel SVT centrality measure is obtained by integrating these four metrics. The experimental results demonstrate that the proposed method is a new centrality measure that significantly outperforms six other published centrality methods on two real-world multilayer networks related to complex diseases, i.e., gastric and colon cancers.     

A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization

We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.     

Tropical Arithmetic and Matrix Algebra

This article introduces a new structure of commutative semiring, generalizing the tropical semiring, and having an arithmetic that modifies the standard tropical operations, i.e., summation and maximum. Although our framework is combinatorial, notions of regularity and invertibility arise naturally for matrices over this semiring; we show that a tropical matrix is invertible if and only if it is regular.     

Maximal Abstract Monotonicity and Generalized Fenchel’s Conjugation Formulas

In this paper, we present a generalization of a theory of monotone operators in the framework of abstract convexity. We show that how generalized Fenchel’s conjugation formulas can be used to obtain some results on maximal abstract monotonicity. We give a necessary and sufficient condition for maximality of abstract monotone operators representable by abstract convex functions by using an additivity constraint qualification.     

Categorical Abstract Algebraic Logic: Partially Ordered Algebraic Systems

An extension of parts of the theory of partially ordered varieties and quasivarieties, as presented by Pałasińska and Pigozzi in the framework of abstract algebraic logic, is developed in the more abstract framework of categorical abstract algebraic logic. Algebraic systems, as introduced in previous work by the author, play in this more abstract framework the role that universal algebras play in the more traditional treatment. The aim here is to build the generalized framework and to formulate and prove abstract versions of the ordered homomorphism theorems in this framework. To Don Pigozzi and Kate Pałasińska.     

An eigenvector existence theorem in idempotent analysis

In this paper, we prove an eigenvector existence theorem for linear operators on abstract idempotent spaces in the framework of the algebraic approach. Earlier, an algebraic version of a similar statement was known only for operators in free finite-dimensional semimodules. The corresponding result for compact operators in semimodules of real continuous functions is known in the case of topological semimodules.