Search

In the last decade, there has been increasing interest in extensions of answer set programming (ASP) that cater for quantitative information such as weights or probabilities. A wide range of quantitative reasoning tasks for ASP and logic programming, among them probabilistic inference and parameter learning in the neuro-symbolic setting, can be expressed as algebraic answer set counting (AASC) tasks, i.e., weighted model counting for ASP with weights calculated over some semiring, which makes efficient solvers for AASC desirable. In this article, we present ▪, a new solver for AASC that pushes the limits of efficient solvability. Notably, ▪ provides improved performance compared to the state of the art in probabilistic inference by exploiting three insights gained from thorough theoretical investigations in our work. Namely, we consider the knowledge compilation step in the AASC pipeline, where the underlying logical theory specified by the answer set program is converted into a tractable circuit representation, on which AASC is feasible in polynomial time. First, we provide a detailed comparison of different approaches to knowledge compilation for programs, revealing that translation to propositional formulas followed by compilation to sd-DNNF seems favorable. Second, we study how the translation to propositional formulas should proceed to result in efficient compilation. This leads to the second and third insight, namely a novel way of breaking the positive cyclic dependencies in a program, called T P -Unfolding, and an improvement to the Clark Completion, the procedure used to transform programs without positive cyclic dependencies into propositional formulas. Both improvements are tailored towards efficient knowledge compilation. Our empirical evaluation reveals that while all three advancements contribute to the success of ▪, T P -Unfolding improves performance significantly by allowing us to handle cyclic instances better. • In depth theoretical comparison of strategies. • Improvements over existing strategies. • Efficient implementation. • In depth empirical evaluation of our and SoTA solvers. [ABSTRACT FROM AUTHOR]

In this article we study the formal side of operations in free harmonic analysis and examine the emerging general picture of all this. We establish an analytic correspondence of semi-rings between Witt vectors and free probability, by building on previous joint work with Friedrich and McKay (Formal groups, Witt vectors and free probability, 2012. arXiv:1204.6522). In particular, an exponential map, which relates the free additive convolution semigroup on R with the free multiplicative convolution semigroup on either the unit circle or the positive real axis of compactly supported, freely infinitely divisible probability measures, is derived with complex analytic methods. Then we define several novel operations on these sets, discuss their relation with classically infinitely divisible measures and determine the internal geometry of the spaces involved. Finally, we formalise the structure induced by the various operations we have introduced, in the language of operads and algebraic theories. [ABSTRACT FROM AUTHOR]

Relationships between F-transforms based on variants of fuzzy partitions and R -semimodules homomorphisms are investigated, where R are appropriate semirings defined on complete residuated lattices or MV-algebras. For general form of a fuzzy partition, these two notions are proved to be identical. [ABSTRACT FROM AUTHOR]

The aim of this paper is to introduce the concept of prime (semiprime) ideals of nearness semiring theory and to introduce some properties of such ideals. [ABSTRACT FROM AUTHOR]

This paper investigates the concept (α, β) derivation on semiring and extend a few results of this map on prime semiring. Also we establish the commutativity of prime semiring and investigate when (α, β) derivation becomes zero. [ABSTRACT FROM AUTHOR]

Abstract Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions. Highlights • A recently proposed model for computing functions copyless CRA is studied. • It is shown that copyless CRA are not closed under reverse. • A restricted variant bounded alternation CRA (BAC) is proposed. • BAC is shown to be closed under reverse and other extensions. [ABSTRACT FROM AUTHOR]

A real symmetric matrix A is called completely positive if there exists a nonnegative real n × k matrix B such that A = B B t . The smallest value of k for all possible choices of nonnegative matrices B is called the CP-rank of A. We extend the ideas of complete positivity and the CP-rank to matrices whose entries are elements of an incline in a similar way. We classify maps on the set of n × n symmetric matrices over certain inclines which strongly preserve CP-rank-1 matrices as well as maps which preserve CP-rank-1 and CP-rank-k. The result suggests that there is a certain standard class of solutions for CP-rank preserver problems on incline matrices. [ABSTRACT FROM AUTHOR]

