Search Results

Documents authored by Badia, Guillermo

Document
DOI: 10.4230/DagRep.15.2.89
Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081)

Authors: Guillermo Badia, Manfred Droste, Phokion G. Kolaitis, Carles Noguera, Sophie Brinke, Lovro Mrkonjić, and Gaia Petreni

Published in: Dagstuhl Reports, Volume 15, Issue 2 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25081 "Semirings in Databases, Automata, and Logic", which was held from February 16 to 21, 2025. The seminar focused on semirings, a class of algebraic structures with many applications in computer science, particularly in databases and automata. Semirings are used in databases to annotate tuples in the input and output relations of queries (in particular, in the case of bag semantics, using the semiring of natural numbers) allowing to model several relevant aspects of databases. In automata theory, semirings allow to define weighted automata, which have applications in natural language processing, speech recognition, and image compression. Moreover, semirings are strongly related to the algebraic semantics of many-valued logics. The seminar brought together researchers from the communities mentioned above, and it developed a research agenda for studying semirings, guided by a collection of diverse applications. This led to several new collaborations between members from different communities, including joint work for publications.
Cite as

Guillermo Badia, Manfred Droste, Phokion G. Kolaitis, Carles Noguera, Sophie Brinke, Lovro Mrkonjić, and Gaia Petreni. Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081). In Dagstuhl Reports, Volume 15, Issue 2, pp. 89-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{badia_et_al:DagRep.15.2.89,
  author =	{Badia, Guillermo and Droste, Manfred and Kolaitis, Phokion G. and Noguera, Carles and Brinke, Sophie and Mrkonji\'{c}, Lovro and Petreni, Gaia},
  title =	{{Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081)}},
  pages =	{89--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{2},
  editor =	{Badia, Guillermo and Droste, Manfred and Kolaitis, Phokion G. and Noguera, Carles and Brinke, Sophie and Mrkonji\'{c}, Lovro and Petreni, Gaia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.2.89},
  URN =		{urn:nbn:de:0030-drops-230893},
  doi =		{10.4230/DagRep.15.2.89},
  annote =	{Keywords: databases, finite model theory, multi-valued logic, provenance, semirings, weighted automata, weighted logic}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.7
Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation

Authors: Guillermo Badia, Carles Noguera, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Many-valued logics, often referred to as fuzzy logics, are a fundamental tool for reasoning about uncertainty, and are based on truth value algebras that generalize the Boolean one; the same logic can be interpreted on algebras from different varieties, for different purposes and pose different challenges. Although temporal many-valued logics, that is, the many-valued counterpart of popular temporal logics, have received little attention in the literature, the many-valued generalization of Halpern and Shoham’s interval temporal logic has been recently introduced and studied, and a sound and complete tableau system for it has been presented for the case in which it is interpreted on some finite Heyting algebra. In this paper, we take a step further in this inquiry by exploring a tableau system for Halpern and Shoham’s interval temporal logic interpreted on some finite {FL_{ew}}-algebra, therefore generalizing the Heyting case, and by providing its open-source implementation.
Cite as

Guillermo Badia, Carles Noguera, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan. Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{badia_et_al:LIPIcs.TIME.2024.7,
  author =	{Badia, Guillermo and Noguera, Carles and Paparella, Alberto and Sciavicco, Guido and Stan, Ionel Eduard},
  title =	{{Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.7},
  URN =		{urn:nbn:de:0030-drops-212145},
  doi =		{10.4230/LIPIcs.TIME.2024.7},
  annote =	{Keywords: Interval temporal logic, many-valued logic, tableau system}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.14
Logical Characterizations of Weighted Complexity Classes

Authors: Guillermo Badia, Manfred Droste, Carles Noguera, and Erik Paul

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Fagin’s seminal result characterizing NP in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there has been much interest in the investigation of quantitative (weighted) models of computations. In this paper, we start the study of descriptive complexity based on weighted Turing machines over arbitrary semirings. We provide machine-independent characterizations (over ordered structures) of the weighted complexity classes NP[𝒮], FP[𝒮], FPLOG[𝒮], FPSPACE[𝒮], and FPSPACE_poly[𝒮] in terms of definability in suitable weighted logics for an arbitrary semiring 𝒮. In particular, we prove weighted versions of Fagin’s theorem (even for arbitrary structures, not necessarily ordered, provided that the semiring is idempotent and commutative), the Immerman-Vardi’s theorem (originally for 𝖯) and the Abiteboul-Vianu-Vardi’s theorem (originally for PSPACE). We also discuss a recent open problem proposed by Eiter and Kiesel. Recently, the above mentioned weighted complexity classes have been investigated in connection to classical counting complexity classes. Furthermore, several classical counting complexity classes have been characterized in terms of particular weighted logics over the semiring ℕ of natural numbers. In this work, we cover several of these classes and obtain new results for others such as NPMV, ⊕𝖯, or the collection of real-valued languages realized by polynomial-time real-valued nondeterministic Turing machines. Furthermore, our results apply to classes based on many other important semirings, such as the max-plus and the min-plus semirings over the natural numbers which correspond to the classical classes MaxP[O(log n)] and MinP[O(log n)], respectively.
Cite as

Guillermo Badia, Manfred Droste, Carles Noguera, and Erik Paul. Logical Characterizations of Weighted Complexity Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{badia_et_al:LIPIcs.MFCS.2024.14,
  author =	{Badia, Guillermo and Droste, Manfred and Noguera, Carles and Paul, Erik},
  title =	{{Logical Characterizations of Weighted Complexity Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.14},
  URN =		{urn:nbn:de:0030-drops-205707},
  doi =		{10.4230/LIPIcs.MFCS.2024.14},
  annote =	{Keywords: Descriptive complexity, Weighted Turing machines, Weighted logics, Semirings}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact