Search

Among the many research accomplishments of Val Tannen, his work on provenance and semirings is probably the most widely known. In this paper, we discuss questions that arise when applying this general framework to the setting of curated databases, and in particular the setting where we can have multiple annotations on the same data, as well as annotations on annotations.

Conditional independence plays a foundational role in database theory, probability theory, information theory, and graphical models. In databases, a notion similar to conditional independence, known as the (embedded) multivalued dependency, appears in database normalization. Many properties of conditional independence are shared across various domains, and to some extent these commonalities can be studied through a measure-theoretic approach. The present paper proposes an alternative approach via semiring relations, defined by extending database relations with tuple annotations from some commutative semiring. Integrating various interpretations of conditional independence in this context, we investigate how the choice of the underlying semiring impacts the corresponding axiomatic and decomposition properties. We specifically identify positivity and multiplicative cancellativity as the key semiring properties that enable extending results from the relational context to the broader semiring framework. Additionally, we explore the relationships between different conditional independence notions through model theory.

Slaba konvergencija niza pseudoverovatnoća i niza intervalno-vrednosnih pseudoverovatnoća je izučavana.Pokazani su ekvivalentni uslovi g-slabe konvergencije niza pseudoverovatnoća i niza intervalno-vrednosnih pseudoverovatnoća., Weak convergence of a sequence of pseudo-probability measures and a sequence of interval-valued pseudo- probability measures is investigated.The equivalent conditions of g-weak convergence of a sequence of pseudo-probability measures and a sequence of interval-valued pseudo-probability measures are proven.

In this paper, we introduce the notion of B-ideal in a commutative semiring R. Then 1) A characterization of B-ideals in the Semiring of non-negative integers is obtained. 2) Relation between B-ideals in a semiring R containing a Q-ideal I of R and B-ideals in the quotient semiring R/I(Q) is obtained. Further study of k-Noetherian semirings is developed. Also B-ideals in polynomial semirings are studied.

The GraphBLAS C specification provisional release 1.0 is complete. To manage the scope of the project, we had to defer important functionality to a future version of the specification. For example, we are well aware that many algorithms benefit from an inspector-executor execution strategy. We also know that users would benefit from a number of standard predefined semirings as well as more general user-defined types. These and other features are described in this paper in the context of a future release of the GraphBLAS C API.

The purpose of the GraphBLAS Forum is to stan- dardize linear-algebraic building blocks for graph computations. An important part of this standardization effort is to translate the mathematical specification into an actual Application Programming Interface (API) that (i) is faithful to the mathematics and (ii) enables efficient implementations on modern hardware. This paper documents the approach taken by the C language specification subcommittee and presents the main concepts, constructs, and objects within the GraphBLAS API. Use of the API is illustrated by showing an implementation of the betweenness centrality algorithm.

The purpose of this paper is to study content semimodules. We obtain some results on content semimodules similar to the corresponding ones on content modules. We study normally at content semimodules and multiplication content semimodules. More- over, we characterize content semimodules over discrete valuation semirings and Boolean algebras.

Rank data, in which each row is a complete or partial ranking of available items (columns), is ubiquitous. Among others, itcan be used to represent preferences of users, levels of gene expression, and outcomes of sports events. It can have many types ofpatterns, among which consistent rankings of a subset of the items in multiple rows, and multiple rows that rank the same subset of theitems highly. In this article, we show that the problems of finding such patterns can be formulated within a single generic framework thatis based on the concept of semiring matrix factorisation. In this framework, we employ the max-product semiring rather than theplus-product semiring common in traditional linear algebra. We apply this semiring matrix factorisation framework on two tasks: sparserank matrix factorisation and rank matrix tiling. Experiments on both synthetic and real world datasets show that the framework iscapable of discovering different types of structure as well as obtaining high quality solutions.

In this paper, (1) a characterization of 2-absorbing ideals in the semiring (Z+0 , gcd, lcm) is obtained; (2) some characterizations of 2-absorbing subtractive ideals in a semiring R are investigated; (3) the 2-absorbing avoidance theorem for subtractive ideals of a semiring R is obtained.

Generalizing the notion of regular ring in the sense of Von Neumann, Bourne, Adhikari, Sen and Wienert introduced the notion of k-regular semiring. In this paper, we investigate Q-ideals of the semiring of non-negative integers for which the quotient semiring is a semifield and a k-regular semiring. Also we prove that a semiring R is k-regular if and only if the quotient semiring R/I is k-regular for every Q-ideal I of R. Finally we prove that if R is an additively idempotent semiring with identity, then R is k-regular if and only if the matrix semiring Rní—n is k-regular.