Explaining why an answer is (or is not) returned by a query is important for many applications including auditing, debugging data and queries, and answering hypothetical questions about data. In this work, we present the first practical approach for answering such questions for queries with negation (first-order queries). Specifically, we introduce a graph-based provenance model that, while syntactic in nature, supports reverse reasoning and is proven to encode a wide range of provenance models from the literature. The implementation of this model in our PUG (Provenance Unification through Graphs) system takes a provenance question and Datalog query as an input and generates a Datalog program that computes an explanation, i.e., the part of the provenance that is relevant to answer the question. Furthermore, we demonstrate how a desirable factorization of provenance can be achieved by rewriting an input query. We experimentally evaluate our approach demonstrating its efficiency. [ABSTRACT FROM AUTHOR]

An element e of a semiring S with commutative addition is called an almost idempotent if e+e2=e2. Here we characterize the subsemiring ⟨E(S)⟩ generated by the set E(S) of all almost idempotents of a k-regular semiring S with a semilattice additive reduct. If S is a k-regular semiring then ⟨E(S)⟩ is also k-regular. A similar result holds for the completely k-regular semirings, too. [ABSTRACT FROM AUTHOR]

We prove that additive transformations on matrices over the binary Boolean semiring that preserve the scrambling index are automatically bijective. As a consequence we characterize such maps for matrices over an arbitrary antinegative semiring with identity and without zero-divisors. [ABSTRACT FROM AUTHOR]

In this paper we characterize bijective linear maps on matrices over semirings that preserve scrambling index. [ABSTRACT FROM AUTHOR]

This article mainly conerns of various semiring properties of Morita contexts. Necessary and sufficient conditions are obtained for a natural Morita context to satisfy a certain semiring property which is strongly π-regular. Some known results given in [4] have been generalized to semirings. [ABSTRACT FROM AUTHOR]

Starting with commutative rings R we form the ideals of R. Equipping Id(R) with ideal operations we can define semiring Sem(R) whose elements are the ideals of R. Now it is possible to define Łukasiewitz ring (Definition 2.7) which will play an essential role in this work. Then we show that quotient rings ℝ/(a) are Łukasiewitz rings where ℝ are real numbers and (a) is a principal ideal generated by a in ℝ. Using the results of L.B. Belluce and A. Di Nola concerning Łukasiewitz rings we create one to one correspondence between triangular and trapezoidal fuzzy numbers A(a1, a2, · · · , an) and the ideals of the direct product of ℝ/(ai ) (Corollary 4.3). Figures will play an important role in this case because every ℝ/(ai) has a geometrical interpretation. Let F be a set of triangular and trapezoidal fuzzy numbers or fuzzy numbers which include both cases and whose membership functions intersect at least one point. Let c1, c2 · · · , ck be the common points. We denote the set of these fuzzy numbers by C. Further let G be a set of the ideals of the direct product of ℝ/(ci). We will prove that h : (F̄,∪,∩) → (Ḡ,˅,∧), h(C) = Id(ℝ/(c1) × · · · × ℝ/(ck)) is a lattice isomorphism (Proposition 4.4). [ABSTRACT FROM AUTHOR]

Generalized roughness for fuzzy ideals in hemirings is studied. Approximations for fuzzy prime ideals are discussed. It is shown that generalized lower approximation as well as generalized upper approximation of -fuzzy prime (semiprime, respectively) ideals of hemirings are -fuzzy prime (semiprime, respectively) ideals. [ABSTRACT FROM AUTHOR]

