Search

Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this article, we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-naïve evaluation algorithm on any datalog program. [ABSTRACT FROM AUTHOR]

Let $(S,\oplus,\otimes)$ be a matrix semiring of max-plus algebra with the addition operation $\oplus$ and the multiplication operation $\otimes$, where the set \( S \) consists of matrices constructed from real numbers together with the element negative infinity. A derivation on the semiring \(S\) is an additive mapping \(\delta\) from \(S\) to itself that satisfies the axiom \(\delta(x \otimes y) = (\delta(x) \otimes y) \oplus (x \otimes \delta(y))\), for every \(x, y \in S\). From $S$ we construct all of semiring derivations of $S$ are denoted by $D$. On the set $D$, we defined two binary operations, i.e., addition "$\dotplus$" and composition "$\circ$". We want to investigate the structure of $D$ over "$\dotplus$" and "$\circ$" operations. We show that \( D \) is not a semiring, but there exists a sub-semiring \( H \) \(\subseteq\) \( D \). Here, triple $(H,\oplus,\circ)$ is a semiring which is constructed from max-plus algebra.

Various researchers extended and generalized the two main theorems of Posner [3] in multiple directions. In this paper we generalize these two main results to semirings. The main tool we use to accomplish this generalization is by defining derivation ( d Δ ) in the ring of differences ( R Δ ) of a semiring (R) corresponding to the derivation d of R. [ABSTRACT FROM AUTHOR]

We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained. Consider labelings of a finite poset \(P\) by \(\left\vert P\right\vert + 2\) elements of a ring \(\mathbb{K}\): one label associated with each poset element and two constant labels for the added top and bottom elements in \(\widehat{P}\). Birational rowmotion is a partial map on such labelings. It was originally defined by Einstein and Propp for \(\mathbb{K}=\mathbb{R}\) as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope \(\mathcal{O}(P) := \{\text{order-preserving } f: P \to[0,1]\}\). The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of \(P\), which correspond to the vertices of \(\mathcal{O}(P)\). Dynamical properties of these combinatorial maps sometimes (but not always) extend to the birational level, while results proven at the birational level always imply their combinatorial counterparts. Allowing \(\mathbb{K}\) to be noncommutative, we generalize the birational level even further, and some properties are in fact lost at this step.In 2014, the authors gave the first proof of periodicity for birational rowmotion on rectangular posets (when \(P\) is a product of two chains) for \(\mathbb{K}\) a field, and conjectured that it survives (in an appropriately twisted form) in the noncommutative case. In this paper, we prove this noncommutative periodicity and a concomitant antipodal reciprocity formula. We end with some conjectures about periodicity for other posets, and the question of whether our results can be extended to (noncommutative) semirings.It has been observed by Glick and Grinberg that, in the commutative case, periodicity of birational rowmotion can be used to derive Zamolodchikov periodicity in the type \(AA\) case, and vice-versa. However, for noncommutative \(\mathbb{K}\), Zamolodchikov periodicity fails even in small examples (no matter what order the factors are multiplied), while noncommutative birational rowmotion continues to exhibit periodicity. Thus, our result can be viewed as a lateral generalization of Zamolodchikov periodicity to the noncommutative setting.Mathematics Subject Classifications: 06A07, 05E99Keywords: Rowmotion, posets, noncommutative rings, semirings, Zamolodchikov periodicity, root systems, promotion, trees, graded posets, Grassmannian, tropicalization

In this paper, we study the influence of derivations on semirings with involution which resembles with commutativity preserving mappings. The action of derivations on Lie ideals and some differential identities regarding Lie ideals are also investigated. It is proved that for any two derivations d1, d2 of a prime semiring S with involution * such that atleast one of d1, d2 is nonzero and char(S) ≠ 2, hence if the identity [d1(a), d1(a*)] + d2(a ◦ a*) = 0, for all a ∈ L, then [L, S] = (0), where L is a Lie ideal of S. [ABSTRACT FROM AUTHOR]

The growing ecosystem of Internet of Things (IoT) devices in the automotive industry demands innovative solutions for secure communication and data exchange. In this context, we present a novel lightweight symmetric key exchange protocol based on matrix power functions, employing the supertropical semiring as a platform. This protocol offers a unique and robust approach to ensure the confidentiality and integrity of data transmission in Vehicle IoT (VIoT) devices. In this paper. we give the theoretical foundations of our protocol. explaining the mathematics behind supertropical semirings. We also describe the algorithm of key exchange process, highlighting its efficiency and security features. Furthermore, we demonstrate the feasibility and performance of our protocol through extensive simulations and experimentation analysis. [ABSTRACT FROM AUTHOR]