All 2-absorbing ideals in the semiring of non-negative integers are investigated.

Integralne nejednakosti Jensena i Čebiševa uopštene su za integrale bazirane na neaditivnim merama. Prvo uopštenje dokazano je za pseudo-integral skupovno-vrednosne funkcije, a drugo za pseudo-integral realno-vrednosne funkcije u odnosu na intervalno-vrednosnu -meru. Dokazana je i uopštena nejednakost Čebiševa za pseudo-integral realno-vrednosne funkcije i njena dva intervalno-vrednosna oblika. Nejednakost Jensena je primenjena u principu premije, a nejednakost Čebiševa na procenu verovatnoće., Integral inequalities of Jensen and Chebyshev type are generalized for integrals based on nonadditive measures. The first generalization is proven for the pseudointegral of a set valued function and the second one for the pseudo-integral of a real-valued function with respect to the interval-valued -measure. Generalized Chebyshev inequality for the pseudo-integral of a realvalued function and its two interval-valued forms are proven. Jensen inequality is applied in the premium principle and Chebyshev inequality is applied to the probability estimation.

A reconstruction problem is formulated for multisets over commutative groupoids. The cards of a multiset are obtained by replacing a pair of its elements by their sum. Necessary and sufficient conditions for the reconstructibility of multisets are determined. These results find an application in a different kind of reconstruction problem for functions of several arguments and identification minors: classes of linear or affine functions over nonassociative semirings are shown to be weakly reconstructible. Moreover, affine functions of sufficiently large arity over finite fields are reconstructible.

We present a variant of the Weighted Maximum Satisfiability Problem(Weighted Max-SAT), which is a modeling of the Semiring Con- straint Satisfaction framework. We show how to encode a Semiring Con- straint Satisfaction Problem (SCSP) into an instance of a propositional Weighted Max-SAT, and call the encoding Weighted Semiring Max-SAT (WS-Max-SAT). The clauses in our encoding are highly structured and we exploit this feature to develop two algorithms for solving WS-Max- SAT: an incomplete algorithm based on the well-known GSAT algorithm for Max-SAT, and a branch-and-bound algorithm which is complete. Our preliminary experiments show that the translation of SCSP into WS- Max-SAT is feasible, and that our branch-and-bound algorithm performs surprisingly well. We aim in future to combine the natural exible rep- resentation of the SCSP framework with the inherent efficiencies of SAT solvers by adjusting existing SAT solvers to solve WS-Max-SAT.

In networks without centralized control (e.g. ad-hoc or peer-to-peer networks) the users cannot always be assumed to follow the protocol that they are supposed to. They will cooperate in the operation of the network to the extent that they achieve their own personal objectives. The decision to cooperate depends on the trust relations that users develop for each other through repeated interactions. Users who have not interacted directly with each other can use direct trust relations, generated by others, in a transitive way as a type of recommendation. Network operation and trust generation can be affected by malicious users, who have different objectives, and against whom any proposed solution needs to be robust. We model the generation of trust relations using repeated games of incomplete information to capture the repetitive operation of the network, as well as the lack of information of each user about the others' objectives. We find equilibria that provide solutions for the legitimate users against which the malicious users cannot improve their gains. The transitive computation of trust is modeled using semiring operators. This algebraic model allows us to generalize various trust computation algorithms. More importantly, we find the maximum distortion that a malicious user can cause to the trust computation by changing the reported trust value of a trust relation.

An important concept in network security is trust, interpreted as a relation among entities that participate in various protocols. Trust relations are based on evidence related to the previous interactions of entities within a protocol. In this work, we are focusing on the evaluation process of trust evidence in Ad Hoc Networks. Because of the dynamic nature of Ad Hoc Networks, trust evidence may be uncertain and incomplete. Also, no pre-established infrastructure can be assumed. The process is formulated as a path problem on a directed graph, where nodes represent entities, and edges represent trust relations. We show that two nodes can establish an indirect trust relation without previous direct interaction. The results are robust in the presence of attackers. We give intuitive requirements for any trust evaluation algorithm. The performance of the scheme is evaluated on various topologies.

