Semirings are fundamental algebraic structures that in recent times have found a number of applications to computer science, especially in the areas of databases and automata. On the side of databases, commercial query languages, such as SQL, use bag semantics, instead of set semantics, to evaluate relational database queries, which means that the semiring of the natural numbers is used to annotate tuples in the input and output relations. More generally, the annotations can be values in some fixed semiring; this gives a common generalization of both set semantics and bag semantics of database queries, and also makes it possible to model other situations in which one is interested, e.g., in the probability or the reliability of an answer. Furthermore, semirings of polynomials have been successfully used to carry out a rigorous study of provenance in databases. On the side of automata, semirings are used to define weighted automata, which are nondeterministic finite automata augmented with values from a semiring as weights on the transitions. These weights may model, e.g., the cost involved when executing a transition, the amount of resources or time needed for this, or the probability or reliability of its successful execution. Weighted automata have found numerous applications to natural language processing, speech recognition, and algorithms for digital image compression.

These applications have inspired numerous investigations in the logic-in-computer-science community. For instance, motivated by the work on semirings in databases, the evaluation of arbitrary first-order formulas in semirings has been recently explored in the literature, where, among other things, the relation between elementary equivalence (i.e., indistinguishability in first-order logic) and isomorphism on finite structures has been examined. In the same vein, various notions of locality in the semiring framework have been studied and zero-one laws and convergence laws have been obtained, whereas Ehrenfeucht–Fraïssé games have been used to characterize equivalence up to bounded quantifier rank under semiring semantics. As regards semirings and automata, Kleene’s classical theorem on the characterization of languages recognized by automata with languages denoted by regular expressions was extended by Schützenberger to the behaviors of weighted automata and rational power series. By a fundamental theorem of Büchi, Elgot, and Trakhtenbrot, finite automata have the same expressive power on words as monadic second-order logic; therefore, various problems about this logic on words are decidable. In recent years, a suitable weighted logic was developed and shown to have the same expressive power on words, trees, and graphs as weighted automata. Consequently, this weighted logic has similar decidability properties on these structures as the unweighted monadic second-order logic. In turn, both of these approaches could be seen as part of the framework of many-valued logics, where algebraic structures expanding semirings with suitable operations have been studied for a long time.

The main goal of this Dagstuhl Seminar is to bring together researchers from the different communities mentioned above and to develop a research agenda for studying semirings, guided by a collection of diverse applications. The seminar will feature invited tutorials and long talks, contributed talks, a problem session, and a closing session to formulate future research directions. The schedule of the seminar will be developed in such a way that will allow sufficient time for informal discussions and exchange of ideas between participants.

Creative Commons BY 4.0

Guillermo Badia, Manfred Droste, Phokion G. Kolaitis, and Carles Noguera