Given two operations ∗ and ∘ on a set S, an operation ⋆ on S is said to be a collaboration between ∗ and ∘ if for all a , b ∈ S , a ⋆ b ∈ { a ∗ b , a ∘ b } . Another term for collaborations is two-option operations. We are interested in learning what associative collaborations of two given operations ∗ and ∘ there may be. We do not require that ∗ and ∘ themselves be associative. For this project, as an initial experiment, we consider Plus-Minus operations (i.e. collaborations between addition and subtraction on an abelian group) and Plus-Times operations (i.e. collaborations between the addition and multiplication operations on a semiring.) Our study of Plus-Minus operations focuses on the additive integers but extends to ordered groups. For Plus Times operations, we make some headway in the case of the semiring of natural numbers. We produce an exhaustive list of associative collaborations between the usual addition and multiplication on the natural numbers N . The Plus-Times operations we found are all examples of a type of construction which we define here and that we call augmentations by multidentities. An augmentation by multidentities combines two separate magmas A and B to create another, A(B), having A ⊔ B as underlying set, and in such a way that the elements of B act as identities over those of A. Hence, B consists of a sort of multiple identities (explaining the moniker multidentities.) When A and B are both semigroups then so is A(B). Understanding the connection between certain collaborations and augmentation by multidenties removes, in several cases, the need for cumbersome computations to verify associativity. A final section discusses connections between group collaborations and skew braces. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study the notion of quasi-ideals in gamma semirings on weak nearness approximation spaces and explain some of the concepts and definitions. Also, it is given an example related to the subject. The features described in this study will contribute greatly to the theoretical development of the nearness semirings theory. [ABSTRACT FROM AUTHOR]

Let R be a commutative semiring with identity and M be a unitary Rsemimodule. Let φ : S(M) → S(M) ∪ {∅} be a function, where S(M) is the set of all subsemimodules of M. We say a proper subsemimodule N of M is φ-primary subsemimodule, if r ∈ R, x ∈ M and rx ∈ N − φ(N) imply that r ∈ √(N :R M) or x ∈ N. The notion of φ-primary subsemimodules is a generalization of the concept of primary, weakly primary and φ-prime subsemimodules. We study properties of φ-primary subsemimodules of a semimodule M and related results to those of ring theory. [ABSTRACT FROM AUTHOR]

The study of symmetry is a fascinating and unifying subject that connects various areas of mathematics in the twenty-first century. Algebraic structures offer a framework for comprehending the symmetries of geometric objects in pure mathematics. This paper introduces new concepts in algebraic structures, concentrating on semimodules over semirings and analysing the neutrosophic structure in this context. We explore the properties of neutrosophic subsemimodules and neutrosophic ideals after defining them. We discuss, utilizing neutrosophic products, the representations of neutrosophic ideals and subsemimodules, as well as the relationship between neutrosophic products and intersections. Finally, we derive equivalent criteria in terms of neutrosophic structures for a semiring to be fully idempotent. [ABSTRACT FROM AUTHOR]

In this article we extend the results on reverse derivation in rings to semirings. First we dispose of reverse derivations in prime semirings analogous to Herstein's result [7]. Then, we prove that reverse derivation is just an ordinary derivation in semiprime semirings if and only if it is a central derivation. We also define generalized reverse derivations and obtain some commutativity results which extend the results in [11]. The primary technique we use in these results is the use of derivations and reverse derivations in ring of differences RΔ corresponding to the semiring R and the fact that R is embedded in RΔ. This fact allows us to travel back and forth between R and RΔ and serve as a key tool in obtaining the desired results. [ABSTRACT FROM AUTHOR]

In this paper, we study the semirings which satisfy the identities x n ≈ x, (2n − 1)x ≈ x, (x + y) n−1 ≈ x n−1 + y n−1 and (xy) n−1 ≈ x n−1 y n−1 . We give the characterizations of the binary relations L · ∧ D +, L · ∧ L +, L · ∧ R + and L + ∧ D ·, and obtain the sufficient and necessary conditions which make these binary relations be congruences. Finally, we show that the classes of semirings which can be determined by the above congruences are indeed varieties of semirings. [ABSTRACT FROM AUTHOR]

