Author name cluster

Guillermo Badia

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

FLAP Journal 2025 Journal Article

Definable Classes of Models and Frames in Bi-intuitionistic Logic

Guillermo Badia
Tomasz Kowalski
Grigory Olkhovikov

The question of the expressive power of a given logical language with Kripke relational semantics has at least two dimensions: (1) what the language can say about frames, and (2) what it can say about models. The Goldblatt–Thomason theorem provides a model-theoretic characterisation of modal axiomatisability for elementary classes of frames in terms of closure under taking generated sub- frames, disjoint unions, bounded morphic images, and reflection of ultrafilter extensions. Goldblatt also provides a similar characterisation for axiomatis- ability in intuitionistic logic of classes of models rather than frames. In this article we provide analogous results for bi-intuitionistic logic, a natural expres- sive extension of intuitionistic logic obtained by adding a binary connective dual to the intuitionistic implication, introduced in the 1970s independently by Dieter Klemke and Cecylia Rauszer. Together with previous results, such as a We are grateful to Jim de Groot with whom we discussed several of the ideas that appear here. We are also grateful to Katalin Bimbó for many editing suggestions that improved the presentation greatly. ∗ Support from ERC HORIZON2020-MSCA-RISE project no. 101007627 (MOSAIC) is gratefully acknowledged.

PDF Details

TIME Conference 2024 Conference Paper

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

Guillermo Badia
Carles Noguera
Alberto Paparella
Guido Sciavicco
Ionel Eduard Stan

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.

Details

MFCS Conference 2024 Conference Paper

Logical Characterizations of Weighted Complexity Classes

Guillermo Badia
Manfred Droste
Carles Noguera
Erik Paul

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.

Details

TCS Journal 2018 Journal Article

Fraïssé classes of graded relational structures

Guillermo Badia
Carles Noguera

We study classes of graded structures satisfying the properties of amalgamation, joint embedding and hereditariness. Given appropriate conditions, we can build a graded analogue of the Fraïssé limit. Some examples such as the class of all finite weighted graphs or the class of all finite fuzzy orders (evaluated on a particular countable algebra) will be examined.

Details DOI

FLAP Journal 2017 Journal Article

Model Definability in Relevant Logic.

Guillermo Badia

It is shown that the classes of Routley–Meyer models which are axioma- tizable by a theory in a propositional relevant language with fusion and the Ackermann constant can be characterized by their closure under certain model- theoretic operations involving prime filter extensions, relevant directed bisimu- lations and disjoint unions.

PDF Details