
Authors:
Haroldo G. BENATTI and Ruy J.G.B.de QUEIROZ
Title:Descriptive Complexity of Modularity Problems on Graphs
Pages:6175
File:bibtex
Abstract ( + )
The infinitary logic L^{ω} extends first order logic by allowing infinitary conjunctions and disjunctions and requiring that the formulas must have only a finite number of variables. Here we study the expressive power of !L^{ω} which is the existential negationfree fragment of L^{ω}. One of the important features of L^{ω} and !L^{ω} is that their expressive power can be characterized by semantic games. We use pebble games for L^{ω} to prove some problems about the modularity of the length of paths and circuits in directed graphs and in bipartite directed graphs are not definable in this logic. For that we show that those problems over bipartite directed graphs are NPcomplete.
Rather than seeking to classify classes of problems by the syntactical complexity of their description in some logical formalism, here we have worked in the other direction: we have shown lower bounds for the descriptive complexity of specific problems. This hints at a research programme which might be called ``concrete'' descriptive complexity, which may be useful in case studies of expressiveness of specific query languages, given that it may suggest a reverse process.

Authors:
Juliana BUENOSOLER and Walter CARNIELLI
Title:Possibletranslations Algebraization for Paraconsistent Logics
Pages:7792
File:bibtex
Abstract ( + )
This note proposes a new notion of algebraizability, which we call possibletranslations algebraic semantics, based upon the newly developed possibletranslations semantics. This semantics is naturally adequate to obtain an algebraic interpretation for paraconsistent logics, and generalizes the wellknown method of algebraization by W. Blok and D. Pigozzi. This generalization obtains algebraic semantics up to translations, applicable to several nonclassical logics and particularly apt for paraconsistent logics, a philosophically relevant class of logics with growing importance for applications.

Authors:
V.V. RIMATSKI and Vladimir V.RYBAKOV
Title:A Note on Globally Admissible Inference Rules for Modal and Superintuitionistic Logics
Pages:9399
File:bibtex
Abstract ( + )
In this shot note we consider globally admissible inference rules. A rule r is globally admissible in a logic L if r is admissible in all logics with the finite model property which extend L. Here we prove a reduction theorem: we show that, for any modal logic L extending K4, a rule r is globally admissible in L iff r is admissible in all tabular logics extending L. The similar result holds for superintuitionistic logics.

Authors:
Gemma ROBLES and Jose M. MENDEZ
Title:Relational Ternary Semantics for a Logic Equivalent to Involutive Mondial tnorm Based Logic IMTL
Pages:101116
File:bibtex
Abstract ( + )
We define the logic ICI complete with respect to certain ternary relational structures. ICI is a particular negation extension of Urquhart's manyvalued logic C. The logic ICI is deductively equivalent to Esteva and Godo's Involutive Monoidal tnorm based logic IMTL.