Copyright of Baghdad Science Journal is the property of Republic of Iraq Ministry of Higher Education & Scientific Research (MOHESR) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Jordan ideals and Jordan derivations are studied by leading researchers as they play a vital role in the study of prime rings. In this paper we define Jordan ideals and Jordan derivations in semirings analogous to rings. Awtar (Proc Am Math Soc 41(1):67–74, 1973) established the commutativity of Jordan ideals in prime rings. We prove that in a semiring of characteristic different from two, a Jordan ideal (U) is in the centre of the semiring if u d (u) = d (u) u , ∀ u ∈ U . We also generalize the classical result of Herstein (Proc Am Math Soc 8(6):1104–1110, 1957) in prime rings to prime semirings and also the result of Bres̆er (Proc Am Math Soc 104(4):1003–1006, 1988) in semiprime rings to semiprime semirings (Jordan derivation is just an ordinary derivation in both cases). The key tool which acts as bridge to go back and forth in these generalization is the derivation in ring of differences of a semiring induced by a derivation in the semiring. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of deciding whether a given univariate integer polynomial p (x) has a factor q (x) satisfying specific additional constraints. When the only constraint imposed on q (x) is to have a degree smaller than the degree of p (x) and greater than zero, the problem is equivalent to testing the irreducibility of p (x) and then it is solvable in polynomial time. We prove that deciding whether a given monic univariate integer polynomial has factors satisfying additional properties is NP-complete in the strong sense. In particular, given any constant value k ∈ Z , we prove that it is NP-complete in the strong sense to detect the existence of a factor that returns a prescribed value when evaluated at x = k (Theorem 1) or to detect the existence of a pair of factors—whose product is equal to the original polynomial—that return the same value when evaluated at x = k (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction. [ABSTRACT FROM AUTHOR]

Let S be a commutative semiring with unity different than zero. In this paper, we study the concept of 2-absorbing ideals of S which can be considered as a generalization of prime ideals. Among others, it is shown that the radical of a 2-absorbing ideal is also a 2-absorbing ideal and there are at most 2 prime k-ideals of S that are minimal over a 2-absorbing ideals. [ABSTRACT FROM AUTHOR]

In this paper, the notions of commutator and derivation in additively regular -semirings with (A2, Г)-condition are introduced. We also characterize Jordan product for additively regular Г -semiring and establish some results which investigate the relationship between commutators, derivations and inner derivations. In 1957, E.C. Posner has shown that if there exists a non-zero centralizing derivation in a prime ring R, then R is commutative. This result is extended in the frame work of derivations of prime additively regular Г -semirings.

Weighted automata are a generalization of nondeterministic automata that associate a weight drawn from a semiring K with every transition and every state. Their behaviours can be formalized either as weighted language equivalence or weighted bisimulation. In this paper we explore the properties of weighted automata in the framework of coalgebras over (i) the category SMod of semimodules over a semiring K and K-linear maps, and (ii) the category Set of sets and maps. We show that the behavioural equivalences defined by the corresponding final coalgebras in these two cases characterize weighted language equivalence and weighted bisimulation, respectively. These results extend earlier work by Bonchi et al. using the category Vect of vector spaces and linear maps as the underlying model for weighted automata with weights drawn from a field K. The key step in our work is generalizing the notions of linear relation and linear bisimulation of Boreale from vector spaces to semimodules using the concept of the kernel of a K-linear map in the sense of universal algebra. We also provide an abstract procedure for forward partition refinement for computing weighted language equivalence. Since for weighted automata defined over semirings the problem is undecidable in general, it is guaranteed to halt only in special cases. We provide sufficient conditions for the termination of our procedure. Although the results are similar to those of Bonchi et al., many of our proofs are new, especially those about the coalgebra in SMod characterizing weighted language equivalence. [ABSTRACT FROM AUTHOR]

We show that the term equivalence between MV-algebras and MV-semirings lifts to involutive residuated lattices and a class of semirings called involutive semirings. The semiring perspective leads to a necessary and sufficient condition for the interval [ d , 1 ] to be a subalgebra of an involutive residuated lattice, where d is the dualizing element. We also import some results and techniques of semimodule theory in the study of this class of semirings, generalizing results about injective and projective MV-semimodules. Indeed, we note that the involution plays a crucial role and that the results for MV-semirings are still true for involutive semirings whenever the Mundici functor is not involved. In particular, we prove that involution is a necessary and sufficient condition in order for projective and injective semimodules to coincide. [ABSTRACT FROM AUTHOR]

In this paper, we introduce some new semiring structures by considering the prime factors, sum of divisors and the number of relatively prime positive divisors of a pair of non-negative integers and solve a variety of system of linear equations over one of these semirings. We then discuss the properties of these structures and how they compare with classical algebra. The paper is concluded by providing a key-exchange scheme using one of the newly discovered semirings. [ABSTRACT FROM AUTHOR]

The notions of hybrid ideals and k-hybrid ideals in a ternary semiring are introduced in this paper, and a substantial amount of effort has been made to study some of their features. In terms of characteristic function, we show some properties of k-hybrid ideals and give some characterizations of hybrid intersection with respect to these k-hybrid ideals. Finally, results based on a k-hybrid ideal's homomorphic hybrid preimage are provided. With respect to k-hybrid ideals, we give certain characterizations of hybrid intersection. [ABSTRACT FROM AUTHOR]

We study permutability properties of matrix semigroups over commutative bipotent semirings (of which the best-known example is the tropical semiring). We prove that every such semigroup is weakly permutable (a result previous stated in the literature, but with an erroneous proof) and then proceed to study in depth the question of when they are strongly permutable (which turns out to depend heavily on the semiring). Along the way we classify monogenic bipotent semirings and describe all isomorphisms between truncated tropical semirings. [ABSTRACT FROM AUTHOR]

The aim of this paper is to introduce Nobusawa Γ -nearness hemiring theory and also to study some properties of ideals and prime (semiprime) ideals for Nobusawa Γ -nearness hemirings. [ABSTRACT FROM AUTHOR]

In this paper, we discuss some differential identities of MA-semirings with involution. The aim to study these identities is to induce commutativity in MA-semirings.

The bipolar fuzzy (BF) set is an extension of the fuzzy set used to solve the uncertainty of having two poles, positive and negative. The rough set is a useful mathematical technique to handle vagueness and impreciseness. The major objective of this paper is to analyze the notion of approximation of BF ideals of semirings by combining the theories of the rough and BF sets. Then, the idea of rough approximation of BF subsemirings (ideals, bi-ideals and interior ideals) of semirings is developed. In addition, semirings are characterized by upper and lower rough approximations using BF ideals. Further, it is seen that congruence relations (CRs) and complete congruence relations (CCRs) play fundamental roles for rough approximations of bipolar fuzzy ideals. Therefore, their associated properties are investigated by means of CRs and CCRs. [ABSTRACT FROM AUTHOR]

We study the free objects in the variety of semigroups and variety of monoids generated by the monoid of all n × n upper triangular matrices over a commutative semiring. We obtain explicit representations of these, as multiplicative subsemigroups of quiver algebras over polynomial semirings. A case of particular interest is where n = 2 and the semiring is the tropical semifield, where the variety coincides with that generated by the bicyclic monoid (or equivalently, by the free monogenic inverse monoid); here we are obtain faithful representations of the free objects in this variety inside a semidirect product of a commutative monoid acting on a semilattice. We apply these representations to answer several questions, including that of when the given varieties are locally finite. [ABSTRACT FROM AUTHOR]

Injective modules play an important role in characterizing different classes of rings (e.g. Noetherian rings, semisimple rings). Some semirings have no nonzero injective semimodules (e.g. the semiring of non-negative integers). In this paper, we study some of the basic properties of the so-called e-injective semimodules introduced by the first author using a new notion of exact sequences of semimodules. We clarify the relationships between the injective semimodules, the e -injective semimodule, and the i -injective semimodules through several implications, examples and counter examples. Moreover, we show that every semimodule over an arbitrary semiring can be embedded in a c - i -injective semimodule. [ABSTRACT FROM AUTHOR]

Domain operations on semirings have been axiomatised in two different ways: by a map from an additively idempotent semiring into a boolean sub-algebra of the semiring bounded by the additive and multiplicative unit of the semiring, or by an endofunction on a semiring that induces a distributive lattice bounded by the two units as its image. This note presents classes of semirings where these approaches coincide. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study the concept of ideals. Especially, prime (semiprime) ideals of Γ -nearness hemiring are introduced and are given some properties of such ideals. [ABSTRACT FROM AUTHOR]

We show that there is an effectively given zero-sum-free commutative semiring S , contained as the subsemiring of nonnegative elements in an effectively given commutative ordered ring, for which there are no procedures deciding, given a weighted finite automaton over S , whether its support is the language of all words or whether its support is infinite. In particular, by a result of D. Kirsten (2011), since S is zero-sum-free and commutative, the support is recognizable by a classical finite automaton, but such an automaton or even just a pushdown automaton for its support cannot be constructed effectively. • We construct an effectively given zero-sum-free commutative semiring S as a subsemiring of a commutative ordered ring. • It is undecidable, given a weighted finite automaton over S , whether its support is the language of all words. • It is also undecidable whether the support is infinite. • By a result of D. Kirsten (2011), the support is recognizable by a classical finite automaton. • But such an automaton or even just a pushdown automaton for its support cannot be constructed effectively. [ABSTRACT FROM AUTHOR]

We study pairs of mutually orthogonal normal matrices with respect to tropical multiplication. Minimal orthogonal pairs are characterized. The diameter and girth of three graphs arising from the orthogonality equivalence relation are computed.

A subsemiring S of R is called a positive semiring provided that S consists of nonnegative numbers and 1 ∈ S . Here we study factorizations in both the additive monoid (S , +) and the multiplicative monoid (S \ { 0 } , ·) . In particular, we investigate when, for a positive semiring S, both (S , +) and (S \ { 0 } , ·) have the following properties: atomicity, the ACCP, the bounded factorization property (BFP), the finite factorization property (FFP), and the half-factorial property (HFP). It is well known that in the context of cancellative and commutative monoids, the chain of implications HFP ⇒ BFP and FFP ⇒ BFP ⇒ ACCP ⇒ atomicity holds. Here we construct classes of positive semirings wherein both the additive and multiplicative structures satisfy each of these properties, and we also give examples to show that, in general, none of the implications in the previous chain is reversible. [ABSTRACT FROM AUTHOR]

Observing that every k-irreducible ideal of a semiring R is a k-primary ideal, if R is an additively cancellative, yoked and commutative Noetherian semiring, we establish the primary decomposition and uniqueness of the primary decomposition of k-ideals of such semirings. Finally, the primary decomposition and uniqueness of primary decomposition proved for k-ideals is also generalised for fuzzy k-ideals of these semirings. [ABSTRACT FROM AUTHOR]

The Brauer category is a symmetric strict monoidal category that arises as a (horizontal) categorification of the Brauer algebras in the context of Banagl's framework of positive topological field theories (TFTs). We introduce the chromatic Brauer category as an enrichment of the Brauer category in which the morphisms are component-wise labeled. Linear representations of the (chromatic) Brauer category are symmetric strict monoidal functors into the category of real vector spaces and linear maps equipped with the Schauenburg tensor product. We study representation theory of the (chromatic) Brauer category, and classify all its faithful linear representations. As an application, we use indices of fold lines to construct a refinement of Banagl's concrete positive TFT based on fold maps into the plane. [ABSTRACT FROM AUTHOR]

We investigate ideal-semisimple and congruence-semisimple semirings. We give several new characterizations of such semirings using e-projective and e-injective semimodules. We extend several characterizations of semisimple rings to (not necessarily subtractive) commutative semirings. [ABSTRACT FROM AUTHOR]

We estimate the number of composite elements in the n-th grade of a group semiring of finite boolean groups. In view of this result we conjecture that the composites in these semirings of finite groups are thinly dispersed. [ABSTRACT FROM AUTHOR]

Projective modules play an important role in the study of the category of modules over rings and in the characterization of various classes of rings. Several characterizations of projective objects which are equivalent for modules over rings are not necessarily equivalent for semimodules over an arbitrary semiring. We study several of these notions, in particular the e-projectivity of semimodules introduced by the first author using his new notion of exact sequences of semimodules. As pushouts of semimodules play an important role in some of our proofs, we investigate them and give a constructive proof of their existence in a way that proved be very helpful. [ABSTRACT FROM AUTHOR]

It was recently shown that anti-unification over an equational theory consisting of only unit equations (more than one) is nullary. Such pure theories are artificial and are of little effect on practical aspects of anti-unification. In this work, we extend these nullarity results to the theory of semirings, a heavily studied theory with many practical applications. Furthermore, our argument holds over semirings with commutative multiplication and/or idempotent addition. We also cover a few open questions discussed in previous work. [ABSTRACT FROM AUTHOR]

It is shown that the classes γ Σ 0 = { R | Σ 0 R = ϕ } and γ Σ 1 = { R | Σ 1 R = ϕ } of semirings are radical classes, where Σ 0 R is the class of subtractive-simple right R -semimodules and Σ 1 R is the class of right R -semimodules isomorphic to R / ρ I for some maximal-subtractive right ideal I of R. We define the lower Jacobson Bourne radical rad l (R) ⊆ ker (Σ 0 R) and upper Jacobson Bourne radical rad u (R) ⊆ ker (Σ 1 R) of R. For a semiring R , rad l (R) ⊆ rad (R) holds, where rad (R) is the Jacobson Bourne radical of R. The radical rad l (R) = ker (Σ 0 R) and also coincides with rad (R) , if we restrict the class Σ 0 R to additively cancellative semimodules. The upper radical rad u (R) = ker (Σ 1 R) and rad (R) ⊆ rad u (R) , if R is additively cancellative. Further, rad u (R / ρ rad u (R)) = { 0 } , if R is a commutative semiring with 1 R. The subtractive-primitiveness and subtractive-semiprimitiveness of R are closely related to the upper radical rad u (R). Finally, we show that rad u -semisimplicity of semirings are Morita invariant property with some restrictions. [ABSTRACT FROM AUTHOR]

The aim of this paper is to introduce the concept of Dedekind semimodules and study the related concepts, such as the class of D1 semimodules, and Dedekind multiplication semimodules . And thus study the concept of the embedding of a semimodule in another semimodule. [ABSTRACT FROM AUTHOR]

We study properties determined by idempotents in the following families of matrix semigroups over a semiring S : the full matrix semigroup M n (S) , the semigroup U T n (S) consisting of upper triangular matrices, and the semigroup U n (S) consisting of all unitriangular matrices. Il'in has shown that (for n > 2) the semigroup M n (S) is regular if and only if S is a regular ring. We show that U T n (S) is regular if and only if n = 1 and the multiplicative semigroup of S is regular. The notions of being abundant or Fountain (formerly, weakly abundant) are weaker than being regular but are also defined in terms of idempotents, namely, every class of certain equivalence relations must contain an idempotent. Each of M n (S) , U T n (S) and U n (S) admits a natural anti-isomorphism allowing us to characterise abundance and Fountainicity in terms of the left action of idempotent matrices upon column spaces. In the case where the semiring is exact, we show that M n (S) is abundant if and only if it is regular. Our main interest is in the case where S is an idempotent semifield, our motivating example being that of the tropical semiring 𝕋. We prove that certain subsemigroups of M n (S) , including several generalisations of well-studied monoids of binary relations (Hall relations, reflexive relations, unitriangular Boolean matrices), are Fountain. We also consider the subsemigroups U T n (S ∗) and U n (S ∗) consisting of those matrices of U T n (S) and U n (S) having all elements on and above the leading diagonal non-zero. We prove the idempotent generated subsemigroup of U T n (S ∗) is U n (S ∗). Further, U T n (S ∗) and U n (S ∗) are families of Fountain semigroups with interesting and unusual properties. In particular, every ℛ ̃ -class and ℒ ̃ -class contains a unique idempotent, where ℛ ̃ and ℒ ̃ are the relations used to define Fountainicity, but yet the idempotents do not form a semilattice. [ABSTRACT FROM AUTHOR]

This article presents a novel generic technique for solving dataflow equations in interprocedural dataflow analysis. The technique is obtained by generalizing Newton's method for computing a zero of a differentiable function to ?-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of ω-continuous semirings. We show that our generalized method always converges to the solution, and requires at most as many iterations as current methods based on Kleene's fixed-point theorem. We also show that, contrary to Kleene's method, Newton's method always terminates for arbitrary idempotent and commutative semirings. More precisely, in the latter setting the number of iterations required to solve a system of n equations is at most n. [ABSTRACT FROM AUTHOR]