Poluprsten je algebarska struktura (5, + , •) sa dve binarne operacije u kojoj su (S,+ ) i (5, •) polugrupe i druga je distributivna prema prvoj sa obe strane. U radu su uvedeni pojmovi p-polugrupe kao i p-poluprstena. Kažemo daje polugrupa ( S, + ) p-polugrupa ako (Vz G S)(3yG S)(x+py+x = y,py + x+py = z ). Poluprsten ( S, +.•)zovemo p-poluprsten ako (Vz G S)(3yG S)(x + py + x = y,py + x + py = z,4p z2 = 4pz). Dokazano je da je svaka p-polugrupa pokrivena grupama koje su u potpunosti opisane. Takođe je pokazano da su p-poluprsteni pokriveni pretprsteni-ma. Za p = 4A; + 3 (kG N0)ili p paran broj p-polugrupe, odnosno p-poluprsteni su varijeteti., A semiring (5 ,+ ,-) is an algebric structure with two binary operations in which ( S, + ) and (S,•) are semigroups, and the second operation is two-side dis­ tributive with respect to the first one. In the present paper notions of p-semigroup and p-semiring are introduced. We say that a semigroup (S', + ) is a p-semigroup if (Vx £ S)(3y £ S)(x + py + x = y,py + x + py = x).A semiring (S', + , •) is called a p-semiring if (Vx £ S)(3y£ S)(x +py + x = y,py + x + py = x,4px2 = 4px). It is proved that each p-semigroup is covered by groups which are completely described. It is also proved that p-semirings are covered by prering. For p = 4k + 3 (k £ No) or for even p, the class of p-semigroups, respectively of p-semirings are varieties.

U ovoj tezi je definisana uopštena konvolucija koja pripada domenu pseudo-analize i ima veliku primenu u mnogim matematičkim teorijama, npr. u proba-bilističkim metričkim prostorima, PDJ, teorijama odlučivanja, sistema, kontrole i fazi brojeva. Dokazane su bitne osobine ove operacije sa funkcijama. Dokazana je veza izmedju pseudo-konvolucija baziranih na poluprstenima različitih klasa Definisana je (5, C/)-konvolucija bazirana na uslovno distributivnom poluprstenu ([0,1], S, U)).Dat je još jedan vid uopštenja konvolucije baziran na uopštenim pseudo-operacijama., In this thesis the generalized convolution have been defined. This operation with functions has applications in different mathematical theo­ ries, for example in Probabilistic Metric Spaces, PDE, System and Control Theory, Fuzzy numbers. Some basic properties of this operation has been proved, as well as connection between generalized convolutions based on dif­ferent classes of semirings. (5, U)-convolution has been defined, as well as convolution based on generalized pseudo-operations.

We prove that if the direct sum of a family of semimodules over a semiring S is an injective semimodule or if the direct product of a family of semimodules over S is a projective semimodule, then the cardinality of the subfamily consisting of all semimodules which are not modules is strictly less than the cardinality of S. As a consequence, we obtain semiring analogs of well-known characterizations of classical semisimple, quasi-Frobenius, and one-sided Noetherian rings. © 2010 Allerton Press, Inc.

Problems concerning the extension of the Baer criterion for injectivity and embedding theorem of an arbitrary module over a ring into an injective module to the case of semirings are treated. It is proved that a semiring S satisfies the Baer criterion and every S-semimodule can be embedded in an injective semimodule if and only if S is a ring. © 2008 Pleiades Publishing, Ltd.

Necessary and sufficient conditions for the regularity of complete matrix semirings over au arbitrary semiring are obtained. ©2001 Plenum Publishing Corporation.

We prove that if the direct sum of a family of semimodules over a semiring S is an injective semimodule or if the direct product of a family of semimodules over S is a projective semimodule, then the cardinality of the subfamily consisting of all semimodules which are not modules is strictly less than the cardinality of S. As a consequence, we obtain semiring analogs of well-known characterizations of classical semisimple, quasi-Frobenius, and one-sided Noetherian rings. © 2010 Allerton Press, Inc.

Necessary and sufficient conditions for the regularity of complete matrix semirings over au arbitrary semiring are obtained. ©2001 Plenum Publishing Corporation.

Problems concerning the extension of the Baer criterion for injectivity and embedding theorem of an arbitrary module over a ring into an injective module to the case of semirings are treated. It is proved that a semiring S satisfies the Baer criterion and every S-semimodule can be embedded in an injective semimodule if and only if S is a ring. © 2008 Pleiades Publishing, Ltd.