In this work, we propose a new quantum structure-weak quantum MV algebras (wQMV algebras)-and define coupled bimonoids and strong coupled bimonoids. We find that the coupled bimonoids and strong coupled bimonoids are ring-like structures corresponding to lattice-ordered wQMV algebras and lattice-ordered QMV algebras, respectively. Using an automated reasoning tool, we give the smallest 4-element wQMV algebra but not a QMV algebra. We also show that lattice-ordered wQMV algebras are the real nondistributive generalization of MV algebras. Certainly, most important properties of quantum MV algebras (QMV algebras) are preserved by wQMV algebras. Furthermore, we can conclude that lattice-ordered wQMV algebras are the simplest unsharp quantum logical structures by far, based on which computation theory could be set up. [ABSTRACT FROM AUTHOR]

We introduce weighted variable automata over infinite alphabets and commutative semirings. We prove that the class of their behaviors is closed under sum, and under scalar, Hadamard, Cauchy, and shuffle products, as well as star operation. Furthermore, we consider rational series over infinite alphabets and we state a Kleene-Schüutzenberger theorem. We introduce a weighted monadic second order logic and a weighted linear dynamic logic over infinite alphabets and investigate their relation to weighted variable automata. An application of our theory, to series over the Boolean semiring, concludes to new results for the class of languages accepted by variable automata. [ABSTRACT FROM AUTHOR]

The main aim of this paper is to investigate relationships between the ideals of semirings R and RQ(I), where RQ(I) is the quotient semiring and I is the partitioning ideal of R. It is shown that if R is additively cancellative and yoked, then RQ(I) is additively cancellative and yoked. If R is additively cancellative, then RQ(I) is isomorphic to R/pI (R/pI is the factor semiring factored by Bourne relation induced by partitioning ideal I) and (RQ(I))Δ (the ring of dfferences of (RQ(I))Δ), is isomorphic to RΔ/IΔ. [ABSTRACT FROM AUTHOR]

The main aim of this paper is to investigate relationships between the ideals of semirings R and RQ(I), where RQ(I) is the quotient semiring and I is the partitioning ideal of R. It is shown that if R is additively cancellative and yoked, then RQ(I) is additively cancellative and yoked. If R is additively cancellative, then RQ(I) is isomorphic to R/pI (R/pI is the factor semiring factored by Bourne relation induced by partitioning ideal I) and (RQ(I))Δ (the ring of dfferences of (RQ(I))Δ), is isomorphic to RΔ/IΔ. [ABSTRACT FROM AUTHOR]

Text We show that the basic categorical concept of an S -algebra as derived from the theory of Segal's Γ-sets provides a unifying description of several constructions attempting to model an algebraic geometry over the absolute point. It merges, in particular, the approaches using monoïds, semirings and hyperrings as well as the development by means of monads and generalized rings in Arakelov geometry. The assembly map determines a functorial way to associate an S -algebra to a monad on pointed sets. The notion of an S -algebra is very familiar in algebraic topology where it also provides a suitable groundwork to the definition of topological cyclic homology. The main contribution of this paper is to point out its relevance and unifying role in arithmetic, in relation with the development of an algebraic geometry over symmetric closed monoidal categories. Video For a video summary of this paper, please visit https://youtu.be/BJ4Zsc4Nv7E . [ABSTRACT FROM AUTHOR]

Let R be a commutative semiring. The purpose of this note is to investigate the concept of 2-absorbing (resp., weakly 2-absorbing) primary ideals generalizing of 2- absorbing (resp., weakly 2-absorbing) ideals of semirings. A proper ideal I of R said to be a 2-absorbing (resp., weakly 2-absorbing) primary ideal if whenever a, b, c ϵ R such that abc ϵ I (resp., 0 ≠ abc ϵ I), then either ab ϵ I or bc ϵ √I or ac ϵ √I. Moreover, when I is a Q-ideal and P is a k-ideal of R/I with I ⊆ P, it is shown that if P is a 2-absorbing (resp., weakly 2-absorbing) primary ideal of R, then P/I is a 2-absorbing (resp., weakly 2-absorbing) primary ideal of R/I and it is also proved that if I and P/I are weakly 2- absorbing primary ideals, then P is a weakly 2-absorbing primary ideal of R. [ABSTRACT FROM AUTHOR]

We give a lower bound on the speed at which Newton's method (as defined in [11] ) converges over arbitrary ω -continuous commutative semirings. From this result, we deduce that Newton's method converges within a finite number of iterations over any semiring which is “collapsed at some k ∈ N ” (i.e. k = k + 1 holds) in the sense of Bloom and Ésik [2] . We apply these results to (1) obtain a generalization of Parikh's theorem, (2) compute the provenance of Datalog queries, and (3) analyze weighted pushdown systems. We further show how to compute Newton's method over any ω -continuous semiring by constructing a grammar unfolding w.r.t. “tree dimension”. We review several concepts equivalent to tree dimension and prove a new relation to pathwidth. [ABSTRACT FROM AUTHOR]

If S is a prime semiring with char S ≠ 2 and f : S → S is an additive mapping which is skew-commuting on an ideal I of S, then f(I) = 0. We also prove that zero is the only additive mapping which is skew-commuting on a 2-torsion free semiprime semiring. These statements are the generalization of Brešar's theorems. [ABSTRACT FROM AUTHOR]

Let R be an additively cancellative K--semialgebra, where K is an additively cancellative commutative semiring. If R is graded by G, we form the smash product R # K[G]* using the tensor product defined in [17]. On the other hand if S is a K--semialgebra and G a finite group acting on S, then the skew group ring S * G is G-graded and we have the smash product (S * G) # K[G] * which is isomorphic to Mn (S). The identity component R1 plays the same role that is played by G-fixed subring in group actions. The main aim of this paper is to establish relations between the semiprimeness of R R1, graded semiprimeness of R and semiprimeness of R #K[G]*, when the grading is nondegenerate. [ABSTRACT FROM AUTHOR]

We introduce FPSOLVE, an implementation of generic algorithms for solving fixpoint equations over semirings. We first illustrate the interest of generic solvers by means of a scenario. We then succinctly describe some of the algorithms implemented in the tool, and provide some implementation details. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and investigatebisemialgebrasandHopf semialgebrasover commutative semirings. We generalize to the semialgebraic context several results on bialgebras and Hopf algebras over commutative rings including the main reconstruction theorems and theFundamental Theorem of Hopf Algebras. We also provide a notion ofquantum monoidsas Hopf semialgebras which are neither commutative nor cocommutative; this extends the Hopf algebraic notion of a quantum group. The generalization to the semialgebraic context is neither trivial nor straightforward due to the nonadditive nature of the base category of commutative monoids which is also neither Puppe-exact nor homological and does not necessarily have enough injectives. [ABSTRACT FROM AUTHOR]

The generalization of the results of group theory and ring theory to semirings is a very desirable feature in the domain of mathematics. The analogy between rings graded by a finite group G and rings on which G acts as automorphism has been observed by a number of mathematicians. The results of M. Lorenz and D.S. Passman [3], M. Lorenz, S. Montgomery and L.W. Small [4] proved for the rings with finite groups acting on them were extended by M. Cohen and S. Montgomery [1] for the group graded rings. Motivated by the analogy between the rings graded by a finite group G and rings on which G acts as automorphisms, we have derived certain results for a group graded semiring R, its ring of differences RΔ, and the smash product R # K[G]*, where R is a Ksemialgebra over a commutative semiring K in [7]. In this paper, we study some fundamental properties of subtractive, prime ideals of a Group graded semiring R and its identity component R1. We establish the existence of fuzzy ideals of R1 corresponding to the fuzzy ideals of R which enables us to settle many results for fuzzy ideals of R and R1. [ABSTRACT FROM AUTHOR]

