Browsing by Autor "Xavier Caicedo"

Now showing 1 - 7 of 7

A Finite Model Property for Gödel Modal Logics
(2018) Xavier Caicedo; George Metcalfe; Ricardo Óscar Rodríguez; Jonas Rogger
A new semantics with the finite model property is provided and used to establish decidability for Gödel modal logics based on (crisp or fuzzy) Kripke frames combined locally with Gödel logic. A similar methodology is also used to establish decidability, indeed co-NP-completeness, for a Gödel S5 logic that coincides with the one-variable fragment of first-order Gödel logic.
ASYMPTOTIC TRUTH-VALUE LAWS IN MANY-VALUED LOGICS
(Cambridge University Press, 2025) Guillermo Badía; Xavier Caicedo; Carles Noguera
Abstract This paper studies which truth-values are most likely to be taken on finite models by arbitrary sentences of a many-valued predicate logic. The classical zero-one law (independently proved by Fagin and Glebskiĭ et al.) states that every sentence in a purely relational language is almost surely false or almost surely true, meaning that the probability that the formula is true in a randomly chosen finite structures of cardinal n is asymptotically $0$ or $1$ as n grows to infinity. We obtain generalizations of this result for any logic with values in a finite lattice-ordered algebra, and for some infinitely valued logics, including Łukasiewicz logic. The finitely valued case is reduced to the classical one through a uniform translation and Oberschelp’s generalization of the zero-one law. Moreover, it is shown that the complexity of determining the almost sure value of a given sentence is PSPACE-complete (generalizing Grandjean’s result for the classical case), and for some logics we describe completely the set of truth-values that can be taken by sentences almost surely.
Congruences in regular categories
(LA Referencia, 1981) W. D. Burgess; Xavier Caicedo
Se investiga la composición de congruencias en categorías regulares y se demuestra, entre otros resultados, que la condición de Lawvere (toda relación de equivalencia es una congruencia) es equivalente en tales categorías a cualquiera de las siguientes propiedades: (i) la compuesta de congruencias que conmutan es una congruencia, (ii) un morfismo regular con congruencia r envía toda congruencia que conmuta con r a una congruencia en la imagen, (iii) cualquier par de morfismos regulares con congruencias que conmutan y tienen intersección trivial posee un "pushout" que es simultáneamente un "pullback". Con lo anterior es posible caracterizar las categorías regulares en las que la compuesta de congruencias es siempre una congruencia, generalizando así hechos bien conocidos del Algebra Universal.
Equivalence and quantifier rules for logic with imperfect information
(Oxford University Press, 2008) Xavier Caicedo; Francien Dechesne; Tim Janssen
In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore (restricted versions of) those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games.
Failure of interpolation for quantifiers of monadic type
(Springer Nature, 1985) Xavier Caicedo
Finitely axiomatizable quasivarieties of graphs
(Birkhäuser, 1995) Xavier Caicedo
Standard Gödel Modal Logics
(Springer Science+Business Media, 2010) Xavier Caicedo; Ricardo Óscar Rodríguez