DROPS

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}
}

Search Results

Documents authored by Badia, Guillermo

Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation

Abstract

Cite as

Logical Characterizations of Weighted Complexity Classes

Abstract

Cite as

Thanks for your feedback!

Could not send message