The generalization of the results of group theory and ring theory to semirings is a very desirable feature in the domain of mathematics. The analogy between rings graded by a finite group G and rings on which G acts as automorphism has been observed by a number of mathematicians. The results of M. Lorenz and D.S. Passman [3], M. Lorenz, S. Montgomery and L.W. Small [4] proved for the rings with finite groups acting on them were extended by M. Cohen and S. Montgomery [1] for the group graded rings. Motivated by the analogy between the rings graded by a finite group G and rings on which G acts as automorphisms, we have derived certain results for a group graded semiring R, its ring of differences RΔ, and the smash product R # K[G]*, where R is a Ksemialgebra over a commutative semiring K in [7]. In this paper, we study some fundamental properties of subtractive, prime ideals of a Group graded semiring R and its identity component R1. We establish the existence of fuzzy ideals of R1 corresponding to the fuzzy ideals of R which enables us to settle many results for fuzzy ideals of R and R1. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and investigate semicorings over associative semirings and their categories of semicomodules. Our results generalize old and recent ones on corings over rings and their categories of comodules. The generalization is not straightforward and even subtle at several places due to the nature of the base category of commutative monoids which is neither Abelian (not even additive) nor homological, and has no nonzero injective objects. To overcome these and other difficulties, a combination of methods and techniques from categorical, homological and universal algebra is used including a new notion of exact sequences of semimodules over semirings. [ABSTRACT FROM AUTHOR]

L-fuzzy soft set is a generalization of fuzzy soft set. In the recent paper L-fuzzy soft sets have emerged as a new tool to characterize semirings. Concepts of L-fuzzy soft subsemirings and L-fuzzy ideals are introduced and some of their properties are studied. It is seen that L-fuzzy soft ideals have ability to characterize regular and weakly regular semirings. Finally fully idempotent semirings are characterized with the help of L-fuzzy soft ideals. [ABSTRACT FROM AUTHOR]

We introduced the notion of Hoehnke Radical class for associative semirings in. We give here some consequences of Hoehnke radical and hereditary Kurosh-Amitsur radical class. [ABSTRACT FROM AUTHOR]

Using a restrictive notion of exactness and the natural tensor product, we generalize several results related to flat modules over rings to flat semimodules over semirings. [ABSTRACT FROM AUTHOR]

Abstract: We show that for a semiring , the supports of all recognizable series over are recognizable if and only if in every finitely generated subsemiring of there exists a finite congruence such that is a singleton congruence class. [Copyright &y& Elsevier]

Given two domains of functions with values in a field, the canonical map from the algebraic tensor product of the vector spaces of functions on the two domains to the vector space of functions on the product of the two domains is well known to be injective, but not generally surjective. By constructing explicit examples, we show that the corresponding map for semimodules of semiring-valued functions is in general not even injective. This impacts the formulation of topological quantum field theories over semirings. We also confirm the failure of surjectivity for functions with values in complete, additively idempotent semirings by describing a large family of functions that do not lie in the image. [ABSTRACT FROM AUTHOR]

Abstract: We introduce and study an abstract class of semirings, which we call exact semirings, defined by a Hahn–Banach-type separation property on modules. Our motivation comes from the tropical semiring, and in particular a desire to understand the often surprising extent to which it behaves like a field. The definition of exactness abstracts an elementary property common to both fields and the tropical semiring, which we believe is fundamental to explaining this similarity. The class of exact semirings turns out to include many other important examples of both rings (proper quotients of principal ideal domains, matrix rings and finite group rings over these and over fields), and semirings (the Boolean semiring, generalisations of the tropical semiring, matrix semirings and group semirings over these). [Copyright &y& Elsevier]

Abstract: Since for the classification of finite (congruence-)simple semirings it remains to classify the additively idempotent semirings, we progress on the characterization of finite simple additively idempotent semirings as semirings of join-morphisms of a semilattice. We succeed in doing this for many cases, amongst others for every semiring of this kind with an additively neutral element. As a consequence we complete the classification of finite simple semirings with an additively neutral element. To complete the classification of all finite simple semirings it remains to classify some very specific semirings, which will be discussed here. Our results employ the theory of idempotent irreducible semimodules, which we develop further. [Copyright &y& Elsevier]