Dagstuhl Seminar 25081
Semirings in Databases, Automata, and Logic
( Feb 16 – Feb 21, 2025 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25081
Organizers
- Guillermo Badia (University of Queensland - Brisbane, AU)
- Manfred Droste (Universität Leipzig, DE)
- Phokion G. Kolaitis (University of California - Santa Cruz, US & IBM Almaden Research Center - San Jose, US)
- Carles Noguera (University of Siena, IT)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
- Upload (Use personal credentials as created in DOOR to log in)
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
Please log in to DOOR to see more details.
- Samson Abramsky
- Paolo Agliano'
- Antoine Amarilli
- Albert Atserias
- Guillermo Badia
- Johanna Björklund
- Mikolaj Bojanczyk
- Camille Bourgaux
- Sophie Brinke
- Silvia Butti
- Xavier Caicedo
- Nofar Carmeli
- Petr Cintula
- Miroslav Ciric
- Victor Dalmau
- Manfred Droste
- Thomas Eiter
- Boris Glavic
- Erich Grädel
- Marcel Jackson
- Phokion G. Kolaitis
- Peter Kostolányi
- Egor Kostylev
- Paris Koutris
- Tomasz Kowalski
- Dietrich Kuske
- Andreas Maletti
- Filip Mazowiecki
- Kuldeep S. Meel
- George Metcalfe
- Hung Ngo
- Carles Noguera
- Nina Pardal
- Erik Paul
- Sudeepa Roy
- Jacques Sakarovitch
- Žaneta Semanišinová
- Dan Suciu
- Val Tannen
- Balder Ten Cate
- Wolfgang Thomas
- Sara Ugolini
- Jonni Virtema
Classification
- Databases
- Formal Languages and Automata Theory
- Logic in Computer Science
Keywords
- Semirings
- Databases
- Multi-valued logic
- Weighted automata
- Finite model theory
